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

Billaut, Jean-Charles, Gribkovskaia, Irina and Strusevich, Vitaly A. (2008) *An improved approximation algorithm for the two-machine open shop scheduling problem with family setup times.* IIE Transactions, 40 (4). pp. 478-493. ISSN 1545-8830 (electronic) 0740-817X (paper) (doi:10.1080/07408170701592473)

## 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.

Item Type: | Article |
---|---|

Uncontrolled Keywords: | scheduling, open shop, batching, group technology, approximation |

Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science |

School / Department / Research Groups: | School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Department of Mathematical Sciences School of Computing & Mathematical Sciences > Statistics & Operational Research Group |

Related URLs: | |

Last Modified: | 31 Mar 2011 18:20 |

URI: | http://gala.gre.ac.uk/id/eprint/1212 |

### Actions (login required)

View Item |