Efficiency of reductions of job-shop to flow-shop problems

被引：6

作者：

Guinet, A ^{[1
]}

机构：

[1] Inst Natl Sci Appl Lyon, Lab PRISMa, F-69621 Villeurbanne, France

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2000年 / 125卷 / 03期

关键词：

scheduling theory; optimisation; heuristics; job-shop; flow-shop;

D O I：

10.1016/S0377-2217(99)00389-6

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

We study the problem of scheduling N independent jobs in a job-shop environment. Each job must be processed on at most M machines according to individual routes. The objective is to minimise the maximum completion time of the jobs. First, the job-shop problem is reduced to a flow-shop problem with job precedence constraints. Then, an extension of Johnson's rule is defined to solve it. The optimality of the extended Johnson's rule is proved for two machine jobshop problems and the rule efficiency for some three and four machine job-shop problems is shown. (C) 2000 Elsevier Science B.V. All rights reserved.

引用

页码：469 / 485

页数：17

共 20 条

[1] THE SHIFTING BOTTLENECK PROCEDURE FOR JOB SHOP SCHEDULING [J].

ADAMS, J ;

BALAS, E ;

ZAWACK, D .

MANAGEMENT SCIENCE, 1988, 34 (03) :391-401

[2] A GRAPHICAL APPROACH TO PRODUCTION SCHEDULING PROBLEMS [J].

AKERS, SB .

OPERATIONS RESEARCH, 1956, 4 (02) :244-245

[3] SEQUENCING RULES AND DUE-DATE ASSIGNMENTS IN A JOB SHOP [J].

BAKER, KR .

MANAGEMENT SCIENCE, 1984, 30 (09) :1093-1104

[4]

Baker KR., 1974, Introduction to Sequencing and Scheduling

[5]

BERNAD J, 1973, PRODUCTION GESTION, V252, P21

[6]

CAMPBELL HG, 1970, MANAGE SCI B-APPL, V16, pB630

[7] THE ONE-MACHINE SEQUENCING PROBLEM [J].

CARLIER, J .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1982, 11 (01) :42-47

[8]

CHARALAMBOUS O, 1991, INFORMATION DECISION, V3, P189

[9]

Christofides N., 1979, COMBINATORIAL OPTIMI

[10]

Dell'Amico M., 1993, Annals of Operations Research, V41, P231, DOI 10.1007/BF02023076

← 1 2 →