Efficient algorithms for flexible job shop scheduling with parallel machines

被引：16

作者：

Kubiak, Wieslaw ^{[1
]}

Feng, Yanling ^{[2
]}

Li, Guo ^{[3
,4
]}

Sethi, Suresh P. ^{[5
]}

Sriskandarajah, Chelliah ^{[6
]}

机构：

[1] Mem Univ Newfoundland, Fac Business Adm, St John, NF, Canada

[2] Beijing Univ Posts & Telecommun, Sch Econ & Management, Beijing, Peoples R China

[3] Beijing Inst Technol, Sch Management & Econ, Beijing 100081, Peoples R China

[4] Beijing Inst Technol, Ctr Energy & Environm Policy Res, Beijing, Peoples R China

[5] Univ Texas Dallas, Naveen Jindal Sch Management, Dallas, TX USA

[6] Texas A&M Univ, Mays Business Sch, College Stn, TX USA

来源：

NAVAL RESEARCH LOGISTICS | 2020年 / 67卷 / 04期

基金：

中国博士后科学基金; 中国国家自然科学基金;

关键词：

absolute worst-case error bound; approximation algorithm; flexible job shop scheduling; makespan; SEQUENCE-DEPENDENT SETUP; GENETIC ALGORITHM; OPTIMIZATION; TARDINESS; DEADLINES; SEARCH;

D O I：

10.1002/nav.21901

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

Job shop scheduling with a bank of machines in parallel is important from both theoretical and practical points of view. Herein we focus on the scheduling problem of minimizing the makespan in a flexible two-center job shop. The first center consists of one machine and the second has k parallel machines. An easy-to-perform approximate algorithm for minimizing the makespan with one-unit-time operations in the first center and k-unit-time operations in the second center is proposed. The algorithm has the absolute worst-case error bound of k - 1, and thus for k = 1 it is optimal. Importantly, it runs in linear time and its error bound is independent of the number of jobs to be processed. Moreover, the algorithm can be modified to give an optimal schedule for k = 2.

引用

页码：272 / 288

页数：17

共 36 条

[1] MINIMIZING MAXIMUM LATENESS IN A 2-MACHINE UNIT-TIME JOB SHOP [J].

BRUCKER, P .

COMPUTING, 1981, 27 (04) :367-370

[2] AN ALGORITHM FOR SOLVING THE JOB-SHOP PROBLEM [J].

CARLIER, J ;

PINSON, E .

MANAGEMENT SCIENCE, 1989, 35 (02) :164-176

[3] Flexible job shop scheduling with parallel machines using Genetic Algorithm and Grouping Genetic Algorithm [J].

Chen, James C. ;

Wu, Cheng-Chun ;

Chen, Chia-Wen ;

Chen, Kou-Huang .

EXPERT SYSTEMS WITH APPLICATIONS, 2012, 39 (11) :10016-10021

[4] Preemptive Parallel-Machine Scheduling with a Common Server to Minimize Makespan [J].

Cheng, T. C. E. ;

Kravchenko, Svetlana A. ;

Lin, Bertrand M. T. .

NAVAL RESEARCH LOGISTICS, 2017, 64 (05) :388-398

[5] A Branch-and-Bound Algorithm for the Prize-Collecting Single-Machine Scheduling Problem with Deadlines and Total Tardiness Minimization [J].

Cordone, Roberto ;

Hosteins, Pierre ;

Righini, Giovanni .

INFORMS JOURNAL ON COMPUTING, 2018, 30 (01) :168-180

[6] New multi-objective method to solve reentrant hybrid flow shop scheduling problem [J].

Dugardin, Frederic ;

Yalaoui, Farouk ;

Amodeo, Lionel .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 203 (01) :22-31

[7]

Emmons H., 2013, FLOW SHOP SCHEDULING, V182

[8] A three-layer chromosome genetic algorithm for multi-cell scheduling with flexible routes and machine sharing [J].

Feng, Yanling ;

Li, Guo ;

Sethi, Suresh P. .

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2018, 196 :269-283

[9]

Garey M. R., 1976, Mathematics of Operations Research, V1, P117, DOI 10.1287/moor.1.2.117

[10] Scatter search with path relinking for the flexible job shop scheduling problem [J].

Gonzalez, Miguel A. ;

Vela, Camino R. ;

Varela, Ramiro .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2015, 245 (01) :35-45

← 1 2 3 4 →