A branch-and-price algorithm for the general case of scheduling parallel machines with a single server

Search Swinburne Research Bank

Home

Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.3/211007

Title: A branch-and-price algorithm for the general case of scheduling parallel machines with a single server
Author(s): Gan, Heng-Soon; Wirth, Andrew; Abdekhodaee, Amir
Abstract: 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.
Publication type: Journal article
Research centre: Swinburne University of Technology. Faculty of Engineering and Industrial Sciences
Source: Computers and Operations Research, Vol. 39, no. 9 (Sep 2012), pp. 2242-2247
Publication year: 2012
FOR Code(s): 0102 Applied Mathematics; 0103 Numerical and Computational Mathematics
Keyword(s): Algorithms; Parallel machines; Scheduling; Servers
Publisher: Elsevier
ISSN: 0305-0548
Publisher URL: http://dx.doi.org/10.1016/j.cor.2011.11.007
Peer reviewed