Skip navigation

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

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

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)

Full text not available from this repository.

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
Pre-2014 Departments: School of Computing & Mathematical Sciences
School of Computing & Mathematical Sciences > Department of Mathematical Sciences
Related URLs:
Last Modified: 14 Oct 2016 09:09
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
URI: http://gala.gre.ac.uk/id/eprint/3668

Actions (login required)

View Item View Item