The machine duplication problem in a job shop with two jobs

The machine duplication problem in a job shop with two jobs

0.00 Avg rating0 Votes
Article ID: iaor1996137
Country: United Kingdom
Volume: 2
Issue: 1
Start Page Number: 45
End Page Number: 60
Publication Date: Jan 1995
Journal: International Transactions in Operational Research
Authors: ,
Keywords: heuristics
Abstract:

This paper addresses a problem related to the classical job shop scheduling problem with two jobs. The problem consists in concurrently determining the best subset of machines to be duplicated and the optimal scheduling of the operations in order to minimize completion time. Such a problem arises in the tool management for a class of flexible manufacturing cells. The job shop with two jobs is first reviewed, the application of the classical search algorithm A* to this problem is discussed and its performance compared with a previous approach. The complexity of the machine duplication problem is then analysed. The problem is proved to be in general NP-hard in the strong sense, but in a class of special cases, relevant from the applications viewpoint, it can be solved in polynomial time by a dynamic programming algorithm. A heuristic based on such an algorithm and on A* is proposed for the general problem; the results are satisfactory in terms of both efficiency and quality of the solution.

Reviews

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