期刊
INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS
卷 186, 期 -, 页码 1-7出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ijpe.2017.01.014
关键词
Scheduling; Maintenance; Periodic recycle; Makespan; Heuristic algorithm
资金
- National Natural Science Foundation of China [71372019, 71471057, 71102174]
- Beijing Higher Education Young Elite Teacher Project [YETP1173]
- Beijing Philosophy and Social Science Foundation of China [11JGC106]
Parallel machine structure is very common in modern production systems. Its performance sometimes has a decisive impact on the whole productivity. In this paper, we consider a parallel-machine scheduling problem where each machine is subject to periodic maintenance. Instead of assuming all the machines have the same maintenance periodic cycle, we assume the maintenance periodic cycles are machine-dependent. The objective is to schedule all the jobs to the machines such that the makespan is minimized. We first provide computational complexity and non-approximability analyses of the problem and then present two mathematical programming models to tackle small-sized instances. Thereafter, we present a worst-case analysis of the classical LPT and LS algorithms for the problem. Then we propose two improved heuristic algorithms based on some observations of large-sized instances. In order to evaluate the performance of the heuristic algorithms, we resort to a lower bound of the optimal makespan, and find that it has a very interesting characteristic. Numerical experiments show that the improved heuristic algorithm MLPT improves the objective value of the LPT schedirle by about 6.75% on average and that the MLPT heuristic algorithm has an average-case relative error less than 1.57% for all combinations of instances, which means that it is very suitable for real world applications.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据