Rescheduling to Minimize Total Completion Time Under a Limit Time Disruption for the Parallel Batch  

作　　者：XU Xiao-yan MU Yun-dong GUO Xiao HAO Yun 

机构地区：[1]School of Science, Henan University of Technology, Zhengzhou 450001, China

出　　处：《Chinese Quarterly Journal of Mathematics》2015年第2期274-279,共6页数学季刊（英文版）

基　　金：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.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.

关 键 词：RESCHEDULING single machine parallel batch time disruptions 

分 类 号：O223[理学—运筹学与控制论]