# Three is easy, two is hard: open shop sum-batch scheduling problem refined

Tools

Lee, Chung-Yee, Gribkovskaia, Irina, Strusevich, Vitaly A. and de Werra, Dominique
(2006)
*Three is easy, two is hard: open shop sum-batch scheduling problem refined.*
Operations Research Letters, 34 (4).
pp. 459-464.
ISSN 0167-6377
(doi:10.1016/j.orl.2005.07.006)

Official URL: http://dx.doi.org/10.1016/j.orl.2005.07.006

## Abstract

For the two-machine open shop sum-batch problem to minimize the makespan an optimal schedule is known to contain

one, two or three batches on each machine, and finding a two-batch optimal schedule is NP-hard. We adapt the open shop

algorithm by de Werra for finding a three-batch optimal schedule in linear time.

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

Uncontrolled Keywords: | scheduling, open shop, batching, polynomial-time algorithm |

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

School / Department / Research Groups: | School of Computing & Mathematical Sciences Faculty of Architecture, Computing & Humanities > School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Department of Mathematical Sciences Faculty of Architecture, Computing & Humanities > School of Computing & Mathematical Sciences > Department of Mathematical Sciences |

Related URLs: | |

Last Modified: | 08 Nov 2010 14:26 |

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

### Actions (login required)

View Item |