An O(n2) algorithm for the variable common due date, minimal tardy jobs bicriteria two-machine flow shop problem with ordered machines

被引：15

作者：

Panwalkar, S. S. ^{[2
]}

Koulamas, Christos ^{[1
]}

机构：

[1] Florida Int Univ, Dept Decis Sci & Informat Syst, Miami, FL 33199 USA

[2] Johns Hopkins Univ, Carey Business Sch, Baltimore, MD 21202 USA

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2012年 / 221卷 / 01期

关键词：

Scheduling; Flow shop; Multi-criteria problems; SCHEDULING PROBLEM; REJECTION; NUMBER;

D O I：

10.1016/j.ejor.2012.02.020

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider the ordinary NP- hard two-machine flow shop problem with the objective of determining simultaneously a minimal common due date and the minimal number of tardy jobs. We present an O(n(2)) algorithm for the problem when the machines are ordered, that is, when each job has its smaller processing time on the first (second) machine. We also discuss the applicability of the proposed algorithm to the corresponding single-objective problem in which the common due date is given. (C) 2012 Elsevier B.V. All rights reserved.

引用

页码：7 / 13

页数：7

共 20 条

[1]

[Anonymous], 2009, PRINCIPLES SEQUENCIN, DOI DOI 10.1002/9780470451793

[2] SCHEDULING IN A SEMI-ORDERED FLOWSHOP WITHOUT INTERMEDIATE QUEUES [J].

ARORA, RK ;

RANA, SP .

AIIE TRANSACTIONS, 1980, 12 (03) :263-272

[3] Multiprocessor scheduling with rejection [J].

Bartal, Y ;

Leonardi, S ;

Marchetti-Spaccamela, A ;

Sgall, J ;

Stougie, L .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2000, 13 (01) :64-78

[4]

Bellman R., 1982, MATH ASPECTS SCHEDUL

[5] Minimizing tardy jobs in a flowshop with common due date [J].

Della Croce, F ;

Gupta, JND ;

Tadei, R .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 120 (02) :375-381

[6]

Della Croce F., 2011, EVOLUTIONARY COMPUTA

[7] Techniques for scheduling with rejection [J].

Engels, DW ;

Karger, DR ;

Kolliopoulos, SG ;

Sengupta, S ;

Uma, RN ;

Wein, J .

JOURNAL OF ALGORITHMS, 2003, 49 (01) :175-191

[8]

Gupta JND, 1997, J OPER RES SOC, V48, P212, DOI 10.1057/palgrave.jors.2600346

[9] Flowshop-scheduling problems with makespan criterion: a review [J].

Hejazi, SR ;

Saghafian, S .

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2005, 43 (14) :2895-2929

[10] The three-machine proportionate flow shop problem with unequal machine speeds [J].

Hou, SX ;

Hoogeveen, H .

OPERATIONS RESEARCH LETTERS, 2003, 31 (03) :225-231

← 1 2 →