期刊
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY
卷 56, 期 9-12, 页码 1139-1145出版社
SPRINGER LONDON LTD
DOI: 10.1007/s00170-011-3249-y
关键词
Scheduling; Maintenance; Heuristic algorithm; Worst-case analysis; Average-case analysis
资金
- Natural Science Foundation of Jiangxi [2010GQS0003]
- Science Foundation of Education Committee of Jiangxi [GJJ11143, GJJ11144]
- Doctor Foundation of East China Institute of Technology
This paper addresses a single-machine scheduling problem with nonresumable jobs and flexible maintenance activities (SJM) and its online version SJMO. It is showed that the competitive ratio of the classical list scheduling (LS) algorithm is 2 for SJMO, and it is the best possible polynomial time approximation algorithm for SJMO from both the competitive ratio point of view unless P = NP and the computational time complexity point of view. Based on the relationship between SJM and SJMO, it is showed that the LS algorithm is the best possible polynomial time approximation algorithm for SJM from both the worst-case ratio point of view unless P = NP and the computational time complexity point of view, which is a significant improvement of some of the existing results on SJM and its special case in the literature. Note that the worst-case ratio of the classical longest processing time first (LPT) algorithm is also 2 for SJM. In order to show which algorithm is better for SJM on average, numerical experiments are conducted. Computational results show that the LPT algorithm performs better than the LS algorithm in all combinations from an average-case error point of view.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据