The Rescheduling Problems with Linear Relationship for Sequence Disruption and Time Disruption

In this paper，we consider the rescheduling problems which sequence disruption and time disruption is a linear relationship，that is maximum sequence disruption and maximum time disruption，maximum sequence disruption and total time disruption，total sequence disruption and maximum time disruption，total sequence disruption and total time disruption，the objective is to minimize the total completion time.Rescheduling problem is a set of original jobs that have been scheduled on a single machine according to some orders.There is another set of new jobs that arrive over time.Preemption is not permitted，so that no interruption in the processing of a job is allowed.The goal is to find a schedule of original jobs set and new jobs set that minimize some objective subject to some disruption constraints.According to classical scheduling theory，we show that shortest processing time first rule is to minimize objective functions，and design some algorithms by dynamic programming，given examples and time complexity of algorithms.