基于遗传变邻域混合算法的带交货期的单机车间逆调度方法

doi:10.3901/JME.2018.03.148

机械工程学报 ›› 2018, Vol. 54 ›› Issue (3): 148-159.doi: 10.3901/JME.2018.03.148

扫码分享

基于遗传变邻域混合算法的带交货期的单机车间逆调度方法

牟健慧¹, 潘全科², 牟建彩³, 徐汝峰¹, 于珊珊¹

1. 山东理工大学机械工程学院淄博 255000;
2. 华中科技大学数字制造装备与技术国家重点实验室武汉 430074;
3. 华立科技职业学院广州 510000

收稿日期:2016-12-10 修回日期:2017-08-18 出版日期:2018-02-05 发布日期:2018-02-05
通讯作者: 牟健慧(通信作者),女,1983年出生,博士研究生。主要研究方向为车间调度与优化。E-mail:mjhcr@163.com
基金资助:
国家自然科学基金（51605267）、山东省自然科学基金（ZR2016EEQ07）和山东省高等学校科技计划（J16LB04）资助项目。

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

MOU Jianhui¹, PAN Quanke², MOU Jiancai³, XU Rufeng¹, YU Shanshan¹

1. School of Mechanical Engineering, Shandong University of Technology, Zibo 255000;
2. State Key Lab of Digital Manufacturing Equipment and Technology, Huazhong University of Science & Technology, Wuhan 430074;
3. Huali Science and Technology College, Guangzhou 510000

Received:2016-12-10 Revised:2017-08-18 Online:2018-02-05 Published:2018-02-05

摘要/Abstract

摘要： 针对带交货期的单机逆调度问题，建立以最小化系统调整为目标函数的单机逆调度数学优化模型；利用互补性能，采用串行、并行和嵌入等结构，将遗传算法与变邻域搜索算法相结合，设计出遗传-变邻域搜索算法、遗传-变邻域搜索交替算法和遗传-变邻域搜索协同算法3种混合算法。为产生逆调度激发机制，采用非最优调度法，将随机初始化与局部初始化进行结合，创造逆调度环境；此外，为提高算法的局部搜索能力，基于交叉变异操作等思想来构建四种搜索邻域，通过邻域结构的切换，加强局部搜索能力；最后，将提出的混合算法用于求解不同规模的问题实例，与其他算法的求解结果进行比较，证明提出的混合算法是可行的和有效的。

关键词: 不确定加工参数, 车间调度, 混合算法, 逆调度

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

中图分类号:

TG156

牟健慧, 潘全科, 牟建彩, 徐汝峰, 于珊珊. 基于遗传变邻域混合算法的带交货期的单机车间逆调度方法[J]. 机械工程学报, 2018, 54(3): 148-159.

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.

参考文献

[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.

基于遗传变邻域混合算法的带交货期的单机车间逆调度方法

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	王彦森, 冯立杰, 王金凤, 刘鹏, 赵华东. 面向节能的复杂机械零部件生产与物流集成调度[J]. 机械工程学报, 2024, 60(20): 403-416.
[2]	王殿熙, 杨波, 成保忠, 段明宇, 高常青. 基于精英回溯-模拟退火混合算法的参数耦合变更路径优选[J]. 机械工程学报, 2024, 60(15): 316-333.
[3]	匡增彧, 谢晖, 任莹晖, 卓晓军, 刘洋, 易峦. 退役产品性能损耗分级评价的拆解车间调度节能优化研究[J]. 机械工程学报, 2024, 60(14): 396-408.
[4]	赵诗奎, 黄林, 吕杰. Job shop强化多工序联动邻域结构与近似评价研究[J]. 机械工程学报, 2023, 59(4): 318-331.
[5]	李浩然, 高亮, 李新宇. 基于离散人工蜂群算法的多目标分布式异构零等待流水车间调度方法[J]. 机械工程学报, 2023, 59(2): 291-306.
[6]	吕海利, 黄志文, 陈建华, 王正国, 吴姝, 韩国震. 基于GEP的装配作业车间调度复合派工法则研究[J]. 机械工程学报, 2023, 59(16): 427-434.
[7]	黄林, 赵诗奎, 黄森. 基于障碍图模型和禁忌搜索混合算法求解作业车间调度问题[J]. 机械工程学报, 2023, 59(16): 435-444,426.
[8]	牟健慧, 段培永, 高亮, 彭武良, 丛建臣. 基于混合遗传算法求解分布式流水车间逆调度问题[J]. 机械工程学报, 2022, 58(6): 295-308.
[9]	吕海利, 朱家涛, 王正国, 吴姝. 装配作业车间的JIT调度研究[J]. 机械工程学报, 2021, 57(5): 157-165.
[10]	赵诗奎. Job Shop基于无延迟调度路径重连与回溯禁忌搜索算法研究[J]. 机械工程学报, 2021, 57(14): 291-303.
[11]	赵诗奎. 作业车间调度问题的多工序联动邻域结构研究[J]. 机械工程学报, 2020, 56(13): 192-206.
[12]	石小秋, 李炎炎, 邓丁山, 龙伟. 基于自适应变级遗传杂草算法的FJSP研究[J]. 机械工程学报, 2019, 55(6): 223-232.
[13]	孙在省, 钱斌, 胡蓉, 张梓琪, 张长胜. 基于块结构性质的花粉算法求解可重入作业车间调度问题[J]. 机械工程学报, 2019, 55(16): 220-232.
[14]	周亚勤, 杨长祺, 吕佑龙, 金永乔, 张洁. 双资源约束的航天结构件车间生产调度方法[J]. 机械工程学报, 2018, 54(9): 55-63.
[15]	李聪波, 沈欢, 李玲玲, 易茜. 面向能耗的多工艺路线柔性作业车间分批优化调度模型^*[J]. 机械工程学报, 2017, 53(5): 12-23.