|
|||||
|
|
Three is easy, two is hard: open shop sum-batch scheduling problem refined |
|
| Authors: | Irina V Gribkovskaia Vitaly A Strusevich Dominique de Werra |
| Institution: | a Molde University College, Molde, Norway b Hong Kong University of Science and Technology, Hong Kong c University of Greenwich, London, UK d École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland |
| 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. |
| Keywords: | Scheduling Open shop Batching Polynomial-time algorithm |
| 本文献已被 ScienceDirect 等数据库收录！ | |