Machine Scheduling Problems With Batch Delivery Consideration

In this thesis we study a class of machine scheduling problems with batch delivery consideration. Traditional scheduling problems assume that there are always infinite vehicles for delivering finished jobs to their customers, and the deliveries need no time, so that the finished jobs can be delivered to the respective customers without delay. However, the number of vehicles is finite and the delivery time is not zero in the real world. Differing from traditional scheduling problems, we study a class of two-stage scheduling problems, in which the jobs J1,J2,…,Jn are first processed in the processing stage and then delivered in batches by a single vehicle with limited capacity to the respective customers in the delivering stage. The goal is to find a schedule that minimizes the makespan, i.e., the time by which the vehicle has delivered the last job to the customer and returned to the initial location. Depending on specific problem characteristics, the processing systems or the delivery types can be different. We design some algorithms for the different cases.In Chapter1we first introduce the basic concepts of combinatorial optimization. Then we review some main results of scheduling problems. At last, we introduce the machine scheduling problems with batch delivery consideration and some related models.In Chapter2we consider the problem in which the processing system is parallel machines, there is only one customer and the jobs have an identical size. We distinguish two types of batching strategies. The strategy of Type1permits the jobs processed on different machines to compose a delivery batch; however, the strategy of Type2assumes that only the jobs processed on the same machine can compose a batch. For both types of the m-machine case, we propose (2-1/m)-approximation algorithms respectively. For both types of the two-machine case, we obtain two improved4/3-approximation algorithms.In Chapter3we consider the problem in which the processing system is two parallel machines, there is only one customer and the jobs have nonidentical sizes. We study the strategy of Type1, and provide an improved algorithm with the worst-case performance ratio14/9+∈.In Chapter4we consider the problem in which the processing system is one single machine, and the customers locate at the vertices of a star-shaped network. We present a3/2-approximation algorithm for the identical job size case and a2-approximation algorithm for the nonidentical job sizes case.In Chapter5we consider the problem in which the processing system is one single machine, and the customers locate at different locations. For the identical job size case, we present a polynomial time algorithm when the number of customers is fixed. For the nonidentical job sizes case, we consider a special case with three customers and develop a2-approximation algorithm.In Chapter6we consider the problem in which the processing system is a two-machine flow shop, there is only one customer and the jobs have nonidentical sizes. We provide a2-approximation algorithm.In Chapter7we present a conclusion as well as a discussion of future research directions.