On no-wait and no-idle flow shops with makespan criterion

被引：50

作者：

Kalczynski, Pawel Jan ^{[1
]}

Kamburowski, Jerzy ^{[1
]}

机构：

[1] Univ Toledo, Coll Business Adm, Dept Informat Operat & Technol Management, Toledo, OH 43606 USA

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2007年 / 178卷 / 03期

关键词：

scheduling; flow shops; makespan; no-wait condition; no-idle condition;

D O I：

10.1016/j.ejor.2006.01.036

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

The paper deals with the NP-hard problems of minimizing the makespan in m-machine no-wait and no-idle permutation flow shops. We identify networks whose longest path lengths represent the makespans. These networks reveal the duality between the two problems, and show graphical explanations of the fact that under no-wait and no-idle conditions the makespan can be a decreasing function of some job processing times. Moreover, they also lead to a natural reduction of the no-wait flow shop problem to the traveling salesman problem, some lower bounds on the shortest makespan, and new efficiently solvable special cases. (c) 2006 Elsevier B.V. All rights reserved.

引用

页码：677 / 685

页数：9

共 21 条

[1] Minimizing cycle time in a blocking flowshop [J].

Abadi, INK ;

Hall, NG ;

Sriskandarajah, C .

OPERATIONS RESEARCH, 2000, 48 (01) :177-180

[2]

Achuthan N. R., 1977, Opsearch, V14, P71

[3] FLOWSHOP NO-IDLE OR NO-WAIT SCHEDULING TO MINIMIZE THE SUM OF COMPLETION TIMES [J].

ADIRI, I ;

POHORYLES, D .

NAVAL RESEARCH LOGISTICS, 1982, 29 (03) :495-504

[4] No-wait flowshops with bicriteria of makespan and maximum lateness [J].

Allahverdi, A ;

Aldowaisan, T .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2004, 152 (01) :132-147

[5]

BAPTISTE P, 1997, INT C IND ENG PROD M

[6] THE ANALYSIS OF ACTIVITY NETWORKS UNDER GENERALIZED PRECEDENCE RELATIONS (GPRS) [J].

ELMAGHRABY, SE ;

KAMBUROWSKI, J .

MANAGEMENT SCIENCE, 1992, 38 (09) :1245-1263

[7] SEQUENCING 1 STATE-VARIABLE MACHINE - SOLVABLE CASE OF TRAVELING SALESMAN PROBLEM [J].

GILMORE, PC ;

GOMORY, RE .

OPERATIONS RESEARCH, 1964, 12 (05) :655-&

[8] Some local search algorithms for no-wait flow-shop problem with makespan criterion [J].

Grabowski, J ;

Pempera, J .

COMPUTERS & OPERATIONS RESEARCH, 2005, 32 (08) :2197-2212

[9] A survey of machine scheduling problems with blocking and no-wait in process [J].

Hall, NG ;

Sriskandarajah, C .

OPERATIONS RESEARCH, 1996, 44 (03) :510-525

[10]

Johnson Selmer Martin., 1954, NAV RES LOG, V1, P61, DOI [10.1002/(ISSN)1931-9193, DOI 10.1002/NAV.3800010110, 10.1002/nav.3800010110]

← 1 2 3 →