On-line Rescheduling to Minimize Makespan under a Limit on the Mazimum Disruptions
In the on-line 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 over time. The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it. In this paper, we consider the on-line rescheduling problem to minimize makespan under a limit on the maximum disruption constraints and give an on-line algorithm of competitive ratio3/2.
rescheduling sequence disruption time disruption single machine on-line algorithm competitive ratio
Yundong Mu Xiao Guo
College of Science, Henan University of Technology Zhengzhou, Peoples Republic of China
国际会议
南昌
英文
141-144
2009-09-01（万方平台首次上网日期，不代表论文的发表时间）