An improved approximation algorithm for the two-machine open shop scheduling problem with family setup times

An improved approximation algorithm for the two-machine open shop scheduling problem with family setup times

0.00 Avg rating0 Votes
Article ID: iaor200972093
Country: United States
Volume: 40
Issue: 4
Start Page Number: 478
End Page Number: 493
Publication Date: Apr 2008
Journal: IIE Transactions
Authors: , ,
Abstract:

We consider the problem of scheduling families of jobs in a two-machine open shop so as to minimize the makespan. The jobs of each family can be partitioned into batches and a family setup time on each machine is required before the first job is processed, and when a machine switches from processing a job of some family to a job of another family. For this NP-hard problem the literature contains (5/4)-approximation algorithms that cannot be improved on using the class of group technology algorithms in which each family is kept as a single batch. We demonstrate that there is no advantage in splitting a family more than once. We present an algorithm that splits one family at most once on a machine and delivers a worst-case performance ratio of 6/5.

Reviews

Required fields are marked *. Your email address will not be published.