In the rescheduling on a single machine, a set of the original jobs has already been scheduled, in order to make a given objective function is optimal. The decision maker needs to insert the new jobs into the existing...In the rescheduling on a single machine, a set of the original jobs has already been scheduled, in order to make a given objective function is optimal. The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it. A batching machine is a machine that can handle up to some jobs simultaneously. In this paper,we consider the total completion time under a limit on the sequence disruptions for parallel batching based on rescheduling. For the parallel batching problem based on rescheduling, we research the properties of feasible schedules and optimal schedules on the total completion time under a limit on the maximum time disruptions or total time disruptions, in which the jobs are sequenced in SPT order, and give out the pseudo-polynomial time algorithms on the number of jobs and the processing time of jobs by applying the dynamic programming method.展开更多
In the rescheduling on a single machine,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.The decision maker needs to insert the ...In the rescheduling on a single machine,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.The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it.In this paper,we consider hierarchical optimization between the scheduling cost of all the jobs and the degree of this disruption.For every problem,we provide either a polynomial time algorithm or an intractable result.展开更多
基金Supported by the National Natural Science Foundation of China（11271338, 11201121, 71201049） Supported by the National Natural Science Foundation of Henan Province（112300410078） Supported by the Natural Science Foundation of the Education Department of Henan Province（2011B110008）
文摘In the rescheduling on a single machine, a set of the original jobs has already been scheduled, in order to make a given objective function is optimal. The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it. A batching machine is a machine that can handle up to some jobs simultaneously. In this paper,we consider the total completion time under a limit on the sequence disruptions for parallel batching based on rescheduling. For the parallel batching problem based on rescheduling, we research the properties of feasible schedules and optimal schedules on the total completion time under a limit on the maximum time disruptions or total time disruptions, in which the jobs are sequenced in SPT order, and give out the pseudo-polynomial time algorithms on the number of jobs and the processing time of jobs by applying the dynamic programming method.
基金Supported by the NSFC(10671183)Supported by the Science Foundation of Henan University of Technology(07XJC002)+1 种基金Supported by the NSF of the Education Department of Henan Province(2008A11004)Supported by the NSF of Henan Province(082300410190)
文摘In the rescheduling on a single machine,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.The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it.In this paper,we consider hierarchical optimization between the scheduling cost of all the jobs and the degree of this disruption.For every problem,we provide either a polynomial time algorithm or an intractable result.
