Online Machine Scheduling with Family Setups
Lele Zhang, Andrew Wirth
ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH | WORLD SCIENTIFIC PUBL CO PTE LTD | Published : 2016
We consider the problem of online scheduling a single machine with family setups under job availability. A setup must be scheduled when the next job comes from a different family from the last completed one, if any. The aim is to minimize the total completion time of all jobs. For the special case of identical processing times, we provide a lower bound for the competitive ratio and an online algorithm with its competitive analysis.