Reduction of job-shop problems to flow-shop problems with precedence constraints |
| |
| Institution: | 1. Department of Chemical System Engineering, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, 113-8656 Tokyo, Japan;2. F. Hoffmann–La Roche Ltd, Grenzacherstrasse 124, 4070 Basel, Switzerland;3. Institute for Chemical and Bioengineering, ETHZ, Vladimir-Prelog-Weg 1, 8093 Zurich, Switzerland;1. Departamento de Ingeniería Informática y de Sistemas - IUDR, Universidad de La Laguna, Spain;2. Escuela de Ingeniería y Ciencias, Tecnológico de Monterrey, Mexico;3. Facultad de Ingeniería Mecánica y Eléctrica, Universidad Autónoma de Nuevo León, Mexico |
| |
| 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
