求解同顺序加工调度问题的一种启发式方法

摘要/Abstract

摘要： 为了更加有效地求解同顺序加工调度问题，分析了现有启发式求解方法，发现影响解的质量的主要因素是调整近似解的方法和初始解，其中调整近似解的方法对解的质量影响较大。对此，提出了一种新的启发式方法。新方法中的调整方法考虑了调整对最短总加工时间的影响，调整任意给定的近似解不会降低解的质量，经过迭代运算，可以逐步改善近似解；新方法采用了多起点策略，利用调整方法调整不同初始解，选取最好的近似解作为问题的解，从而减小了初始解对问题解的质量的影响。实验结果表明，这种方法是有效的。

关键词: 同顺序加工调度问题

Abstract: Research was carried on current heuristic methods to get more valid solutions to Permutation Flow- shop Scheduling Problem (PFSP). It was found that initial solution and the adjustment on approximation may affect the solution. The adjustments on approximation were more effectively. So a new heuristic method was proposed. The adjustments on approximation took the manufacture time into account, so adjustment on any initial solution with it would not decrease the quality of the solution. Improvement was achieved by iteration. Multi-start strategy was adopted to decrease the effect of initial solution. Better solution was achieved based on the adjustment on different initial solution. Experiments showed that the method was valid.

Key words: permutation flow shop, scheduling, heuristic algorithm

中图分类号:

TP301.6

王正元，岑凯辉，谭跃进. 求解同顺序加工调度问题的一种启发式方法[J]. .

WANG Zheng-yuan, CEN Kai-hui, TAN Yue-jin. Heuristic algorithm to permutation flow shop scheduling problem[J]. .

参考文献

［1］WANG Ling. Intelligent optimization algorithms with applications[M]. Bejing:Tsinghua University Press,Springer Press,2001.159-160(in Chinese).[王凌.智能优化算法及其应用[M].北京：清华大学出版社，施普林格出版社，2001.159-160.]

[2]JOHNSON S M. Optimal two- and three-stage production schedules with setup times included[J]. Naval Research Logistics Quarterly, 1954,1(1):61-68.

[3]GAREY M, JOHNSON D，SETHI R.The complexity of flow shop and job shop scheduling[J]. Mathematics of Operations Reseach,1976,1(2):117-129.

[4]WANG Ling, ZHENG Dazhong. An improved genetic algorithm to solve permutation scheduling problem[J]. System Engineering Theory and Practice,2002，(6):74-79(in Chinese). [王凌，郑大钟.求解同顺序加工调度问题的一种改进遗传算法[J].系统工程理论与实践，2002，（6）：74-79.]

[5]CHEN Xiong, TANG Guangqiang, WU Qidi. Genetic algorithm for three-machine flow-shop scheduling problem[J]. Journal of Tongji University, 2001, 29(8):940-945(in Chinese).[陈雄，汤光强，吴启迪，一种求解3机flow-shop调度问题的遗传算法[J].同济大学学报，2001, 29(8)：940-945.]

[6]WANG Wanliang, WU Qidi. A new method solving job-shop scheduling problems based on hopfield neural networks[J]. Computer Integrated Manufacturing Systems,2001,7(12):7-12(in Chinese).[王万良，吴启迪.基于Hopfield神经网络求解作业车间调度问题的新方法[J].计算机集成制造系统，2001，7(12)：7-12.]

[7]WEI Youshuang, YANG Xianglong, FENG Yuncheng. Heuristic algorithms for flow shop scheduling problem[J]. System Engineering Theory and Practice, 2000，(9):41-47(in Chinese).[韦有双，杨湘龙，冯允成.一种新的求解Flow-shop问题的启发式方法[J].系统工程理论与实践，2000，(9)：41-47.]

[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):9-95.

[9]PALMER D S.Sequencing jobs through a multi-stage process in the minimum total time—a quick method of obtaining a near optimum[J]. Opserations Research Quarterly, 1965,16(1):101-107.

