加工时间存在双重约束的批调度模型及算法

doi:10.3969/j.issn.1007-7375.e16-3303

工业工程 ›› 2017, Vol. 20 ›› Issue (2): 78-85.doi: 10.3969/j.issn.1007-7375.e16-3303

加工时间存在双重约束的批调度模型及算法

黄锦钿¹, 黄伟², 郑耿灶³

1. 揭阳职业技术学院机电工程系, 广东揭阳 522000;
2. 揭阳市光丰钢业有限公司, 广东揭阳 522000;
3. 广东省特种设备检测研究院江门检测院, 广东江门 529000

收稿日期:2016-12-01 出版日期:2017-04-30 发布日期:2017-05-13
作者简介:黄锦钿(1983-),男,广东省人,讲师,博士,主要研究方向为生产计划与控制、CIMS关键技术等.
基金资助:
揭阳市科技计划资助项目（2015B01026）

Model and Algorithm for Batch Scheduling with Double Constrains of Processing Time

HUANG Jindian¹, HUANG Wei², ZHENG Gengzao³

1. Department of Mechanical and Electrical Engineering, Jieyang Vocational & Technical College, Jieyang 522000, China;
2. Jieyang Guangfeng Steel Industry, Jieyang 522000, China;
3. Special Equipment Inspection and Research Institute of Guangdong Province, Jiangmen 529000, China

Received:2016-12-01 Online:2017-04-30 Published:2017-05-13

摘要/Abstract

摘要： 为了提高热处理的加工效率并实现准时交货，本文根据热处理各批次加工时间受装炉量和批中最大工件尺寸双重约束的特点，分别以最小化最大完成时间和最小化最大拖期量为调度目标，构建混合整数线性规划模型Model C和Model L。根据分批数量上界设定值与Model C运算结果的关系特性，构建启发式算法HC提高Model C的运算效率。通过反例说明Model C所具有的特性并不适用于求解Model L。提出启发式算法HL求解最小化最大拖期量问题，并证明算法HL的计算复杂度。通过大量实验数据验证，结果显示两个数学模型都分别能够求得最优解，但调度规模不超过18个工件；算法HC能得到调度规模为60个工件的最优解；算法HL与最优解相比平均偏差不超过15%，调度性能明显优于其他2种典型算法。

关键词: 批调度, 热处理, 数学模型, 启发式算法

Abstract: In order to improve the efficiency of heat-treatment and to effect on-time delivery, considering the heat-treatment batch processing time constrained by double factors, the amount of stove and the maximum job size of the batch with two objectives of minimizing makespan and minimizing maximum lateness, two mixed integer linear programming models are developed, respectively called Model C and Model L. According to the relational feature between the calculation result of Model C and the setting value of the batch number upper bound, the heuristic HC is developed to improve the efficiency of Model C. A counter-example shows that the feature of Model C does not apply to solving Model L. The heuristic HL is developed for minimizing maximum lateness. An extensive simulation study is conducted. The results show that the two mathematical models are able to obtain the optimal solution, but not more than 18 jobs. The algorithm HC can get the optimal solution of 60 jobs. Compared with the optimal solution, the average deviation of the algorithm HL is not more than 15%, and the scheduling performance is better than the other two typical algorithms.

Key words: batch scheduling, heat-treatment, mathematical model, heuristic

中图分类号:

F406

黄锦钿, 黄伟, 郑耿灶. 加工时间存在双重约束的批调度模型及算法[J]. 工业工程, 2017, 20(2): 78-85.

HUANG Jindian, HUANG Wei, ZHENG Gengzao. Model and Algorithm for Batch Scheduling with Double Constrains of Processing Time[J]. Industrial Engineering Journal , 2017, 20(2): 78-85.

参考文献

