Title :
On-Line Rescheduling to Minimize Makespan under a Limit on the Maximum Disruptions
Author :
Mu, Yundong ; Guo, Xiao
Author_Institution :
Coll. of Sci., Henan Univ. of Technol., Zhengzhou, China
Abstract :
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 overtime. 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 ratio 3/2.
Keywords :
job shop scheduling; minimisation; job scheduling; online rescheduling; single machine; Conference management; Costs; Educational institutions; Electronic government; Job shop scheduling; Manufacturing; Procurement; Production facilities; Single machine scheduling; Technology management; competitive ratio; on-line algorithm; rescheduling; sequence disruption; single machine; time disruption;
Conference_Titel :
Management of e-Commerce and e-Government, 2009. ICMECG '09. International Conference on
Conference_Location :
Nanchang
Print_ISBN :
978-0-7695-3778-8
DOI :
10.1109/ICMeCG.2009.26
