Rescheduling For New Orders With Precedence Constraints And Disruption Indicators

Rescheduling is a modern scheduling model which received very much attention and appears popularly in human life. For example,in the manufacture industry,we need rescheduling the no-processed jobs when it has a disruption,which creates by the new orders arriving,order cancellations,changes in order priority,alter in release dates, machine error and so on.In the research for the rescheduling with new jobs arriving,Hall and Potts(2004) introduced the sequence disruptions and the time disruptions of the original jobs and studied several rescheduling problems for minimizing scheduling cost under the limitation of the disruptions.Afterwards,the research for this model is very active.Bases on the research of Hall and Potts(2004),we introduce in this paper the disruption indicators of the original jobs and convention that the precedence constraints between the jobs are given by double total order or single total order.We use Prec(O,N)to express the double total order,Prec(O,Φ)the single total order of the original jobs,and prec(Φ,N) the single total order of the new jobs.We study the computational complexity of various rescheduling problems according the variation of the precedence constraints,the variation of the disruption limitations,and the variation of the objective functions. The main results of this paper are as follows:·For Γ∈{Dmax(π*),△max(π*)},γ∈{∑fj(Cj),fmax),the rescheduling problem1|prec(O,N),Γ≤k|γ can be solved in polynomial O(nOnN)time.·For Γ=∑Dj(π*),γ∈{∑fj(Cj),fmax},the rescheduling problem1|prec(O,N), Γ≤k|γ can be solved in polynomial O(n2On2N)time.·For Γ=∑△j(π*),γ∈{∑fj(Cj),fmax},the rescheduling problem1|prec(O,N), Γ≤k|γ can be solved in pseudo-polynomial O(n2OnNP(N)nN)time.·For Γ≤∈{∑wj∧Dj(π*),∑wj∧△j(π*)},γ∈{∑fj(Cj),fmax},the rescheduling problem1|prec(O,N),Γ≤k|γ can be solved in polynomial O(nOnN)time.·The rescheduling problem1|prec(O,Φ),∑∧Dj(π*)≤k｜∑Cj can be solved in polynomial O(nOnN)time.Especially,when prec(O)is given by the SPT order,the problem can be solved in polynomial O(n+nN log nN)time..The rescheduling problem1|prec(O,φφ),∑∧(π*)≤k｜Lmax can be solved in polynomial O(nonN)time. Especially,when prec(O)is given by the EDD order,the problem can be solved in polynomial O(n+nN log nN)time..For every given г,the rescheduling problems1|prec(O,φ),г≤k|∑jfj(Cj)and1|prec(φ,N),г≤k|∑fj(Cj)axe strongly NP-hard.