Single-machine scheduling with deteriorating jobs and aging effects under an optional maintenance activity consideration

被引:21
作者
Ji, Min [1 ]
Hsu, Chou-Jung [2 ]
Yang, Dar-Li [3 ]
机构
[1] Zhejiang Gongshang Univ, Sch Comp Sci & Informat Engn, Contemporary Business & Trade Res Ctr, Hangzhou 310018, Peoples R China
[2] Nan Kai Univ Technol, Dept Ind Engn & Management, Nan Tou 542, Taiwan
[3] Natl Formosa Univ, Dept Informat Management, Yunlin 632, Taiwan
基金
中国国家自然科学基金;
关键词
Scheduling; Deteriorating jobs; Aging effect; Makespan; FPTAS; PROCESSING TIMES; MAKESPAN; COMPLEXITY; FPTAS;
D O I
10.1007/s10878-011-9415-1
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
This article studies a single-machine scheduling with deteriorating jobs and aging effects under an optional maintenance activity. We assume that after maintenance activity, the machine will revert to its initial condition and the aging effects will start anew. Moreover, due to the restriction of budget of maintenance, the limitation of the maintenance frequency on the machine is assumed to be known in advance. The optional maintenance activity of this study means that the starting time of the maintenance activity is unknown in advance. It can be scheduled immediately after the processing of any job that has been completed. Therefore, the planner must to make decision on whether or when to schedule the maintenance activity during the scheduling horizon to optimal the performance measures. The objective is to minimize the makespan. We first show that the addressed problem is NP-hard in the strong sense. Then a fully polynomial-time approximation scheme (FPTAS) for the proposed problem is presented.
引用
收藏
页码:437 / 447
页数:11
相关论文
共 40 条
[1]  
Alidaee B, 1999, J OPER RES SOC, V50, P711, DOI 10.2307/3010325
[2]   Single-machine scheduling with learning considerations [J].
Biskup, D .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1999, 115 (01) :173-178
[3]   A state-of-the-art review on scheduling with learning effects [J].
Biskup, Dirk .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 188 (02) :315-329
[4]   SCHEDULING DETERIORATING JOBS ON A SINGLE PROCESSOR [J].
BROWNE, S ;
YECHIALI, U .
OPERATIONS RESEARCH, 1990, 38 (03) :495-498
[5]   Some scheduling problems with deteriorating jobs and learning effects [J].
Cheng, T. C. E. ;
Wu, Chin-Chia ;
Lee, Wen-Chiung .
COMPUTERS & INDUSTRIAL ENGINEERING, 2008, 54 (04) :972-982
[6]   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
[7]  
Cheng TCE, 2010, COMPUT OPER RES, V38, P1760, DOI [10.1016/j.cor.2010.11.014, DOI 10.1016/J.C0R.2010.11.014]
[8]   Scheduling resumable deteriorating jobs on a single machine with non-availability constraints [J].
Fan, Baoqiang ;
Li, Shisheng ;
Zhou, Li ;
Zhang, Liqi .
THEORETICAL COMPUTER SCIENCE, 2011, 412 (4-5) :275-280
[10]   Complexity and approximability of scheduling resumable proportionally deteriorating jobs [J].
Gawiejnowicz, Stanislaw ;
Kononov, Alexander .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 200 (01) :305-308