Batch Scheduling on a Two-Machine Jobshop with Machine-Dependent Setup Times

被引：5

作者：

Mosheiov, Gur ^{[1
]}

Oron, Daniel ^{[2
]}

机构：

[1] Hebrew Univ Jerusalem, Sch Business Adm, IL-91905 Jerusalem, Israel

[2] Univ Sydney, Sch Business, Sydney, NSW 2006, Australia

来源：

NAVAL RESEARCH LOGISTICS | 2011年 / 58卷 / 07期

关键词：

batch scheduling; jobshop; setup-time; unit execution time jobs; FLOWSHOP;

D O I：

10.1002/nav.20473

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The problem of minimum makespan on an In machine jobshop with unit execution time (UET) jobs (m >= 3) is known to be strongly NP-hard even with no setup times. We focus in this article on the two-machine case. We assume UET jobs and consider batching with batch availability and machine-dependent setup times. We introduce an efficient (O(root n)) algorithm, where n is the number of jobs. We then introduce a heuristic for the multimachine case and demonstrate its efficiency for two interesting instances. (C) 2011 Wiley Periodicals, Inc. Naval Research Logistics 58: 676-684, 2011

引用

页码：676 / 684

页数：9

共 8 条

[1] A survey of scheduling problems with setup times or costs [J].

Allahverdi, Ali ;

Ng, C. T. ;

Cheng, T. C. E. ;

Kovalyov, Mikhail Y. .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 187 (03) :985-1032

[2] Batch Scheduling on Two-Machine Flowshop with Machine-Dependent Setup Times [J].

Ben-Dati, Lika ;

Mosheiov, Gur ;

Oron, Daniel .

ADVANCES IN OPERATIONS RESEARCH, 2009, 2009

[3]

Cheng TCE, 2000, NAV RES LOG, V47, P128, DOI 10.1002/(SICI)1520-6750(200003)47:2<128::AID-NAV4>3.0.CO

[4]

2-#

[5] Scheduling batches with sequential job processing for two-machine flow and open shops [J].

Glass, CA ;

Potts, CN ;

Strusevich, VA .

INFORMS JOURNAL ON COMPUTING, 2001, 13 (02) :120-137

[6]

Lenstra JK, 1979, Annals of discrete mathematics, V4, P121

[7] A note on flow-shop and job-shop batch scheduling with identical processing-time jobs [J].

Mosheiov, G ;

Oron, D .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2005, 161 (01) :285-291

[8] Open-shop batch scheduling with identical jobs [J].

Mosheiov, Gur ;

Oron, Daniel .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 187 (03) :1282-1292

← 1 →