Study On Integrated Production And Delivery Scheduling On A Serial-Batch Machine

Scheduling is one of the most active fields of operational research, and a large amount of scheduling models under different machine environments have been studied. In this pa-per, we study scheduling problems on a serial-batch machine with integrated production and delivery. In order to save time and/or cost, the coordination between job produc-tion and job delivery has been widely discussed in the literature. There are usually two traditional methods to deliver all jobs. The first method always sends the finished jobs individually and immediately to their customers. It is generally assumed that there is a sufficient number of vehicles. The second method transports the finished jobs in batches to their customers. Clearly, the second method needs fewer vehicles and lower delivery costs than the first method. In this paper, we adopt the second method to deliver all jobs. Due to the limits of facilities, the machine and the vehicle may be have limited capacity.Lu et al. [26] introduced the concept of "split" in their problems. Under the assump-tion of "split", a job Jj can be split into two parts Jj and Jj such that Jj and Jj can be viewed as two independent jobs for processing and delivery.In this paper, we study the coordination of scheduling and delivery on serial-batching machine with limited capacity. The contents in this research can be divided into two parts. In the first part, we study the serial-batch scheduling problem with split-allowed delivery, where the delivery is made in batches with limited capacity. In the second part, we study the scheduling problem with no split, where production and delivery are made in batches with limited capacity.In Chapter 2, we study one case of serial-batch scheduling problem which only the delivery batch is bounded, and split is allowed in delivery:· We present a 4/3-approximation algorithm, which improves the 3/2-approximation algorithm in Lu et al. [26].· We present a polynomial-time algorithm for a special case when all jobs have the same size.In Chapter 3, we study one case of the bounded serial-batch scheduling problem which the processing batch and the delivery batch are both bounded:· When the restriction is the number of jobs in the processing batch and the delivery batch, we present two dynamic programming algorithms with two different values.· When the restriction is the general weight restriction in the processing batch and the delivery batch, we present a polynomial-time algorithm where split is allowed in both pro-duction and delivery. Also, we present a 2-approximation algorithm under the condition that job is not allowed spilt.