Reduction of job-shop problems to flow-shop problems with precedence constraints

Reduction of job-shop problems to flow-shop problems with precedence constraints

0.00 Avg rating0 Votes
Article ID: iaor19992902
Country: Netherlands
Volume: 109
Issue: 1
Start Page Number: 96
End Page Number: 110
Publication Date: Aug 1998
Journal: European Journal of Operational Research
Authors: ,
Keywords: optimization, heuristics
Abstract:

We study the problem of scheduling N independent jobs in a job-shop environment. Each job must be processed on M machines according to individual routes. The objective is to minimize the maximum completion time of the jobs. First, the job-shop problem is reduced to a flow-shop problem with job precedence constraints. Then, a set of flow-shop algorithms are modified to solve it. To evaluate the quality of these heuristics, several lower bounds on the optimal solution have been computed and compared with the heuristic solutions for 3040 problems. The heuristics appear especially promising for job-shop problems with ‘flow-like’ properties.

Reviews

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