Journal article

Online Machine Scheduling with Family Setups

Lele Zhang, Andrew Wirth

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH | WORLD SCIENTIFIC PUBL CO PTE LTD | Published : 2016

Abstract

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.