The total completion time open shop scheduling problem with a given sequence of jobs on one machine

The total completion time open shop scheduling problem with a given sequence of jobs on one machine

0.00 Avg rating0 Votes
Article ID: iaor2003194
Country: United Kingdom
Volume: 29
Issue: 9
Start Page Number: 1251
End Page Number: 1266
Publication Date: Aug 2002
Journal: Computers and Operations Research
Authors: , ,
Keywords: heuristics, programming: branch and bound
Abstract:

This paper addresses the open shop scheduling problem to minimize the total completion time, provided that one of the machines has to process the jobs in a given sequence. The problem is NP-hard in the strong sense even for the two-machine case. A lower bound is derived based on the optimal solution of a relaxed problem in which the operations on every machine may overlap except for the machine with a given sequence of jobs. This relaxed problem is NP-hard in the ordinary sense; however, it can be quickly solved via a decomposition into subset-sum problems. Both heuristic and branch-and-bound algorithm are proposed. Experimental results show that the heuristic is efficient for solving large-scaled problems, and the branch-and-bound algorithm performs well on small-scaled problems.

Reviews

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