A branch-and-bound algorithm for solving a two-machine flow shop problem with deteriorating jobs

被引：59

作者：

Ng, C. T. ^{[1
]}

Wang, J. -B. ^{[1
,2
]}

Cheng, T. C. E. ^{[1
]}

Liu, L. L. ^{[1
,3
]}

机构：

[1] Hong Kong Polytech Univ, Dept Logist & Maritime Studies, Kowloon, Hong Kong, Peoples R China

[2] Shenyang Inst Aeronaut Engn, Dept Sci, Shenyang 110034, Peoples R China

[3] Shanghai Second Polytech Univ, Sch Sci, Shanghai 201209, Peoples R China

来源：

COMPUTERS & OPERATIONS RESEARCH | 2010年 / 37卷 / 01期

关键词：

Scheduling; Flow shop; Deteriorating jobs; Total completion time; Branch-and-bound algorithm; DEPENDENT PROCESSING TIMES; TOTAL COMPLETION-TIME; SCHEDULING PROBLEMS; MACHINES;

D O I：

10.1016/j.cor.2009.03.019

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

In this paper we consider a two-machine flow shop scheduling problem with deteriorating jobs. By a deteriorating job we mean that the job's processing time is an increasing function of its starting time. We model job deterioration as a function that is proportional to a linear function of time. The objective is to find a sequence that minimizes the total completion time of the jobs. For the general case, we derive several dominance properties, some lower bounds, and an initial upper bound by using a heuristic algorithm, and apply them to speed up the elimination process of a branch-and-bound algorithm developed to solve the problem. (C) 2009 Elsevier Ltd. All rights reserved.

引用

页码：83 / 90

页数：8

共 11 条

[1]

Alidaee B, 1999, J OPER RES SOC, V50, P711, DOI 10.2307/3010325

[2] A concise survey of scheduling with time-dependent processing times [J].

Cheng, TCE ;

Ding, Q ;

Lin, BMT .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2004, 152 (01) :1-13

[3]

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

[4]

HARDY GH, 1964, INEQUALITIES, P261

[5] APPLICATION OF BRANCH AND BOUND TECHNIQUE TO SOME FLOW-SHOP SCHEDULING PROBLEMS [J].

IGNALL, E ;

SCHRAGE, L .

OPERATIONS RESEARCH, 1965, 13 (03) :400-&

[6] NP-hard cases in scheduling deteriorating jobs on dedicated machines [J].

Kononov, A ;

Gawiejnowicz, S .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2001, 52 (06) :708-717

[7] Minimizing total completion time in a two-machine flowshop with a learning effect [J].

Lee, WC ;

Wu, CC .

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2004, 88 (01) :85-93

[8] Complexity analysis of job-shop scheduling with deteriorating jobs [J].

Mosheiov, G .

DISCRETE APPLIED MATHEMATICS, 2002, 117 (1-3) :195-209

[9] Efficient heuristic and optimal approaches for n/2/F/Sigma C-i scheduling problems [J].

Wang, CG ;

Chu, CB ;

Proth, JM .

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 1996, 44 (03) :225-237

[10] Flow shop scheduling problems with deteriorating jobs under dominating machines [J].

Wang, JB ;

Xia, Q .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2006, 57 (02) :220-226

← 1 2 →