期刊
COMPUTERS & INDUSTRIAL ENGINEERING
卷 130, 期 -, 页码 198-221出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cie.2019.02.015
关键词
Outsourcing; Rescheduling; Two-machine flow shop; Variable neighborhood search
资金
- Natural Science Foundation of China (NSFC) [71501083]
- Youth Fund for Humanities and Social Sciences of Ministry of Education of China [14YJCZH098]
- Promotive Research Foundation for Outstanding Young and Middle-aged Scientists of Shandong Province in China [BS2015ZZ002]
This paper addresses the two-machine flow shop outsourcing and rescheduling problem (TFSORP) in response to an unexpected arrival of new jobs, in which each job can be processed in the in-house shop or outsourced to a single subcontractor. An efficient schedule is constructed for the in-house jobs, and its performance is measured by the makespan. Each of the outsourced jobs requires paying an outsourcing cost. The objective is to minimize the sum of the in-house makespan and total outsourcing cost, subject to a limit on the number of original jobs processed by the subcontractor after disruption. To solve this NP-hard problem, a mixed integer programming formulation and helpful optimization properties are first established, and then a hybrid variable neighborhood search algorithm (HVNS) that incorporates one-dimensional array representation and three problem-specific neighborhood structures is developed. At the initialization stage, either of two well-designed constructive heuristics, i.e., job addition heuristic (JAH) and job removal heuristic (JRH) is employed. At the iterative search stage, an adaptive best-improvement procedure based on three neighborhood structures is devised to play the role of local search. An extensive experimental calibration for main factors in HVNS is carried out by a full factorial design of experiments. To validate the calibrated HVNS, computational experiments are conducted upon the test suite of various instances. As demonstrated in the results, the calibrated HVNS gains the advantage over both the commercial optimizer and exhaustive approach in terms of computation time for small-sized instances, while it also outperforms an existing meta-heuristic algorithm and two canonical ones (based on the principles of genetic algorithm and simulated annealing) in the optimizing capability.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据