|本期目录/Table of Contents|

[1]陈海波,张超隆,董建明.基于时序Petri网的机器人柔性作业车间无死锁调度优化算法[J].浙江理工大学学报,2024,51-52(自科六):839-850.
　CHEN Haibo,ZHANG Chaolong,DONG Jianming.A deadlockfree scheduling algorithm of robotic flexible job shops based on temporal Petri nets[J].Journal of Zhejiang Sci-Tech University,2024,51-52(自科六):839-850.
点击复制

基于时序Petri网的机器人柔性作业车间无死锁调度优化算法()
分享到：

浙江理工大学学报[ISSN:1673-3851/CN:33-1338/TS]

卷:
第51-52卷
期数:
2024年自科第六期
页码:
839-850
栏目:
出版日期:
2024-11-20

文章信息/Info

Title:
A deadlockfree scheduling algorithm of robotic flexible job shops based on temporal Petri nets
作者:
陈海波; 张超隆; 董建明
1.浙江理工大学计算机科学与技术学院（人工智能学院），杭州 310018；2.浙江工商大学管理工程与电子商务学院， 杭州 310018
Author(s):
CHEN Haibo;  ZHANG Chaolong;  DONG Jianming
1 School of Computer Science and Technology (School of Artificial Intelligence), Zhejiang Sci-Tech University, Hangzhou 310018, China; 2 School of Management and E Business, Zhejiang  Gongshang University, Hangzhou 310018, China
关键词:
作业车间调度; 离散蜂群算法; 单机器人; Petri网; 阻塞和死锁
分类号:
TP301-6
文献标志码:
A
摘要:
研究了一类源于芯片生产等智能制造领域的机器人柔性作业车间调度问题。针对该类问题在算法设计过程中，需要同时考虑工件加工、机器人运输和死锁求解等带来的问题，提出了一种基于时序Petri网的无死锁调度优化算法。首先，对问题进行时序Petri网建模，提出了一种基于Petri网变迁串的解表示形式，以方便死锁求解和算法寻优；其次，通过对问题死锁的结构分析和分类，提出了一种死锁判断和求解算法，并证明了算法可在多项式时间内求解任意类型死锁，同时也能在一定程度上保证解的优良结构；最后，提出了问题的一种离散蜂群算法求解方案，在算法寻优过程中进行实时死锁求解以保证解的可行性和较快的收敛速度。不同规模实例的数值实验和与问题最优解及最优解下界的比较分析表明，提出的算法对不同类型实例都体现了较好的性能和较低的时间复杂度。该研究为复杂作业车间实时调度问题的算法研究提供了新思路和方法。

参考文献/References:

［ 1 ］胡觉亮 , 李志林 , 董建明 . 工件加工需要额外资源的平行机调度问题［ J ］ . 浙江理工大学学报 ( 自然科学版 ),2022,47(5):791 - 797.

［2］Ali Chaudhry I, Ali Khan A. A research survey: review of flexible job shop scheduling techniques［J］. International Transactions in Operational Research, 2016, 23(3): 551-591.

［3］曹珍,韩曙光.考虑充电调度的电动无人车配送路径规划问题研究［J］.浙江理工大学学报(自然科学),2023,49(6):784-794.

［4］Yan P Y, Liu S Q, Sun T F, et al. A dynamic scheduling approach for optimizing the material handling operations in a robotic cell［J］. Computers & Operations Research, 2018, 99: 166-177.

［5］Wei L X, He J X, Guo Z Y, et al. A multi-objective migrating birds optimization algorithm based on game theory for dynamic flexible job shop scheduling problem［J］. Expert Systems with Applications, 2023, 227: 120268.

［6］Liu S Q, Kozan E, Masoud M, et al. Job shop scheduling with a combination of four buffering constraints［J］. International Journal of Production Research, 2018, 56(9): 3274-3293.

［7］Bektur G, SaraT. A mathematical model and heuristic algorithms for an unrelated parallel machine scheduling problem with sequence-dependent setup times, machine eligibility restrictions and a common server［J］. Computers & Operations Research, 2019, 103: 46-63.

［8］Drobouchevitch I G, Neil Geismar H, Sriskandarajah C. Throughput optimization in robotic cells with input and output machine buffers: A comparative study of two key models［J］. European Journal of Operational Research, 2010, 206(3): 623-633.

［9］Li X L, Xing K Y, Lu Q C. Hybrid particle swarm optimization algorithm for scheduling flexible assembly systems with blocking and deadlock constraints［J］. Engineering Applications of Artificial Intelligence, 2021, 105: 104411.

［10］Xing K Y, Wang F, Zhou M C, et al. Deadlock characterization and control of flexible assembly systems with Petri nets［J］. Automatica, 2018, 87: 358-364.

相似文献/References:

[1]张建明.基于改进量子进化算法的作业车间调度研究[J].浙江理工大学学报,2014,31-32(自科3):310.
　ZHANG Jian ming.A Novel Quantum Evolutionary Algorithm for Job shop Scheduling[J].Journal of Zhejiang Sci-Tech University,2014,31-32(自科六):310.

备注/Memo

备注/Memo:
收稿日期： 2024-04-15
网络出版日期：2024-07-22
基金项目： 国家自然科学基金项目（11971435）；浙江省“领雁”研发攻关项目（2024C01108）
作者简介： 陈海波（1972—），男，杭州人，副教授，博士，主要从事算法设计与计算机语言理论方面的研究
通信作者： 董建明，E-mail:djm226@163.com
更新日期/Last Update: 2024-11-14