Whole-set order problem of hybrid flow shop based on heuristic-genetic algorithms

doi:10.11772/j.issn.1001-9081.2019030468

Abstract

Abstract:

A heuristic-genetic algorithm based on batch scheduling strategy was proposed for the whole-set order problem in hybrid flow shop environment with process constrainted parallel machine. Firstly, a mathematical model was established with the objective of maximizing the number of weighted whole-set orders, and initial scheduling was generated by inner genetic algorithm applying to workpieces in batches. Then, the target was transformed to the maximum weighted whole-set order quantity by outer heuristic rules, and an order evaluation index was designed to break the delivery time bottleneck. Finally, the inner and outer algorithms were optimized circularly until there was no bottleneck, which means the satisfactory solution was obtained. Examples show that heuristic-genetic algorithm can obtain the optimal scheduling within 20 generations, and the probability of obtaining the optimal solution is 70% when the population size is larger than 50. The experimental results show that when the scale of the problem increases to 40 workpieces, the solving time of genetic algorithm increases significantly, and the number of whole-set orders optimized by Smallest Critical Ratio (SCR) rule is smaller than the heuristic-genetic algorithm in different problem sizes. Heuristic-genetic algorithm can increase the quantity of weighted whole-set orders to more than 1.5 times in practical engineering, and shorten the processing time by 5.1% on average. The results show that the heuristic-genetic algorithm can solve the problem that the whole-set order problems are easy to fall into local optimum in the hybrid flow shop environment, and can realize the synchronization of planning and production in the large-scale and complex hybrid flow shop ordering enterprises, which has practical significance.

Key words: hybrid flow shop, whole-set order, genetic algorithm, heuristic rule, shop scheduling

摘要：

针对并行机带工艺约束的混合流水车间环境下的成套订单问题，提出一种基于分批调度策略的启发式-遗传算法。首先，以最大化加权成套订单数为目标建立数学模型，对工件分批采用内层遗传算法生成初始调度；再以外层启发式规则转化目标为最大加权成套订单数，设计一种订单评价指标用于突破交货时间瓶颈；最后，内外层算法循环优化，直到不存在瓶颈即得到满意解。实例验证结果显示，启发式-遗传算法能在20代以内得到每组最优调度，种群规模大于50时得到最优解的概率达到70%。对比实验结果显示，当问题规模增加到40个工件时，遗传算法求解时间显著增加，在不同问题规模中临界比最小（SCR）规则优化后的加权成套订单数均较启发式-遗传算法更少。启发式-遗传算法能在实际工程中够将加权成套订单数提高到1.5倍以上，使加工时间平均缩短5.1%。结果表明，启发式-遗传算法能够改善成套订单问题在混合流水车间环境下易陷入局部最优的问题，可在大规模复杂混合流水车间的订货型企业中实现计划与生产同步，具有实际意义。

关键词: 混合流水车间, 成套订单, 遗传算法, 启发式规则, 车间调度

CLC Number:

TP301
TP18

JIA Yeling, Dong Shaohua. Whole-set order problem of hybrid flow shop based on heuristic-genetic algorithms[J]. Journal of Computer Applications, 2019, 39(9): 2772-2777.

贾叶玲, 董绍华. 基于启发式遗传算法的混合流水车间成套订单问题[J]. 计算机应用, 2019, 39(9): 2772-2777.

References

[1] 吕秀芬.复杂环境下MTO企业交货期优化研究[D].广州:广东工业大学,2011:6-13.(LYU X F. Research on due-date optimization for MTO manufacture based in complex environment[D]. Guangzhou:Guangdong University of Technology, 2011:6-13.)
[2] 周水银,陈荣秋.单机加权成套订单数遗传算法研究[J].系统工程,2005,23(5):22-24.(ZHOU S Y, CHEN R Q. A genetic algorithm:weighted single machine scheduling problems to maximize the whole-set orders[J]. Systems Engineering, 2005, 23(5):22-24.)
[3] 苏亚,傅青.并行机含调整时间成套订单数问题遗传算法[J].控制工程,2007,14(1):78-81.(SU Y, FU Q. Genetic algorithm for whole-set order problem of identical parallel scheduling with setup time[J]. Control Engineering of China, 2007,14(1):78-81.)
[4] YU Z, YANG X. Full glowworm swarm optimization algorithm for whole-set orders scheduling in single machine[J]. The Scientific World Journal, 2013(1):652061.
[5] 肖世昌,孙树栋,杨宏安.混合分布估计算法求解随机Jobshop提前/拖期调度问题[J].控制与决策,2015(10):1854-1860.(XIAO S C, SUN S D, YANG H A. Hybrid estimation of distribution algorithm for stochastic Job shop scheduling with earliness/tardiness penalty[J]. Control and Decision, 2015(10):1854-1860.)
[6] 桂玲,谢勇,王红卫.钢箱梁生产的提前/拖期调度问题研究[J].系统工程理论与实践,2017,37(5):1274-1281.(GUI L, XIE Y, WANG H W. Early/tardy scheduling problem for the steel box girders production and construction[J]. Systems Engineering-Theory and Practice, 2017,37(5):1274-1281.)
[7] HOOGEVEEN J A, LENSTRA J K, VELTMAN B. Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard[J]. European Journal of Operational Research, 1996, 89(1):172-175.
[8] TAMAKI H, NISHINO E, ABE S. A genetic algorithm approach to multi-objective scheduling problems with earliness and tardiness penalties[C]//Proceedings of the 1999 Congress on Evolutionary Computation. Piscataway, NJ:IEEE, 1999,1:No. 99TH8406.
[9] PORTMANN M C, VIGNIER A, DARDILHAC D, et al. Branch and bound crossed with GA to solve hybrid flowshops[J]. European Journal of Operational Research, 1998, 107(2):389-400.
[10] WANG C, LIU C, ZHANG Z H, et al. Minimizing the total completion time for parallel machine scheduling with job splitting and learning[J]. Computers and Industrial Engineering, 2016, 97(C):170-182.
[11] WANG W-L, WANG H-Y, ZHAO Y-W, et al. Parallel machine scheduling with splitting jobs by a hybrid differential evolution algorithm[J]. Computers and Operations Research, 2013, 40(5):1196-1206.
[12] 史青涛.基于遗传算法的单工序并行机分批调度研究[D].大连:大连理工大学, 2014:25-34.(SHI Q T. Research on lot splitting scheduling for parallel machines with single operation based on genetic algorithm[D]. Dalian:Dalian University of Technology, 2014:25-34.)
[13] WANG C, LIU C, ZHANG Z-H, et al. Minimizing the total completion time for parallel machine scheduling with job splitting and learning[J]. Computers and Industrial Engineering, 2016, 97(C):170-182.
[14] 赵海丹.有模具限制的并行机台调度问题研究[D].长春:吉林大学,2016:19-32.(ZHAO H D. Study on parallel machines with mold constraint scheduling problem[D]. Changchun:Jilin University, 2016:19-32.)
[15] 高家全,赵端阳,何桂霞,等.解特殊工艺约束拖后调度问题的并行遗传算法[J].计算机工程与应用,2007,43(27):184-186.(GAO J Q, ZHAO D Y, HE G X, et al. Parallel genetic algorithm for tardiness scheduling problem with special process constraint[J]. Computer Engineering and Applications, 2007, 43(27):184-186.)