文献类型：期刊文献

英文题名：Single-machine scheduling problems with machine aging effect and an optional maintenance activity

作者：Gu, Manzhan[1,5];Lu, Xiwen[2];Gu, Jinwei[3,6];Zhang, Ying[4]

机构：[1]Shanghai Univ Finance & Econ, Sch Math, Shanghai 200433, Peoples R China;[2]East China Univ Sci & Technol, Dept Math, Shanghai 200237, Peoples R China;[3]Shanghai Univ Elect Power, Coll Econ & Management, Shanghai 200090, Peoples R China;[4]Georgia Inst Technol, Sch Elect & Comp Engn, Atlanta, GA 30332 USA;[5]Shandong Univ, Sch Math & Stat, Weihai 264209, Shandong, Peoples R China;[6]Shandong Univ, Sch Mech Elect & Informat Engn, Weihai 264209, Shandong, Peoples R China

年份：2016

卷号：40

期号：21-22

起止页码：8862

外文期刊名：APPLIED MATHEMATICAL MODELLING

收录：;EI(收录号：20160902036609);WOS:【SCI-EXPANDED(收录号:WOS:000384853900002)】；

基金：This work is supported by National Natural Science Foundation of China (Grant no. 11201282 and 61304209), Humanity and Social Science Youth Foundation of Ministry of Education (Grant no. 10YJCZH032), Innovation Program of Shanghai Municipal Education Commission (Grant no. 14YZ127).

语种：英文

外文关键词：Aging effect; Maintenance; Makespan; Total completion times

摘要：This paper considers two single-machine scheduling problems with a new type of aging effect, which is dominated by the processing speed of the machine. During the whole scheduling horizon, the machine is subject to an optional maintenance, and the duration of the maintenance depends on the length of the uptime before it. The objective is to schedule all jobs and find the location of the maintenance so as to minimize the makespan or the total completion times. The two problems are proved to be NP-complete, and two dynamic programming algorithms are proposed to solve the problems. We analyze the computation complexity of the algorithms, and show that the problems under study are solvable in polynomial time if the processing loads of all jobs are uniformly bounded. (C) 2016 Elsevier Inc. All rights reserved.