Bi-criteria minimization for the permutation flowshop scheduling problem with machine-based learning effects

被引:14
作者
Chung, Yu-Hsiang [1 ]
Tong, Lee-Ing [1 ]
机构
[1] Natl Chiao Tung Univ, Dept Ind Engn & Management, Hsinchu 300, Taiwan
关键词
Scheduling; Learning effect; Flowshop; Total completion time; Makespan; TOTAL COMPLETION-TIME; SINGLE-MACHINE; 2-MACHINE FLOWSHOP; BOUND ALGORITHM; RELEASE TIMES; HEURISTICS; TARDINESS; MAKESPAN;
D O I
10.1016/j.cie.2012.03.009
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
In traditional scheduling problems, the processing time for the given job is assumed to be a constant regardless of whether the job is scheduled earlier or later. However, the phenomenon named "learning effect" has extensively been studied recently, in which job processing times decline as workers gain more experience. This paper discusses a bi-criteria scheduling problem in an m-machine permutation flowshop environment with varied learning effects on different machines. The objective of this paper is to minimize the weighted sum of the total completion time and the makespan. A dominance criterion and a lower bound are proposed to accelerate the branch-and-bound algorithm for deriving the optimal solution. In addition, the near-optimal solutions are derived by adapting two well-known heuristic algorithms. The computational experiments reveal that the proposed branch-and-bound algorithm can effectively deal with problems with up to 16 jobs, and the proposed heuristic algorithms can yield accurate near-optimal solutions. (C) 2012 Elsevier Ltd. All rights reserved.
引用
收藏
页码:302 / 312
页数:11
相关论文
共 37 条
[1]   Single-machine scheduling with learning considerations [J].
Biskup, D .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1999, 115 (01) :173-178
[2]   A state-of-the-art review on scheduling with learning effects [J].
Biskup, Dirk .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 188 (02) :315-329
[3]  
Brucker P., 1977, Ann. Discrete Math., V1, P343, DOI [DOI 10.1016/S0167-5060(08)70743-X, 10.1016/S0167-5060(08)70743-X]
[4]   A bi-criteria two-machine flowshop scheduling problem with a learning effect [J].
Chen, P. ;
Wu, C-C ;
Lee, W-C .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2006, 57 (09) :1113-1125
[5]   A two-agent single-machine scheduling problem with truncated sum-of-processing-times-based learning considerations [J].
Cheng, T. C. E. ;
Cheng, Shuenn-Ren ;
Wu, Wen-Hung ;
Hsu, Peng-Hsiang ;
Wu, Chin-Chia .
COMPUTERS & INDUSTRIAL ENGINEERING, 2011, 60 (04) :534-541
[6]   Single-machine scheduling with sum-of-logarithm-processing-times-based learning considerations [J].
Cheng, T. C. E. ;
Lai, Peng-Jen ;
Wu, Chin-Chia ;
Lee, Wen-Chiung .
INFORMATION SCIENCES, 2009, 179 (18) :3127-3135
[7]   Some scheduling problems with sum-of-proces sing-times-based and job-position-based learning effects [J].
Cheng, T. C. Edwin ;
Wu, Chin-Chia ;
Lee, Wen-Chiung .
INFORMATION SCIENCES, 2008, 178 (11) :2476-2487
[8]   A branch and bound algorithm to minimize the total tardiness for m-machine permutation flowshop problems [J].
Chung, Chia-Shin ;
Flynn, James ;
Kirca, Omer .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2006, 174 (01) :1-10
[9]   A branch and bound algorithm to minimize the total flow time for m-machine permutation flowshop problems [J].
Chung, CS ;
Flynn, J ;
Kirca, O .
INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2002, 79 (03) :185-196
[10]   A review and classification of heuristics for permutation flow-shop scheduling with makespan objective [J].
Framinan, JM ;
Gupta, JND ;
Leisten, R .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2004, 55 (12) :1243-1255