Article ID: | iaor20121292 |
Volume: | 39 |
Issue: | 9 |
Start Page Number: | 2242 |
End Page Number: | 2247 |
Publication Date: | Sep 2012 |
Journal: | Computers and Operations Research |
Authors: | Wirth Andrew, Gan Heng-Soon, Abdekhodaee Amir |
Keywords: | combinatorial optimization |
We consider the strongly NP‐hard problem of scheduling two‐operation non‐preemptable jobs on two identical parallel machines. A single server, that can handle at most one job at a time, is available to carry out the first (or setup) operation. The second operation, to be carried out on the same machine but without the server, must be executed immediately after the setup. The objective is to minimize the makespan. We apply a column generation method to a population of partial schedules, in turn generated by some well known heuristics, to achieve effective and efficient solutions. We compare the performance of this method with those proposed earlier and also suggest future work.