Premium
The Machine Duplication Problem in a Job Shop with Two Jobs
Author(s) -
Agnetis A.,
Oriolo G.
Publication year - 1995
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.1995.tb00004.x
Subject(s) - job shop scheduling , computer science , mathematical optimization , job shop , scheduling (production processes) , heuristic , time complexity , class (philosophy) , flow shop scheduling , mathematics , algorithm , artificial intelligence , schedule , operating system
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.