Research on Single-machine Inverse Scheduling Methods with Due-dates Based on Variable Neighborhood Search Hybrid Algorithm

doi:10.3901/JME.2018.03.148

Abstract

Abstract: Aiming at the single-machine inverse scheduling problem with due-dates(SISPD), a mathematical model with the minimal adjustment of system as a target is constructed. Using complementary properties, three hybrid algorithms combining genetic algorithm with variable neighborhood search algorithm are proposed by using serial, parallel and embedded structure. In the algorithm, a double scheduling method which combines heuristic non-optimal scheduling method with random initial population and local initial population is designed to construct inverse scheduling mechanism. Then, based on the features of problem and encoding, four neighborhood structures are put forward to improve the local search ability by changing the neighborhood structure. Finally, the proposed algorithms are used to solve numerical instances. The computational results show that the proposed method could solve SISPD effectively.

Key words: hybrid algorithm, inverse scheduling, shop scheduling, uncertain processing parameter

CLC Number:

TG156

MOU Jianhui, PAN Quanke, MOU Jiancai, XU Rufeng, YU Shanshan. Research on Single-machine Inverse Scheduling Methods with Due-dates Based on Variable Neighborhood Search Hybrid Algorithm[J]. Journal of Mechanical Engineering, 2018, 54(3): 148-159.

References

[1] NGUYEN S,ZHANG M,JOHNSTON M,et al. Automatic design of scheduling policies for dynamic multi-objective job shop scheduling via cooperative coevolution genetic programming[J]. Evolutionary Computation,IEEE Transactions on,2014,18(2):193-208.
[2] XU Y,WANG L,WANG S,et al. An effective teaching–learning-based optimization algorithm for the flexible job-shop scheduling problem with fuzzy processing time[J]. Neurocomputing,2015,148:260-268.
[3] HE T,LIU F,MA Y,et al. Study on shop-floor scheduling[J]. Journal of Mechanical Engineering,2000,36(5):97-102.
[4] TANG,D B. Energy-efficient approach to minimizing the energy consumption in an extended job-shop scheduling problem[J]. Chinese Journal of Mechanical Engineering,2015,28(5):1048-1055.
[5] GAO K Z,SUGANTHAN P N,TASGETIREN M F,et al. Effective ensembles of heuristics for scheduling flexible job shop problem with new job insertion[J]. Computers & Industrial Engineering,2015,90:107-117.
[6] BRUCKER P,SHAKHLEVICH N V. Inverse scheduling with maximum lateness objective. Journal of Scheduling,2009,12(5):475-488.
[7] BRUCKER P,SHAKHLEVICH N V. Inverse scheduling:two-machine flow-shop problem[J]. J. Sched.,2011,14(3):239-256.
[8] KOULAMAS C. Inverse scheduling with controllable job parameters[J]. International Journal of Services and Operations Management,2005,1(1):35-43.
[9] ZHANG FENG,NG T C,TANG G C. Inverse scheduling:Applications in shipping[J]. International Journal of Shipping and Transport Logistics,2011,3(3):312-322.
[10] 陈荣军,陈峰,唐国春. 单台机器总完工时间排序问题的反问题[J]. 上海第二工业大学学报,2005,22(2):1-7. CHEN Rongjun,CHEN Feng,TANG Guochun. Inverse problems of a single machine scheduling to minimize the total completion time[J]. J. Shanghai Second Polytechnic University,2005,22(2):1-7.
[11] 陈荣军. 单台机器总完工时间随机排序问题的反问题[J]. 常州工学院学报,2006,19(6):1-5. CHEN Rongjun. Inverse scheduling problem on a single machine stochastic scheduling to minimize the total completion time[J]. Journal of Changzhou of technology,2006,19(6):1-5.
[12] 陈荣军,唐国春. 单机供应链排序及流水作业的反问题模型[J]. 运筹与管理,2009,18(2):80-84. Chen Rongjun,Tang Guochun. Inverse problems of supply chain scheduling and flowshop scheduling[J]. Operations research and management science,2009,18(2):80-84.
[13] Pham Hongtruong,鲁习文. 平行机上单位加工时间加权总完工时间排序问题的反问题[J]. 华东理工大学学报,2012,38(6):757-761. Pham Hongtruong,Lu Xiwen. Inverse problem of total weighted completion time objective with unit processing time on identical parallel machines[J]. Journal of East China University of Science and Technology,2012,38(6):757-761.
[14] VERELA R,VELA C R,PUENTE J. GOMEZ A. A knowledge-based evolutionary strategy for scheduling problems with bottlenecks[J]. European Journal of Operational Research,2003,145:57-71.
[15] SHAPIRO J F. A survey of Lagrangian techniques for discrete optimization[J]. Annals of Discrete Mathematics,1979,5:113-138.
[16] HANSEN P,MLADENOVIC N. Variable neighborhood search[M]. New York:Springer,2014.
[17] XIA W,WU Z,ZhANG W,et al. Applying particle swarm optimization to job-shop scheduling problem[J]. Chinese Journal of Mechanical Engineering,2004,17(3):437-441.
[18] 潘全科,王文宏,朱剑英,等. 基于粒子群优化和变邻域搜索的混合调度算法[J]. 计算机集成制造系统,2007,13(2):323-328. PAN Quanke,WANG Wenhong,ZHU Jianying,et al. Hybrid heuristics based on particle swarm optimization and variable neighborhood search for job shop scheduling. Computer integrated manufacturing system,2007,13(2):323-328.
[19] RANTALANKILA P,KANNALS J,RAHTU E. Generating object segmentation proposals using global and local search[C]// Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2014:2417-2424.
[20] MOU J H,GAO L,LI X Y,et al. Optimization of the reverse scheduling problem by a modified genetic algorithm. International Journal of Production Research,2015,53(23):6980-6993.
[21] MOU J H,LI X Y,GAO L,et al. An improved genetic algorithm for single-machine inverse scheduling problem[J]. Mathematical Problems in Engineering,2014,2014(4):1-14.
[22] MOU J H,GAO L,LI X Y,et al. An effective L-MONG for solving multiobjective flow shop inverse scheduling problems[J]. Journal of Intelligent Manufacturing,2015:1-19.
[23] 王松. 基于遗传算法的单机逆调度方法研究[D]. 武汉:华中科技大学,2014. WANG Song. Research on the solution method of single machine inverse scheduling based on genetic algorithm[D]. Wuhan:Huazhong University of Science and Technology,2014
[24] 牟健慧,郭前建,高亮,等. 基于混合的多目标遗传算法的多目标流水车间逆调度问题求解方法[J]. 机械工程学报,2016,52(22):186-197. MU Jianhui,GUO Qianjian,GAO Liang et al. Hybrid HMGA algorithm for solving multi-objective flow-shop inverse scheduling problems[J]. Journal of Mechanical Engineering,2016,52(22):186-197.