Rescheduling Research Under Pareto Optimization And Disruption Constraint

Rescheduling is a new class of scheduling problems in scheduling research. Due to its important research value and wide practical application background, rescheduling has been studied extensively in the field of scheduling theory in the last decade.The model of rescheduling can be stated as follows. A set of original jobs has been scheduled （but has not been processed） optimally to minimize some cost function and promises have been made to customers based on the schedule. Then a new set of jobs arrives unexpectedly before the processing starts and has to be scheduled on a common machine with the set of original jobs. The production planners need to adjust the existing schedule and address the trade-off between the scheduling cost and the disruptions of all the original jobs, with a view to obtaining a cost-efficient schedule without causing too much inconveniences to customers.This thesis includes two parts. In the first part, we consider the Pareto optimization of rescheduling problem for jobs on a single machine with release dates to minimize the makespan and the total sequence disruption simultaneously. In the second part, we intro-duce and study two new rescheduling models:（1） The job-disruption constraint reschedul-ing problems in which each original job has its own disruption constraint, and （2） the weighted disruption rescheduling problems in which each original job has the correspond-ing penalty of unit disruption.In Chapter2, we consider the Pareto optimization rescheduling problem1（?）(C_max,∑D_j). For rescheduling with release dates to minimize makespan under a limit on the total sequence disruption, a weakly polynomial-time algorithm has been provided in the literature. We present a strongly polynomial-time algorithm for finding all Pareto optimal points of the Pareto optimization problem. Consequently, the rescheduling problem to minimize makespan under a limit on the total sequence disruption can be solved in a strongly polynomial time.In Chapter3, we study the job-disruption constraint rescheduling problems and the weighted disruption rescheduling problems. The following results are presented:（1） Devel-op a polynomial-time algorithm for the job-disruption constraint rescheduling problem to minimize the maximum lateness under a limit on the sequence disruption of each job:（2） Provide a polynomial-time algorithm for the job-disruption constraint rescheduling prob-lem to minimize the total completion time under a limit on the sequence disruption of each job;（3） For the two job-disruption constraint rescheduling problems to minimize the total completion time or the maximum lateness under a limit on the time disruption of each job, provide NP-hardness proofs, approximation algorithms and intractability results;（4） For the three weighted disruption rescheduling problems to minimize the total completion time, the makespan or the maximum lateness under a limit on the total weighted time disruption, provide the strongly NP-hardness proofs;（5） For both job-disruption rescheduling prob-lems and weighted disruption rescheduling problems, we give polynomial-time algorithms for some special cases.