带运输资源约束柔性作业车间调度问题的人工蜂群算法

doi:10.12263/DZXB.20200382

电子学报 ›› 2021, Vol. 49 ›› Issue (2): 324-330.DOI: 10.12263/DZXB.20200382

带运输资源约束柔性作业车间调度问题的人工蜂群算法

李俊青^1,2, 杜宇¹, 田杰¹, 段培永¹, 潘全科^3,2

1. 山东师范大学信息科学与工程学院, 山东济南 250014;
2. 聊城大学计算机学院, 山东聊城 252059;
3. 上海大学机电工程与自动化学院, 上海 200072

收稿日期:2020-04-21 修回日期:2020-07-06 出版日期:2021-02-25
- 作者简介:
- 李俊青 男,1976年出生,山东聊城人.教授、博士生导师,主要从事智能优化与调度的研究.E-mail:lijunqing@lcu-cs.com;杜宇男,1992年出生,山东泰安人.博士研究生,主要从事智能优化与调度的研究.E-mail:dyscupse@163.com
- 基金资助:
- 国家自然科学基金 (No.61773192）; 山东省高等学校科技计划重点项目 (No.J17KZ005）

An Artificial Bee Colony Algorithm for Flexible Job Shop Scheduling with Transportation Resource Constraints

LI Jun-qing^1,2, DU Yu¹, TIAN Jie¹, DUAN Pei-yong¹, PAN Quan-ke^3,2

1. School of Information Science and Engineering, Shandong Normal University, Jinan, Shandong 250014, China;
2. College of Computer Science, Liaocheng University, Liaocheng, Shandong 252059, China;
3. School of Mechatronic Engineering and Automation, Shanghai University, Shanghai 200072, China

Received:2020-04-21 Revised:2020-07-06 Online:2021-02-25 Published:2021-02-25
- Supported by:
- National Natural Science Foundation of China (No.61773192); Science and Technology Project of Higher Education Institutions in Shandong Province (No.J17KZ005)

摘要/Abstract

摘要： 本文针对一类柔性作业车间调度问题，综合考虑运输资源约束、工件间准备时间约束等条件，以最小化最大完工时间和能耗为目标，提出了一种改进的人工蜂群优化算法.为求解该问题，算法采用二维向量编码，即调度向量记录工件的调度顺序，机床分配向量记录工件分配可用机床情况，解码过程充分考虑运输资源、工件间准备时间等约束条件.在局部搜索策略方面，提出了五种不同的调度邻域结构，并根据目标特点，设计了一种机床分配邻域结构.围绕人工蜂群算法的三个阶段，提出了不同的改进策略.为进一步提升算法的全局搜索能力，嵌入了模拟退火接受准则.实验结果验证了所提算法的优势显著.

关键词: 人工蜂群, 柔性作业车间, 能耗, 起重机运输, 准备时间

Abstract: The flexible job shop scheduling problem is investigated, where the transportation resource and operation related setup time constraints are considered simultaneously. The objective is to minimize the maximum completion time and the energy consumption. To solve the problem, we propose an improved artificial bee colony algorithm, where each solution is represented by a two-dimensional vector, the scheduling vector is to record the operation processing sequence, and the machine assignment vector is to assign the candidate machine for each operation. In the decoding mechanism, the transportation and setup time constraints are investigated. For the local search approaches, we develop five types of neighborhood structures for the scheduling part, and a well-designed machine assignment neighborhood structure for the machine assignment vector. To enhance the global searching abilities, the simulated annealing acceptance method is embedded. Finally, the experiment comparisons verify the performance of the proposed algorithm.

Key words: artificial bee colony, flexible job shop, energy consumption, crane transportation, setup time

中图分类号:

TP301.6

李俊青, 杜宇, 田杰, 等. 带运输资源约束柔性作业车间调度问题的人工蜂群算法[J]. 电子学报, 2021, 49(2): 324-330.

LI Jun-qing, DU Yu, TIAN Jie, et al. An Artificial Bee Colony Algorithm for Flexible Job Shop Scheduling with Transportation Resource Constraints[J]. Acta Electronica Sinica, 2021, 49(2): 324-330.

参考文献

[1] Kacem I,Hammadi S,Borne P.Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems[J].IEEE Transactions on Systems,Man,and Cybernetics,Part C (Applications and Reviews),2002,32(1):1-13.
[2] 王春,田娜,纪志成,王艳.求解模糊柔性作业车间调度的多目标进化算法[J].电子学报,2017,45(12):2909-2916. WANG Chun,TIAN Na,JI Zhi-cheng,WANG Yan.Multi-objective evolutionary algorithm to solve fuzzy flexible job shop scheduling problem[J].Acta Electronica Sinica,2017,45(12):2909-2916.(in Chinese)
[3] 雷德明,杨冬婧.具有总能耗约束的柔性作业车间调度问题研究[J].自动化学报,2018,44(11):2083-2091. Lei D M,Yang D J.Research on flexible job shop scheduling problem with total energy consumption constraint[J].Acta Automatica Sinica,2018,44(11):2083-2091.(in Chinese)
[4] Nouri H E,Belkahla Driss O,Ghédira K.Simultaneous scheduling of machines and transport robots in flexible job shop environment using hybrid metaheuristics based on clustered holonic multiagent model[J].Computers & Industrial Engineering,2016,102(6):488-501.
[5] Liu Z,Guo S,Wang L.Integrated green scheduling optimization of flexible job shop and crane transportation considering comprehensive energy consumption[J].Journal of Cleaner Production,2019,211(4):765-786.
[6] Karimi S,Ardalan Z,Naderi B,Mohammadi M.Scheduling flexible job-shops with transportation times:Mathematical models and a hybrid imperialist competitive algorithm[J].Applied Mathematical Modelling,2017,41(1):667-82.
[7] Bukata L,cha P,Hanzálek Z.Optimizing energy consumption of robotic cells by a Branch & Bound algorithm[J].Computers & Operations Research,2019,102(2):52-66.
[8] Gürel S,Gultekin H,Akhlaghi V E.Energy conscious scheduling of a material handling robot in a manufacturing cell[J].Robotics and Computer-Integrated Manufacturing,2019,58(4):97-108.
[9] Kats V,Levner E.On the existence of dominating 6-cyclic schedules in four-machine robotic cells[J].European Journal of Operational Research,2018,268(2):755-759.
[10] Liu S Q,Kozan E.A hybrid metaheuristic algorithm to optimise a real-world robotic cell[J].Computers & Operations Research,2017,84(5):188-194.
[11] Hurink J,Knust S.Tabu search algorithms for job-shop problems with a single transport robot[J].European Journal of Operational Research,2015,162(1):99-111.
[12] Batur G D,Erol S,Karasan O E.Robot move sequence determining and multiple part-type scheduling in hybrid flexible flow shop robotic cells[J].Computers & Industrial Engineering,2016,100(5):72-87.
[13] Li J Q,Pan Q K,Duan P Y.An improved artificial bee colony algorithm for solving hybrid flexible flowshop with dynamic operation skipping[J].IEEE Transactions on Cybernetics,2016,46(6):1311-1324.
[14] Li J Q,Bai S C,Duan P Y,Sang H Y,Han Y Y,Zheng Z X.An improved artificial bee colony algorithm for addressing distributed flow shop with distance coefficient in a prefabricated system[J].International Journal of Production Research,2019,57(22):6922-6942.

[1]	王强, 王有政, 王天施, 刘晓琴. 新型单相低能耗半桥逆变器[J]. 电子学报, 2023, 51(3): 779-782.
[2]	宋政育, 郝媛媛, 孙昕. 低轨卫星协作边缘计算任务迁移和资源分配算法[J]. 电子学报, 2022, 50(3): 567-573.
[3]	吕阳, 钱斌, 胡蓉, 张梓琪. 增强人工蜂群算法求解半导体最终测试调度问题[J]. 电子学报, 2021, 49(9): 1708-1715.
[4]	蒋万春, 廖凯琴. 节能以太网的节能策略综述[J]. 电子学报, 2021, 49(9): 1830-1839.
[5]	徐娟, 黄鸿敏, 阚佳丽, 张妍, 林林. 肺部太赫兹纳米传感器网络的拓扑结构优化设计[J]. 电子学报, 2021, 49(6): 1050-1058.
[6]	王强, 曹睿, 王天施, 刘晓琴. 具有低能耗辅助电路的三相谐振极逆变器[J]. 电子学报, 2021, 49(1): 167-170.
[7]	常丽, 朱宇祥, 蒋辉. 量子全加器设计[J]. 电子学报, 2019, 47(9): 1863-1867.
[8]	刘焕淋, 胡浩, 陈勇, 杜君丹, 向敏. 联合能耗与负载均衡的虚拟网络映射方法[J]. 电子学报, 2019, 47(12): 2488-2494.
[9]	杜振鑫, 刘广钟, 韩德志, 余学山, 贾建鑫. 基于全局无偏搜索策略的精英人工蜂群算法[J]. 电子学报, 2018, 46(2): 308-314.
[10]	张新明, 王霞, 康强, 程金凤. GWO与ABC的混合优化算法及其聚类优化[J]. 电子学报, 2018, 46(10): 2430-2442.
[11]	于昕妍, 沈艳霞, 陈杰, 纪志成. 考虑概率区间的微电网短期负荷多目标预测方法[J]. 电子学报, 2017, 45(4): 930-936.
[12]	王春, 田娜, 纪志成, 王艳. 求解模糊柔性作业车间调度的多目标进化算法[J]. 电子学报, 2017, 45(12): 2909-2916.
[13]	邬海琴, 王良民. 基于连通支配集的无线传感网Top-k查询最优支撑树研究[J]. 电子学报, 2017, 45(1): 119-127.
[14]	黄龙军, 王万良, 姚信威, 沈士根, 潘小刚. 电磁纳米网节能编码方法研究进展[J]. 电子学报, 2016, 44(8): 2018-2024.
[15]	徐超, 陈勇, 葛红美, 何炎祥. 基于符号执行的能耗错误检测方法[J]. 电子学报, 2016, 44(5): 1040-1050.

带运输资源约束柔性作业车间调度问题的人工蜂群算法

An Artificial Bee Colony Algorithm for Flexible Job Shop Scheduling with Transportation Resource Constraints

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics