有限缓冲区流水线调度的多搜索模式遗传算法

摘要/Abstract

摘要： 针对有限缓冲区流水线调度问题，提出了一种多搜索模式遗传算法，算法使用多个交叉和变异操作进行解空间的探索和改良，并采用基于有向图的邻域结构来增强局部搜索。同时，局部搜索和变异操作受决策概率控制。基于典型算例的仿真和比较研究验证了所提算法的有效性。

关键词: 遗传算法, 流水线调度, 有限缓冲区

Abstract: A genetic algorithm with multiple search modes was proposed for flow-shop scheduling with limited buffers. Multiple crossover operators and mutation operators were utilized in the algorithm for evolutionary exploration and exploitation among the solution space, and a directed graph model based neighborhood structure was also applied to improve the local search. Moreover, the local search and mutation were controlled by decision probability. Simulation results and comparisons based on benchmarks demonstrated the effectiveness of the proposed algorithm.

Key words: genetic algorithm, flow-shop scheduling, limited buffers

中图分类号:

TP273

王凌，张亮. 有限缓冲区流水线调度的多搜索模式遗传算法[J]. .

WANG Ling, ZHANG Liang. Genetic algorithm with multiple searching modes for flow-shop scheduling with limited buffers[J]. .

参考文献

［1］ THORNTON H W, HUNSUCKER J L. A new heuristic for minimal makespan in flow shops with multiple processors and no intermediate storage［J］. European Journal of Operational Research, 2004, 152(1): 96-114.

[2] HALL N G, SRISKANDARAJAH C. A survey of machine scheduling problems with blocking and no-wait in process［J］. Operations Research, 1996, 44(3): 510-525.

[3] NORMAN B A. Scheduling flowshops with finite buffers and sequence-dependent setup times［J］. Computers & Industrial Engineering, 1999, 36(1): 163-177.

[4] NOWICKI E. The permutation flow shop with buffers: a tabu search approach［J］. European Journal of Operational Research, 1999, 116(1): 205-219.

[5] BRUCKER P, HEITMANN S, HURINK J. Flow-shop problems with intermediate buffers［J］. OR Spectrum, 2003, 25(4): 549-574.

[6] LEISTEN R. Flowshop sequencing problems with limited buffer storage［J］. International Journal of Production Research, 1990, 28(11): 2085-2100.

[7] RONCONI D P. A note on constructive heuristics for the flowshop problem with blocking［J］. International Journal of Production Economics, 2004, 87(1): 39-48.

[8] NAWAZ M, ENSCORE E Jr, HAM I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem［J］. Omega, 1983, 11(1): 91-95.

[9] MASCIS A, PACCIARELLI D. Job-shop scheduling with blocking and no-wait constraints［J］. European Journal of Operational Research, 2001, 143(3): 498-517.

[10] WARDONO B, FATHI Y. A tabu search algorithm for the multi-stage parallel machine problems with limited buffer capacities［J］. European Journal of Operational Research, 2004, 155(2): 380-401.

[11] SAWIK T. Mixed integer programming for scheduling flexible flow lines with limited intermediate buffers［J］. Mathematical and Computer Modeling, 2000, 31(13): 39-52.

[12] WOLPERT D H, MACREADY W G. No free lunch theorems for optimization［J］. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 67-82.

[1]	陈年,金涛,王建民. 基于变异反馈的临床路径优化[J]. 计算机集成制造系统, 2021, 27(9): 2556-2564.
[2]	黎英杰,刘建军,陈庆新,毛宁. 多层级装配作业车间等量分批策略与调度算法[J]. 计算机集成制造系统, 2021, 27(8): 2307-2320.
[3]	王文中,张树生,余隋怀,陈登凯. 基于解构·重构思维的潜水器舱室布局优化[J]. 计算机集成制造系统, 2021, 27(7): 2045-2052.
[4]	王勇,周雪,刘永,许茂增. 基于车辆共享的多中心共同配送联盟优化[J]. 计算机集成制造系统, 2021, 27(6): 1820-1832.
[5]	张昊鹏,郭宇,汤鹏洲,黄少华,刘道元,李晗. 基于图像匹配的增强现实装配系统跟踪注册方法[J]. 计算机集成制造系统, 2021, 27(5): 1281-1291.
[6]	胡金昌,刘紫薇,马文凯,吴耀华. 考虑学习效应的单人作业车间多目标调度算法[J]. 计算机集成制造系统, 2021, 27(5): 1361-1370.
[7]	刘俊琦,张则强,王沙沙,曾艳清. 考虑不规则物流交互点的过道布置问题建模与优化[J]. 计算机集成制造系统, 2021, 27(4): 1155-1166.
[8]	裴小兵,李依臻. 新型混合改进遗传算法求解零等待流水车间调度问题[J]. 计算机集成制造系统, 2021, 27(3): 815-827.
[9]	李从东,章志伟,曹策俊,张帆顺. 复杂产品设计变更传播路径的多目标优选[J]. 计算机集成制造系统, 2021, 27(3): 842-856.
[10]	杨小明,徐子奇,金雯,舒帆. 复合拣选策略下堆垛机作业序列优化问题[J]. 计算机集成制造系统, 2021, 27(3): 933-942.
[11]	李丽丽,陈琨,高建民,李辉,冯增行,张建. 采用优化概率神经网络的质量异常识别方法[J]. 计算机集成制造系统, 2021, 27(10): 2813-2821.
[12]	薛玲玲. 作业车间调度的块结构邻域搜索遗传算法[J]. 计算机集成制造系统, 2021, 27(10): 2848-2857.
[13]	罗焕,陈浩杰,宋小欣,张剑. 带有缓存约束的作业车间调度求解方法[J]. 计算机集成制造系统, 2021, 27(10): 2880-2888.
[14]	张韵,钟慧超,张春江,李新宇,丛建臣. 基于机器学习的多策略并行遗传算法[J]. 计算机集成制造系统, 2021, 27(10): 2921-2928.
[15]	狄卫民,王然. 考虑多级设施中断的供应链选址—库存决策模型及优化算法[J]. 计算机集成制造系统, 2021, 27(1): 270-283.