About Some Of The Results Of Reordering

The theory of scheduling, as a branch of the operations research has its profound theoretical and broad applied prospect. Scheduling is to assign jobs processed on machines under some constraints, such that one- or multi-criteria are attained to the optimum. It can be divided into classical scheduling and modern scheduling. There have been more than ten modern scheduling models which are widely discussed over the last twenty years, such as the scheduling with controllable processing time, the batching scheduling, multi-criteria scheduling, the scheduling with transportation constraints and so on. In this paper, we consider rescheduling problems where a set of original jobs has already been scheduled to minimize some cost objective, when a new set of jobs arrives and creates a disruption. We assume that π^* is an optimal schedule of original jobs and ο is any schedule of all jobs. Let D_j(π^*,ο) denote the sequence disruption and Δ_j(π^*,ο) denote the time disruption of job j between π^* and ο, respectively. We simplify (D_j(ο)) and Δ_j(ο) to D_j(π^*) and D_j(π^*), respectively. The disruptions considered in this thesis are as follows. D_max(π^*): the maximum sequence disruption; A_max(π^*): the maximum time disruption; ΣD_j(π^*) : the total sequence disruption; ΣD_j(π^*): the total time disruption.The works of this paper are the development of the research works of Hall and Potts etc (2004). We consider two classes of models: minnimize the scheduling cost of all the jobs and minimize a total cost objective, which includes both the original cost measure and the cost of disruption. The main works of this paper are as follows:(1) Problem 1|D_max(π^*)≤ k₁, Δ_max(π^*) ≤k₂,ΣD_j(π^*)< k₃,ΣD_j(π^*)≤k₄|EC_j can be solved in O(n_O²n_N²min{n_OPN, n_NPo}) time.(2) Problem 1||L_max + μ₁D_max(π^*) + μ₂Δ_max(π^*) can be solved in O(n + n_N\ogn_N) time.(3) Problem 1|| ΣC_j + μ₁D_max{π^*) + μ₂Δ_max(π^*) can be solved in O(n + n_N logn_N) time.(4) Problem 1|| ΣC_j +μ₁ΣD_j(π^*) + μ₂ΣΔ_j(π^*) can be solved in O(n + n_Nlog_n)...