期刊
COMPUTERS & OPERATIONS RESEARCH
卷 90, 期 -, 页码 264-274出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2017.02.011
关键词
Parallel machine scheduling; Makespan; Job splitting; Learning effect; Vital-few law; Worst-case analysis
类别
资金
- National Natural Science Foundation of China [71371106, 71472108]
- National Natural Science of China [71332005]
- Ministry of Science and Technology of the People's Republic of China [2014IM010100]
- Shenzhen Municipal Science and Technology Innovation Committee [JCYJ20160531195231085]
This research, which is motivated by real cases in labor-intensive industries where learning effects and the vital-few law take place, integrates learning and job splitting in parallel machine scheduling problems to minimize the makespan. We propose the lower bound of the problem and a job-splitting algorithm corresponding to the lower bound. Subsequently, a heuristic called SLMR is proposed based on the job splitting algorithm with a proven worst case ratio. Furthermore, a branch-and-bound algorithm, which can obtain optimal solutions for very small problems, and a hybrid differential evolution algorithm are proposed, which can not only solve the problem, but also serve as a benchmark to evaluate the solution quality of the heuristic SLMR. The performance of the heuristic on a large number of randomly generated instances is evaluated. Results show that the proposed heuristic has good solution quality and calculation efficiency. (C) 2017 Published by Elsevier Ltd.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据