基于文化基因算法的开放车间调度问题研究

doi:10.3969/j.issn.1007-7375.2018.06.003

工业工程 ›› 2018, Vol. 21 ›› Issue (6): 16-22.doi: 10.3969/j.issn.1007-7375.2018.06.003

基于文化基因算法的开放车间调度问题研究

陈祥¹, 朱传军¹, 张超勇²

1. 湖北工业大学机械工程学院, 湖北武汉 430068;
2. 华中科技大学数字制造装备与技术国家重点实验室, 湖北武汉 430074

收稿日期:2017-08-25 出版日期:2018-12-30 发布日期:2018-12-29
通讯作者: 朱传军(1971-)，男，湖北省人，副教授，博士，主要研究方向为制造信息、智能调度算法、决策分析等. E-mail: zcj2579@126.com E-mail:1073428699@qq.com
作者简介:陈祥(1991-)，男，湖北省人，硕士研究生，主要研究方向为智能调度算法、决策分析
基金资助:
国家自然科学基金资助项目（51575211）

An Open Shop Scheduling Problem Based on Memetic Algorithm

CHEN Xiang¹, ZHU Chuanjun¹, ZHANG Chaoyong²

1. School of Mechanical Engineering, Hubei University of Technology, Wuhan 430068, China;
2. State Key Lab of Digital Manufacturing Equipment & Technology, Huazhong University of Science and Technology, Wuhan 430074, China

Received:2017-08-25 Online:2018-12-30 Published:2018-12-29

摘要/Abstract

摘要： 针对开放车间调度问题，运用了文化基因算法进行优化求解。在文化基因算法的框架中，既有种群中的全局搜索，又包含针对问题自身特点的局部搜索，为解决开放车间调度问题提供了一种新的算法。按照文化基因算法的思想和特点，将爬山法作为局部搜索策略加入到全局搜索策略所用到的遗传算法中，通过对开放车间调度问题的邻域结构进行研究，加入爬山搜索法进行优化求解。基于40个标准算例，通过与下界值的比较，验证了所提算法在解决具有较大搜索空间的调度问题时，其拥有更出色的算法性能。

关键词: 文化基因算法, 开放车间调度, 遗传算法, 爬山搜索法

Abstract: Aiming at the Open Shop Scheduling Problem (OSSP), a Memetic Algorithm (MA) is proposed to solve the problem. In the framework of the cultural Genetic Algorithm (GA), both global search and local search for the problem's own characteristics are provided. It provides a new algorithm for solving the open job shop scheduling problem. According to the thought and cultural characteristics of genetic algorithm, the method of climbing as a local search strategy into the genetic algorithm global search strategy is used, and a research of neighborhood structure is conducted on open shop scheduling problem, adding hill-climbing search method to solve the optimal. Based on the comparison of 40 standard examples, it is proved that the proposed algorithm has better performance in solving the scheduling problem with larger search space by comparing with lower bound values.

Key words: memetic algorithm, open shop scheduling, genetic algorithm, hill climbing search

中图分类号:

TH186

陈祥, 朱传军, 张超勇. 基于文化基因算法的开放车间调度问题研究[J]. 工业工程, 2018, 21(6): 16-22.

CHEN Xiang, ZHU Chuanjun, ZHANG Chaoyong. An Open Shop Scheduling Problem Based on Memetic Algorithm[J]. Industrial Engineering Journal , 2018, 21(6): 16-22.

参考文献

