Reorder

Scheduling is to allocate some jobs or tasks to some machines under a limited condition according to time order, and in order to optimize some objectives.Rescheduling is one of significant modern scheduling models and it is motivated by important applications. The problem of rescheduling in the face of dynamically arriving orders is faced constantly by manufacturing companies. The manufacturing companies have been made their production schedules in earlier according to their planes or some customers' call, and schedule the jobs by some rule to optimize some objective. However it frequently happens that additional orders arrive after a schedule has been developed. These orders must then be integrated into the schedule so as to optimize some measure of system performance without causing undue disruption in the shop. Based on some researches, Hall and Potts (2004) studied the problem of rescheduling and introduced the conception of disruptions. They considered the rescheduling problem to minimize the maximum lateness and total completion time under a limit on the disruption constraints.Multicriteria scheduling, as a way of multi-objective decision-making, plays an important role in solving complicated problems arising from economics, administration, engineering, etc.. For example, a factory administrator needs to arrange the jobs to be processed such that the total completion time is minimized firstly to reduce the processing cost and the tardy jobs are limited to a lowest level secondly, and to satisfy the clients. Multicriteria scheduling includes lexicographical optimization or hierarchical optimization, Pareto optimization and composite objective function optimization.On-line scheduling is a modern scheduling model, in which the job information may not be known in advance. A job becomes available for processing at its arrival time, and its processing time only becomes known upon its arrival. Once the jobs have been scheduled, the states of the jobs cannot be changed. In the off-line scheduling, the information of all jobs has been completely known in advance. The performance of an on-line algorithm is described by its competitiveness, i.e. the ratio of the result of the on-line algorithm and the optimal value of the off-line situation for the same jobs. Exactly, for the problem of minimizing objective, the competitive ratioρof an on-line algorithm is defined as the supremum of the ratio of C and C₀, where C and C₀ are the objective of scheduling obtained by the on-line algorithm and an optimal off-line algorithm, respectively.This paper includes four parts. In the first part, some spacial solvable cases of rescheduling models are considered (Chapter 2). In the second part, the new rescheduling models are studied (Chapter 3). In the third part, multi-criteria rescheduling models are discussed (Chapter 4). In the last part, on-line rescheduling problems are presented (Chapter 5).In Chapter 2, the following results are developed. (1) The rescheduling problem to minimize the maximum lateness or the total completion time under a limit on the disruption constraints when d_j, p_j are compatible or the original jobs are fixed order are solvable in polynomial time or pseudo-polynomial time. (2) The rescheduling problem to minimize the total tardiness under a limit on the disruption constraints when p_j = p or d_j = d are solvable in polynomial time or pseudo-polynomial time. (3) The rescheduling problem for jobs on a single machine to minimize total weighted completion time under a limit on the maximum disruption when p_j and w_j of the jobs are anticompatible are solvable in polynomial time or pseudo-polynomial time.In Chapter 3, the following results are developed. (1) The rescheduling problem for jobs on a single machine with release dates to minimize makespan under a limit on the maximum sequence disruption is solvable in polynomial time. (2) The rescheduling problem for jobs on a single machine with release dates to minimize makespan under a limit on the total sequence disruption can be solved in polynomial time. (3) The rescheduling problems for jobs on a single machine with release dates to minimize makespan under a limit on the maximum time disruption or the total time disruption are strongly NP-hard.Chapter 4 studies the multicriteria rescheduling problems. In this parts, the disruptions of the original jobs are regarded as an objective in the same as classical objectives. The rescheduling problems of hierarchical optimization, Pareto optimization and linear composite objective function optimization between the classical scheduling cost (such as C_max, L_max,∑w_jC_j) of all the jobs and the degree of the disruptions (D_max(Ï€^*),Δ_max(Ï€^*),∑D_j(Ï€^*),∑Δ_j(Ï€^*)) are considered. For some problems, we provide a polynomial or pseudo-polynomial time algorithm.Chapter 5 discusses the on-line rescheduling problems. In this parts, the original jobs have been arrived and sequenced by some rule, the new jobs arrive over time. For the online rescheduling problem to minimize the maximum lateness under a limit on the disruption constraints, a 2-competitive ratio algorithm is presented. For the online rescheduling problem to minimize makespan under a limit on the disruption constraints with release date, some |-competitive ratio algorithms are presented.