|
| << previous | next >> |
Journal description
All volumes of the corresponding journal
All issues of the corresponding volume
All articles of the corresponding issues
Details for article 2 of 10 found articles
| Title: |
An improved approximation algorithm for the two-machine open shop scheduling problem with family setup times |
| Author: |
Billaut, Jean-Charles Gribkovskaia, Irina Strusevich, Vitaly |
| Appeared in: |
IIE transactions |
| Paging: | Volume 40 (2008) nr. 4 pages 478-493 |
| Year: |
2008-04 |
| Contents: |
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. |
| Publisher: |
Taylor & Francis |
| Source file: |
Elektronische Wetenschappelijke Tijdschriften |
Details for article 2 of 10 found articles
| << previous | next >> |