[1] LOW C F, YEH Y. Genetic algorithm-based heuristics for an open shop scheduling problem with setup processing and removal times separated[J]. Robotics and Computer-Integrated Manufacturing, 2009, 25(2):314-322
[2] BRUCKER P, HURINK J, JURISCH B, et al. A branch & bound algorithm for the open-shop problem[J]. Discrete Applied Mathematics, 1997, 76(1-3):43-59
[3] TAILLARD E D. Benchmark for basic scheduling problems[J]. European Journal of Operational Research, 1993, 64(2):278-285
[4] ROCK H, SCHMIDT G. Machine aggregation heuristics in shop-scheduling[J]. Methods of Operations Research, 1983, 45:303-314
[5] AHMADIZAR F, FARAHANI M H. A novel hybrid genetic algorithm for the open shop scheduling problem[J]. The International Journal of Advanced Manufacturing Technology, 2012, 62(5-8):775-787
[6] DOULABI S, AVAZBEIUI M, ARAB S, et al. An effective hybrid simulated annealing and two mixed integer linear formulations for just-in-time open shop scheduling problem[J]. The International Journal of Advanced Manufacturing Technology, 2012, 59(9-12):1143-1155
[7] GUERET C, PRINS C. Classical and new heuristics for the open-shop problem:a computational evaluation[J]. European Journal of Operational Research, 1998, 107(2):306-314
[8] 王军强, 郭银洲, 崔福东, 等. 基于多样性增强的自适应遗传算法的开放式车间调度优化[J]. 计算机集成制造系统, 2014, 20(10):2479-2493 WANG Junqiang, GUO Yinzhou, CUI Fudong, et al. Diversity enhancement based adaptive genetic algorithm for open-shop scheduling problem[J]. Computer Integrated Manufacturing Systems, 2014, 20(10):2479-2493
[9] 展勇, 邱长华, 祝海涛. 基于网络流的多并行机可中断开放车间调度算法[J]. 计算机集成制造系统, 2011, 17(5):990-996 ZHAN Yong, QIU Changhua, ZHU Haitao. Algorithm of preemptive open-shop scheduling with parallel machines based on network flow[J]. Computer Integrated Manufacturing Systems, 2011, 17(5):990-996
[10] ROY B, SUSSMAN B. Les problèmes d'ordonnancement avec contraintes disjonctives[C/OL].(2017-08-01).http://www.scirp.org/(S(i43dyn45teexjx455qlt3d2q))/reference/ReferencesPapers.aspx?ReferenceID=1201138.
[11] PINEDO M. 调度:原理、算法和系统[M]. 张智海, 译. 北京:清华大学出版社, 2007.
[12] BELLMAN R E. On a routing problem[J]. Quarterly Applied Mathematics, 1958, 16:87-90
[13] 刘漫丹. 文化基因算法(Memetic Algorithm)研究进展[J]. 自动化技术与应用, 2007, 26(11):1-4, 18 LIU Mandan. The development of the memetic algorithm[J]. Techniques of Automation & Application, 2007, 26(11):1-4, 18
[14] 玄光男, 程润伟. 遗传算法与工程优化[M]. 北京:清华大学出版社, 2004.
[15] MATTFELD D C. Evolutionary Search and The Job Shop[M]. Berlin:Springer, 1995.

基于文化基因算法的开放车间调度问题研究

An Open Shop Scheduling Problem Based on Memetic Algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	张正敏, 管在林, 岳磊. 基于Lévy Flight的混合GA在柔性作业车间调度问题中的性能分析[J]. 工业工程, 2021, 24(4): 83-92.
[2]	王晓军, 王博, 晋民杰, 杨春霞, 白新利. 改进多种群遗传算法的AutoStore系统多AGV调度优化[J]. 工业工程, 2021, 24(4): 112-118,167.
[3]	王莹莹, 吴立云. 基于改进NSGA-II的多项目多技能人力资源调度研究[J]. 工业工程, 2021, 24(3): 130-138.
[4]	曾创锋, 刘建军, 陈庆新, 毛宁. 求解一类无关并行机调度的遗传迭代贪心算法[J]. 工业工程, 2021, 24(2): 110-118.
[5]	黄露, 纪延光. 考虑顾客延误损失的配送中心选址双层规划问题研究[J]. 工业工程, 2021, 24(2): 141-147.
[6]	王冰怡, 张锦. 考虑网点共享与变更的多级快递网点选址问题[J]. 工业工程, 2021, 24(2): 155-165.
[7]	马跃如, 文铮, 易丹. 考虑老年人满意度的多目标居家养老护理员路径优化[J]. 工业工程, 2021, 24(1): 74-81,103.
[8]	王玖河, 高辉, 刘欢. 基于遗传算法的共享助力车调度问题研究[J]. 工业工程, 2021, 24(1): 90-96.
[9]	吴斌, 宋琰, 程晶, 董敏. 基于密度峰值聚类的VRPTW问题研究[J]. 工业工程, 2020, 23(5): 58-66,74.
[10]	王苏林, 邱菲尔, 陈凡, 刘川昆, 鹿腾, 王芷芸. 基于贪心遗传的地下物流节点选择规划研究[J]. 工业工程, 2020, 23(5): 88-95.
[11]	侯艳, 黄康焕, 张亿仙, 伍乃骐. 原油一次加工过程的多目标调度优化[J]. 工业工程, 2020, 23(4): 131-139.
[12]	王泽, 杨信丰, 刘兰芬. 考虑电量消耗的车辆调度优化研究[J]. 工业工程, 2020, 23(4): 140-147.
[13]	曾垂飞, 刘建军, 陈庆新, 毛宁. 装配作业车间分批调度问题的算法对比[J]. 工业工程, 2020, 23(4): 174-182.
[14]	张巍, 李鹏翔, 仝自强, 岳毅蒙. 基于损坏车辆分布预测与损益阈值分析下的共享单车回收研究[J]. 工业工程, 2020, 23(3): 132-137.
[15]	张国辉, 胡一凡, 孙靖贺. 改进遗传算法求解多时间约束的柔性作业车间调度问题[J]. 工业工程, 2020, 23(2): 19-25,48.