Single-machine scheduling with learning effect and deteriorating jobs

被引:24
作者
Wang, Ji-Bo [1 ]
机构
[1] Shenyang Inst Aeronaut Engn, Sch Sci, Operat Res & Cybernet Inst, Shenyang 110136, Peoples R China
关键词
Scheduling; Single machine; Learning effect; Deteriorating jobs; DEPENDENT PROCESSING TIMES; LINEAR DETERIORATION; SETUP TIMES; COMPLETION-TIME; COMPLEXITY; MAKESPAN; MINIMIZE; CURVES;
D O I
10.1016/j.cie.2009.07.015
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
In this paper we consider the single-machine scheduling problems with the effects of learning and deterioration. By the effects of learning and deterioration, we mean that job processing times are defined by functions of their starting times and positions in the sequence. It is shown that even with the introduction of learning effect and deteriorating jobs to job processing times, single machine makespan and sum of completion times (square) minimization problems remain polynomially solvable, respectively. But for the following objective functions: the weighted sum of completion times and the maximum lateness, this paper proves that the WSPT rule and the EDD rule can construct the optimal sequence under some special cases, respectively. (C) 2009 Elsevier Ltd. All rights reserved.
引用
收藏
页码:1452 / 1456
页数:5
相关论文
共 48 条
[1]  
Alidaee B, 1999, J OPER RES SOC, V50, P711, DOI 10.2307/3010325
[2]  
[Anonymous], 2004, Int. J. Bus. Econom.
[3]   Minimizing maximum lateness under linear deterioration [J].
Bachman, A ;
Janiak, A .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 126 (03) :557-566
[4]   Scheduling jobs with position-dependent processing times [J].
Bachman, A ;
Janiak, A .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2004, 55 (03) :257-264
[5]   Minimizing the total weighted completion time of deteriorating jobs [J].
Bachman, A ;
Janiak, A ;
Kovalyov, MY .
INFORMATION PROCESSING LETTERS, 2002, 81 (02) :81-84
[6]   COMPUTATIONAL SURVEY OF UNIVARIATE AND MULTIVARIATE LEARNING-CURVE MODELS [J].
BADIRU, AB .
IEEE TRANSACTIONS ON ENGINEERING MANAGEMENT, 1992, 39 (02) :176-188
[7]   Common due date scheduling with autonomous and induced learning [J].
Biskup, D ;
Simons, D .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2004, 159 (03) :606-616
[8]   Single-machine scheduling with learning considerations [J].
Biskup, D .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1999, 115 (01) :173-178
[9]   A state-of-the-art review on scheduling with learning effects [J].
Biskup, Dirk .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 188 (02) :315-329
[10]   SCHEDULING DETERIORATING JOBS ON A SINGLE PROCESSOR [J].
BROWNE, S ;
YECHIALI, U .
OPERATIONS RESEARCH, 1990, 38 (03) :495-498