Equal processing and equal setup time cases of scheduling parallel machines with a single server

Equal processing and equal setup time cases of scheduling parallel machines with a single server

0.00 Avg rating0 Votes
Article ID: iaor2005504
Country: United Kingdom
Volume: 31
Issue: 11
Start Page Number: 1867
End Page Number: 1889
Publication Date: Sep 2004
Journal: Computers and Operations Research
Authors: , ,
Keywords: combinatorial analysis, heuristics
Abstract:

This paper considers the deterministic 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. Two special cases which arise in practice, the equal processing times and regular equal setup times problems turn out to be closely linked to the restricted set partitioning problem. This link is used to show that they are NP-hard in the ordinary sense, and to construct a tight lower bound and two highly effective O(n log n) heuristics.

Reviews

Required fields are marked *. Your email address will not be published.