A Research on Batch Scheduling with Non-identical Job Sizes Considering Parallel Processes

doi:10.3969/j.issn.1007-7375.2021.03.009

Abstract

Abstract: Considering that the batch process is multi-constrained with non-identical job sizes in foundry enterprises, a parallel process batch scheduling model is constructed, with the maximum makespan and sandbox vacancy rate as the optimization objective on the premise that the job can be parallel, an improved harmony search algorithm designed to solve the scheduling model, and a single process code method and two machine allocation rules proposed to solve the problems of batch division, sandbox selection, process allocation and machine selection. In the algorithm, a new harmony generation method is proposed. At the same time, the simulated annealing algorithm is added to make it jump out of the local optimal solution and tend to the global optimal solution. Finally, a simulation experiment is carried out based on the actual production data of the enterprise to prove the effectiveness of the proposed model.

Key words: process parallel, batch scheduling, multi-constrained, harmony search algorithm

CLC Number:

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.

References

[1] DAMODARAN P, DIYADAWAGAMAGE D A, GHRAYEB O, et al. A particle swarm optimization algorithm for minimizing makespan of nonidentical parallel batch processing machines[J]. International Journal of Advanced Manufacturing Technology, 2012, 58(9-12): 1131-1140
[2] 包博, 李体方, 张搏. 基于遗传算法的装备维修作业车间并行调度模型[J]. 装甲兵工程学院学报, 2017, 31(6): 34-38
BAO Bo, LI Tifang, ZHANG Bo. Equipment maintenance job shop parallel scheduling model based on genetic algorithm[J]. Journal of Academy of Armored Force Engineering, 2017, 31(6): 34-38
[3] IKURA Y, GIMPLE M. Efficient scheduling algorithms for a single batch processing machine[J]. Operations Research Letters, 1986, 5(2): 61-65
[4] STAWOWY A, DUDA J. Coordinated production planning and scheduling problem in a foundry[J]. Archives of Foundry Engineering, 2017, 17(3): 133-138
[5] 胡常伟, 陈新度, 陈庆新, 等. 含不一致任务重量的同型熔炼炉批调度优化[J]. 工业工程, 2014, 17(3): 73-78, 85
HU Changwei, CHEN Xindu, CHEN Qingxin, et al. Optimization for scheduling identical parallel melting furnaces with non-identical job weights[J]. Industrial Engineering Journal, 2014, 17(3): 73-78, 85
[6] 刘晓平, 徐本柱, 彭军, 等. 工件工序可并行的作业车间调度模型与求解[J]. 计算机辅助设计与图形学学报, 2012, 24(1): 120-127
LIU Xiaoping, XU Benzhu, PENG Jun, et al. Model and solution of job-shop scheduling for parallel processes[J]. Journal of Computer-Aided Design & Computer Graphics, 2012, 24(1): 120-127
[7] 黄锦钿, 刘建军, 陈庆新, 等. 不相容工件族柔性流水车间批调度算法[J]. 机械设计与制造, 2016(6): 75-77
HUANG Jindian, LIU Jianjun, CHEN Qingxin, et al. Batch optimization algorithm for flexible flow-shop with incompatible job families[J]. Machinery Design & Manufacture, 2016(6): 75-77
[8] 徐本柱, 费晓璐, 章兴玲. 柔性作业车间批量划分与并行调度优化[J]. 计算机集成制造系统, 2016, 22(8): 1953-1964
XU Benzhu, FEI Xiaolu, ZHANG Xingling. Batch division and parallel scheduling optimization of flexible job shop[J]. Computer Integrated Manufacturing Systems, 2016, 22(8): 1953-1964
[9] 王万良, 范丽霞, 徐新黎, 等. 基于混合差分进化算法的并行机批处理调度问题研究[J]. 机电工程, 2012, 29(2): 7-12
WANG Wanliang, FAN Lixia, XU Xinli, et al. New hybrid differential evolution for parallel machines batch scheduling[J]. Journal of Mechanical & Electrical Engineering, 2012, 29(2): 7-12
[10] LIU L L, NG C T, CHENG T C E. On the complexity of bi-criteria scheduling on a single batch processing machine[J]. Journal of Scheduling, 2010, 13(6): 629-638
[11] GEEM Z W, KIM J H, LOGANATHAN G V. A new heuristic optimization algorithm: harmony search[J]. Simulation, 2001, 76(2): 60-68
[12] MAHDAVI M, FESANGHARY M, DAMANGIR E. An improved harmony search algorithm for solving optimization problems[J]. Applied Mathematics and Computation, 2007, 188(2): 1567-1579
[13] OMRAN M G H, MAHDAVI M. Global-best harmony search[J]. Applied Mathematics and Computation, 2007, 198(2): 643-656
[14] ALOULOU M A, BOUZAIENE A, DRIDI N, et al. A bicriteria two-machine flow-shop serial-batching scheduling problem with bounded batch size[J]. Journal of Scheduling, 2014, 17(1): 17-29
[15] UZSOY R. Scheduling a single batch processing machine with non-identical job sizes[J]. International Journal of Production Research, 1994, 32(7): 1615-1635
[16] KELLEGÖZ T, TOKLU B, WILSON J. Comparing efficiencies of genetic crossover operators for one machine total weighted tardiness problem[J]. Applied Mathematics and Computation, 2008, 199(2): 590-598
[17] CHO H M, BAE S J, KIM J, et al. Bi-objective scheduling for reentrant hybrid flow shop using Pareto genetic algorithm[J]. Computers & Industrial Engineering, 2011, 61(3): 529-541
[18] 陈辅斌, 李忠学, 杨喜娟. 基于改进NSGA2算法的多目标柔性作业车间调度[J]. 工业工程, 2018, 21(2): 55-61
CHEN Fubin, LI Zhongxue, YANG Xijuan. Multi-objective flexible job shop scheduling based on improved NSGA2 algorithm[J]. Industrial Engineering Journal, 2018, 21(2): 55-61