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

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

Abstract

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

CLC Number:

F406

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.

References

[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]	TANG Hongtao, YANG Zhipeng, LIU Jiayi. A Research on Batch Scheduling with Non-identical Job Sizes Considering Parallel Processes [J]. Industrial Engineering Journal, 2021, 24(3): 68-76,114.
[2]	CAO Zhenyu, JIANG Yangsheng, LUO Xiaoling, YANG Jie, ZHANG Yao. A Direct Optimization in Urban Transit Network for Small and Medium-sized Cities [J]. Industrial Engineering Journal, 2020, 23(6): 117-123.
[3]	ZHU Xiang, XIANG Yanping. An Optimization of Multi-Freights Loading into Multi-Cars with Balancing Constraints [J]. Industrial Engineering Journal, 2020, 23(3): 123-131.
[4]	ZHANG Guochen, SUN Chaoli, SHI Hui, LI Xiaobo. A Ready-mixed Concrete Vehicle Scheduling with Vehicle Daily Inspection [J]. Industrial Engineering Journal, 2020, 23(2): 67-75.
[5]	JIANG Hai, CHEN Feng. A Study of Vehicle Routing Problem for Urban Transport of Express [J]. Industrial Engineering Journal , 2019, 22(4): 58-63.
[6]	CHEN Xuanrui, CHEN Qingxin, MAO Ning. A Research on Order Batching Problem of Panel Furniture Enterprises [J]. Industrial Engineering Journal , 2019, 22(2): 96-102.
[7]	YI Yali. A Research on Multi-Project Human Resource Scheduling in R & D Enterprises——A Hyper-Heuristic Algorithm Based on Ant Colony Optimization [J]. Industrial Engineering Journal , 2018, 21(4): 104-109.
[8]	ZHOU Na, SHU Fan, JIN Peiqing. Facility Mixed Layout Problems (FMLP) based on Hybrid Heuristic Algorithms [J]. Industrial Engineering Journal , 2017, 20(1): 77-82.
[9]	LAN Haiyan . Research Progress and Trend of Production inventory in Multi-level Supply Chain Based on the Solving Method for Optimization Model [J]. Industrial Engineering Journal , 2016, 19(6): 9-16.
[10]	JIANG Aiping， XIA Hao, GAO Junjun, CHI Qiuguo,WU Siyu. Optimal Order Quantity of Electric Power Materials with Compound Poisson Demand Distribution [J]. Industrial Engineering Journal , 2016, 19(3): 90-95.
[11]	He Meng-ying, Xu Mei, Zhang Ning-bo, Yan Fu. An Analysis of Passenger Car Transportation Problems Based on Heuristic Algorithm [J]. Industrial Engineering Journal , 2015, 18(5): 141-147.
[12]	Li Bai-lin, Yu Au-lin, Mao Ning, Chen Qing-xin. Optimization of the Assembly Line Subject to Workers with Different Skills [J]. Industrial Engineering Journal , 2015, 18(3): 113-118.
[13]	Wu Ming-hong1,Zhang Feng-li2,Dong Guang-jing2，Wang Bai-lin2. Optimization Algorithm for Batch Planning with the Information of Billet Inventory [J]. Industrial Engineering Journal , 2015, 18(1): 42-47.
[14]	Zhang Lian-ying1, Li Yan-wei1,2, Sun Ruo-xin1. A Fuzzy Resource Constrained MultiProject Schedule Based on Priority Rule [J]. Industrial Engineering Journal , 2014, 17(3): 13-17.
[15]	Hu Chang-wei，Chen Xin-du，Chen Qing-xin，Mao Ning，Chen Xin. Optimization for Scheduling Identical Parallel Melting Furnaces withNon-identical Job Weights [J]. Industrial Engineering Journal , 2014, 17(3): 73-78.