Some Scheduling Problems With Transportation Consideration

Scheduling problem, one of the classical combinatorial optimization problems, has gained great attention from both manufacturers and academic researchers. This thesis mainly concerns a type of scheduling problems with job delivery coordination, which have broad application prospects in supply chain management. The thesis is split into four chapters.We first introduce some related preliminary concepts of supply chain and scheduling and then summarize recent research results of scheduling problems with transportation in chapter 1.In chapter 2, A two-machine flowshop scheduling problem with intermediate transporta-tion is investigated, where jobs of varying size finished on the last machine need to be transported to the other machine for further processing. One service vehicle of a limited capacity is used for transportation between the two machines. The problem objective is to minimize the makespan, or the finishing time of the last job on the second machine. Us-ing a better bin-packing algorithm and balancing between two schedules, we present an 11/5 approximation algorithm for the problem.In chapter 3, we discuss a problem with a single machine but with jobs that must be delivered to each one of customer areas, in which every job needs to be delivered to its customer after production and the completion time is defined as the time when the job arrives at its customer. There is one vehicle with limited capacity, and each job occupies different size in the vehicle during transportation. The goal is to minimize the maximum job completion time. When there is a single machine for processing jobs and only two customers, we propose a polynomial-time approximation algorithm with worst case ratio of 5/3.In chapter 4, we study identical (uniform) machine scheduling models that explicitly consider constraints on both transportation capacity and transportation times. In the model a set of jobs are first processed in a processing facility and then delivered to the customers directly without intermediate inventory. There is only one vehicle is available to deliver the finished jobs and each job demands different amount of storage space during transportation. According to different characteristics of the machine environment, two cases are studied: 1) If the machine environment is parallel processors, we discuss the both case of m= 3 and the general m machine.2) If the machine environment is uniform processors, we consider the both case of m= 2 and the general m machine. The goal is minimizing the time when all jobs are completed and delivered to the customer area and the vehicle returns to the machine. Because of NP-hardness, we provide polynomial time approximation algorithms for the problem. If there are m parallel processors, our algorithm has a worst case ratio of 7/3-1/m. If only 3 parallel processors are valid, it can be improved to 17/10. For the problem of parallel processors, we design and analyze approximation algorithms for both the case of m=2 and the general m machine case. The worst case ratio is shown to be 5/3=1/6s and 20/9+(?)/3, respectively.