[1] LIU Jianjun, CHEN Qingxin, MAO Ning, et al. Bi-objective dynamic control of batch processor with non-identical jobs in mould manufacturing [J]. International Journal of Production Research, 2013, 51(6): 1820-1835.
[2] 刘建军, 陈庆新, 毛宁. 基于滚动调度的模具热处理车间负荷控制算法[J]. 机械工程学报, 2010, 46(20): 125-133. LIU Jianjun, CHEN Qingxin, MAO Ning. Rolling-scheduling-based workload control for mould heat-treatment shop floor [J]. Jourrnal of Mechanical Engineering, 2010, 46(20): 125-133.
[3] HUANG J, LIU J, CHEN Q, et al. Minimizing makespan in a flow shop with two batch machines[C]//Proceedings of the 22nd International Conference on Industrial Engineering and Engineering Management 2015, Atlantis Press, 2016: 283-292.
[4] 黄锦钿, 刘建军, 陈庆新, 等. 两机flow-shop类型模具热处理车间批调度算法[J]. 计算机集成制造系统, 2014, 20(7): 1665-1674. HUANG Jindian, LIU Jianjun, CHEN Qingxin, et al. Batch optimization algorithm for mould heat-treatment flow-shop with two machines [J]. Computer Integrated Manufacturing Systems, 2014, 20(7): 1665-1674.
[5] 刘建军, 陈庆新, 毛宁, 等. 事件驱动的并行多机模具热处理生产调度[J]. 计算机集成制造系统, 2015, 21(4): 1013-1022. LIU Jianjun, CHEN Qingxin, Mao Ning, et al. Event-driven mould heat-treatment production scheduling with parallel batch processors [J]. Computer Integrated Manufacturing Systems, 2015, 21(4): 1013-1022.
[6] 林刚, 刘建军, 陈庆新, 等. 可重入流水车间类型模具热处理生产动态批调度[J]. 计算机集成制造系统, 2016, 22(4): 1046-1058. LIN Gang, LIU Jianjun, CHEN Qingxin, et al. Dynamic batch scheduling for re-entrant mould heat-treatment flow-shop [J]. Computer Integrated Manufacturing Systems, 2016, 22(4): 1046-1058.
[7] 包耳, 田绍洁, 王华琪. 热处理加热保温时间的 369 法则[J]. 热处理技术与装备, 2008, 29(2): 53-55. BAO Er, TIAN Shaojie, WANG Huaqi. The formula 369 of heating and heat preservation about heat treatment [J]. Heat Treatment Technology and Equipment, 2008, 29(2): 53-55.
[8] MELOUK S, DAMODARAN P, CHANG P Y. Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing[J]. International Journal of Production Economics, 2004, 87(2): 141-147.
[9] LIAO Chingjong, LIAO Liman, Improved MILP models for two-machine flowshop with batch processing machines[J]. Mathematical and Computer Modelling, 2008, 48(7): 1254-1264.
[10] CABO M, POSSANI E, POTTS C N, et al. Split-merge: using exponential neighborhood search for scheduling a batching machine[J]. Computers & Operations Research, 2015, 63(4): 125-135.
[11] HADDAD H, GHANBARI P, MOGHADDAM A. A new mathematical model for single machine batch scheduling problem for minimizing maximum lateness with deteriorating jobs[J]. International Journal of Industrial Engineering Computations, 2012, 3(2): 253-264.
[12] TANG L, LIU P. Minimizing makespan in a two-machine flowshop scheduling with batching and release time [J]. Mathematical and Computer Modelling, 2009: 49(5): 1071-1077.
[13] PEI J, LIU X, FAN W, et al. Minimizing the makespan for a serial-batching scheduling problem with arbitrary machine breakdown and dynamic job arrival[J]. The International Journal of Advanced Manufacturing Technology, 2016, 86(9): 1-17.
[14] LU L, ZHANG L, WAN L. Integrated production and delivery scheduling on a serial batch machine to minimize the makespan[J]. Theoretical Computer Science, 2015, 572(3): 50-57.

[1]	唐红涛, 杨志鹏, 刘家毅. 考虑工序并行的差异工件批调度研究[J]. 工业工程, 2021, 24(3): 68-76,114.
[2]	曹振宇, 蒋阳升, 罗孝羚, 杨洁, 张姚. 中小城市直达公交网络优化[J]. 工业工程, 2020, 23(6): 117-123.
[3]	曾垂飞, 刘建军, 陈庆新, 毛宁. 装配作业车间分批调度问题的算法对比[J]. 工业工程, 2020, 23(4): 174-182.
[4]	朱向, 向延平. 多车多件货物平衡装载优化研究[J]. 工业工程, 2020, 23(3): 123-131.
[5]	曾垂飞, 刘建军, 陈庆新, 毛宁. 优化交货可靠性的装配作业车间分批调度[J]. 工业工程, 2019, 22(6): 45-56.
[6]	江海, 陈峰. 面向快递同城运输的车辆路径问题研究[J]. 工业工程, 2019, 22(4): 58-63.
[7]	陈炫锐, 陈庆新, 毛宁. 板式家具企业的订单组批问题研究[J]. 工业工程, 2019, 22(2): 96-102.
[8]	伊雅丽. 研发型企业多项目人力资源调度研究——基于蚁群优化的超启发式算法[J]. 工业工程, 2018, 21(4): 104-109.
[9]	周娜, 舒帆, 金佩卿. 基于混合启发式算法的设备混合布局问题[J]. 工业工程, 2017, 20(1): 77-82.
[10]	蓝海燕. 基于优化模型求解方法的多级供应链生产-库存研究进展与趋势[J]. 工业工程, 2016, 19(6): 9-16.
[11]	何梦莹, 徐梅, 张宁波, 晏福. 基于启发式算法的乘用车物流运输问题分析[J]. 工业工程, 2015, 18(5): 141-147.
[12]	李柏林，俞爱林，毛宁，陈庆新. 考虑人员能力差异的装配生产线优化[J]. 工业工程, 2015, 18(3): 113-118.
[13]	吴明宏1, 张丰丽2, 董广静2, 王柏琳2. 考虑库存信息的钢管批量计划优化算法[J]. 工业工程, 2015, 18(1): 42-47.
[14]	张连营1, 李彦伟1,2, 孙若昕1. 基于优先规则的模糊资源受限多项目调度[J]. 工业工程, 2014, 17(3): 13-17.
[15]	胡常伟，陈新度，陈庆新，毛宁，陈新. 含不一致任务重量的同型熔炼炉批调度优化[J]. 工业工程, 2014, 17(3): 73-78.

加工时间存在双重约束的批调度模型及算法

Model and Algorithm for Batch Scheduling with Double Constrains of Processing Time

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价