Search Swinburne Research Bank
Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.3/73654
- Scheduling two parallel machines with a single server: the general case
- Abdekhodaee, Amir H.; Wirth, Andrew; Gan, Heng-Soon
- This paper considers the problem of scheduling two-operation non-preemptable jobs on two identical semi-automatic machines. A single server is available to carry out the first (or setup) operation. The second operation is executed automatically, without the server. The general problem of makespan minimization is NP-hard in the strong sense. In earlier work, we showed that the equal total length problem is polynomial time and we also provided efficient and effective solutions for the special cases of equal setup and equal processing times. Most of the cases analyzed thus far have fallen into the category of regular problems. In this paper we build on this earlier work to deal with the general case. Various approaches will be considered. One may reduce the problem to a regular one by amalgamating jobs, or we may apply the earlier heuristics to (possibly regular) job clusters. Alternately we may apply a greedy heuristic, a metaheuristic such as a genetic algorithm or the well known Gilmore-Gomory algorithm to solve the general problem. We report on the performance of these various methods.
- Publication type
- Journal article
- Computers and Operations Research, Vol. 33, no. 4 (Apr 2006), pp. 994-1009
- Publication year
- Genetic algorithms; Heuristic methods; Job analysis; Operations research; Parallel machines; Parallel processing systems; Polynomials; Problem solving; Scheduling; Semi-automatic machines; Servers; Setup; Single server
- Publisher URL
- Copyright © 2004 Elsevier Ltd. All rights reserved.
- Peer reviewed