Identical Machines Scheduling Problems With Delivery Coordination To Minimize The Maximum Delivery Completion Time

In this dissertation, we study two parallel-machine scheduling problems with delivery coordination. The objectives of the two problems are to minimize the maximum delivery completion time, i.e., the time when all the jobs are delivered to their respective customers and the vehicle returns to the facility. Since the operations of the jobs consists of two stages of processing and delivery, we call such problems as two-stage scheduling problems.In Chapter 2, we study the two-stage parallel-machine scheduling problem with job preemption. In the problem, a set N={1,2, …,n} of n jobs are first processed preemptively on m identical machines and then delivered to their customers by only one vehicle which can deliver one job at each shipment. A schedule for the problem includes a scheme for the preemptive processing of the n jobs on the m machines and a scheme for the delivery of the n jobs, where a job j can be delivered only if it has completed its processing and the only vehicle is available. Let Dj be the delivery completion time of job j, i.e., the time when job j is delivered to its customer and the vehicle returns to the facility. We use-Dmax to denote the maximum delivery completion time of all jobs. Following the classification scheme for scheduling problems by Graham et al. [23], the problem in consideration is denoted by P|pmtn|.Dmax. We show that the problem is strongly NP-hard and present a 3/2 -approximation algorithm.In Chapter 3, we study the two-stage parallel-machine scheduling problem without job preemption under the ADT (assignable delivery times) assumption. In the problem, a set N={1,2, …,n} of n jobs are first processed on m identi-cal machines and then delivered to their customers by only one vehicle which can deliver one job at each shipment. Moreover, a set of n delivery times are given in advance, but each delivery time does not belong to a specific job. A schedule for the problem includes a processing scheme of the n jobs on the m machines, an assignment of the n delivery times to the n jobs, and a delivery scheme for the delivery of the n jobs, where a job j can be assigned a delivery time and delivered only if it has completed its processing and the only vehicle is available. Let Dj be the delivery completion time of job j, i.e., the time when job j is delivered to its customer and the vehicle returns to the facility. We use-Dmax to denote the maximum delivery completion time of all jobs. Following the classification scheme for scheduling problems by Graham et al. [23], the problem in consid-eration is denoted by P|ADT|.Dmax. Note that the classical strongly NP-hard scheduling problem P||Cmax is a special version of problem P|ADT|Dmax. Then problem P|ADT|Dmax is also strongly NP-hard. For this problem, we present a 3/2-approximation algorithm and a polynomial-time approximation scheme (P-TAS).