[10]SHEN Yingjun, HUANG Haijun, WU Sa,et al. New scheduling heuristic for the permutation flow-shop problem[J]. Journal of Beijing University of Aeronautics and Astronautic,1998，24(1)：83-87(in Chinese).[沈英俊，黄海军，吴飒，等.一种求解同顺序Flow shop排序问题的新的启发式算法[J].北京航空航天大学学报，1998， 24(1)：83-87.]

[11]ANDREW L T. No optimization without representation:a knowledge based systems view of evolutionary/neighborhood search optimization[D]. Scotland，U.K.:University of Edinburgh,1999.18-19.

[12]DIRK C，MATTFELD ROB J M V. Flowshopinfo.txt [EB/ OL]. http://mscmga.ms.ic.ac.uk/ueb/orlib/.

[1]	崔鹏浩,王军强,张文沛,李洋. 基于深度强化学习的流水线预测性维护决策[J]. 计算机集成制造系统, 2021, 27(12): 3416-3428.
[2]	杨丽丽,李文龙,孔祥龙,许浩. 混合不确定性鲁棒协同优化设计方法[J]. 计算机集成制造系统, 2021, 27(11): 3282-3290.
[3]	罗焕,陈浩杰,宋小欣,张剑. 带有缓存约束的作业车间调度求解方法[J]. 计算机集成制造系统, 2021, 27(10): 2880-2888.
[4]	张韵,钟慧超,张春江,李新宇,丛建臣. 基于机器学习的多策略并行遗传算法[J]. 计算机集成制造系统, 2021, 27(10): 2921-2928.
[5]	潘楠1,陈启用2+,刘海石1,孙雨轩3,安裕强4,潘地林5. 复杂工业品仓储环境无人机盘库任务规划[J]. 计算机集成制造系统, 2021, 27(10): 2940-2949.
[6]	张辰源,陶飞. 数字孪生模型评价指标体系[J]. 计算机集成制造系统, 2021, 27(8): 2171-2486.
[7]	刘晶,张喆语,董志红,季海鹏. 基于工业物联网的区块链多目标优化[J]. 计算机集成制造系统, 2021, 27(8): 2382-2392.
[8]	欧一鸣,苏雍贺,靳健,倪玮晨,陶飞. 基于知识图谱的分布式光伏运维方案匹配方法[J]. 计算机集成制造系统, 2021, 27(7): 1860-1870.
[9]	汪逸晖,高亮. 乌鸦搜索算法的改进及其在工程约束优化问题中的应用[J]. 计算机集成制造系统, 2021, 27(7): 1871-1883.
[10]	刘景森,马义想,李煜. 改进鲸鱼算法求解工程设计优化问题[J]. 计算机集成制造系统, 2021, 27(7): 1884-1897.
[11]	蒋晋,张则强,谢梦柯,蔡宁. 空间约束下多目标拆卸线平衡问题的改进狼群算法[J]. 计算机集成制造系统, 2021, 27(6): 1569-1581.
[12]	袁友伟,黄锡恺,俞东进,李忠金. 移动边缘计算环境下服务工作流容错调度算法[J]. 计算机集成制造系统, 2021, 27(6): 1693-1702.
[13]	刘俊琦,张则强,王沙沙,曾艳清. 考虑不规则物流交互点的过道布置问题建模与优化[J]. 计算机集成制造系统, 2021, 27(4): 1155-1166.
[14]	谢梦柯,张则强,蒋晋. 考虑工位约束及能耗的双边拆卸线平衡问题建模与优化[J]. 计算机集成制造系统, 2021, 27(3): 701-715.
[15]	高鹏,苏雍贺,靳健,谢祥颖,张长志,陶飞. 基于分布式光伏运维的多类型资源调度技术[J]. 计算机集成制造系统, 2021, 27(3): 787-799.