基于块结构性质的花粉算法求解可重入作业车间调度问题

doi:10.3901/JME.2019.16.220

机械工程学报 ›› 2019, Vol. 55 ›› Issue (16): 220-232.doi: 10.3901/JME.2019.16.220

• 交叉与前沿 • 上一篇

扫码分享

基于块结构性质的花粉算法求解可重入作业车间调度问题

孙在省, 钱斌, 胡蓉, 张梓琪, 张长胜

昆明理工大学信息工程与自动化学院昆明 650500

收稿日期:2018-12-15 修回日期:2019-05-02 出版日期:2019-08-20 发布日期:2019-08-20
通讯作者: 钱斌(通信作者),男,1976年出生,教授,博士。主要研究方向为优化调度理论与方法、智能优化方法。E-mail:bin.qian@vip.163.com
作者简介:孙在省,男,1993年出生。主要研究方向为优化调度理论与方法。E-mail:szx_1010@163.com
基金资助:
国家自然科学基金（51665025，60904081）和云南省自然科学基金（2015FB136）资助项目。

Flower Pollination Algorithm Based on Block Structure Properties for Reentrant Job Shop Scheduling Problem

SUN Zaixing, QIAN Bin, HU Rong, ZHANG Ziqi, ZHANG Changsheng

College of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500

Received:2018-12-15 Revised:2019-05-02 Online:2019-08-20 Published:2019-08-20

摘要/Abstract

摘要： 针对可重入作业车间调度问题（Reentrant job shop scheduling problem，RJSSP），提出一种基于块结构性质的花粉算法（Flower pollination algorithm based on block structure properties，FPA_BSP），用于最小化总加权延误时间（Total weighted tardiness，TWT）。首先，建立RJSSP基于析取图的数学模型，并证明在确定析取弧方向后，该模型的对偶模型为最大费用流问题模型。其次，设计扩展RSOV （Reentrant-smallest-order-value，RSOV）编码规则，将花粉算法的实数矢量个体转变为排列矢量，使其可对问题解空间进行全局搜索，以发现存在优质解的区域。然后，定义8种邻域结构，并基于最大费用流问题特性分析块结构内部性质，得到前4种邻域结构能改进TWT的判定条件，可用于避免对无效区域的搜索，进而提出融合多种邻域的高效局部搜索，对全局搜索发现的优质解区域进行细致搜索。试验和算法比较验证FPA_BSP的有效性。提出RJSSP的块结构性质，并将其与花粉算法结合得到求解RJSSP的有效算法FPA_BSP，首次将花粉算法用于求解车间调度问题。

关键词: 花粉算法, 可重入作业车间调度问题, 块结构性质, 总加权延误时间

Abstract: Flower pollination algorithm based on block structure properties (FPA_BSP) is presented to minimize the total weighted tardiness (TWT) for reentrant job shop scheduling problem (RJSSP). Firstly, the mathematical model of RJSSP based on the disjunctive graph is established, and then its duality model is proved to be the model of maximum cost flow problem after it being determined the direction of the disjunctive arcs. Secondly, the extended reentrant-smallest-order-value (RSOV) encoding rule is designed to transform FPA's individuals from real vectors to job permutations so that flower pollination algorithm (FPA) can be used to perform global search for finding high-quality solutions or regions in the solution space. Thirdly, eight kinds of neighborhood structures are defined, and the inner properties of block structures are analyzed based upon the properties of the maximum cost flow problem. The determination conditions of the four former neighborhood structures for improving TWT are obtained by the block structures' analyses, which can be used to avoid search in the invalid regions. Then, a high-efficient local search integrating multiple neighborhoods with the obtained determination conditions is proposed to execute a thorough search from the promising regions found by the global search. Computational experiments and comparisons manifest the effectiveness of the presented FPA_BSP. The properties of RJSSP's block structures and incorporates them with FPA are proposed to obtain an effective FPA_BSP for solving RJSSP. It is also the first time that FPA is used to address scheduling problem.

Key words: block structure properties, flower pollination algorithm, reentrant job shop scheduling problem, total weighted tardiness

中图分类号:

TG156

孙在省, 钱斌, 胡蓉, 张梓琪, 张长胜. 基于块结构性质的花粉算法求解可重入作业车间调度问题[J]. 机械工程学报, 2019, 55(16): 220-232.

SUN Zaixing, QIAN Bin, HU Rong, ZHANG Ziqi, ZHANG Changsheng. Flower Pollination Algorithm Based on Block Structure Properties for Reentrant Job Shop Scheduling Problem[J]. Journal of Mechanical Engineering, 2019, 55(16): 220-232.

导出引用管理器 EndNote|Reference Manager|ProCite|BibTeX|RefWorks

链接本文: http://www.cjmenet.com.cn/CN/10.3901/JME.2019.16.220

http://www.cjmenet.com.cn/CN/Y2019/V55/I16/220

参考文献

[1] 潘全科,王凌,高亮,等. 基于差分进化与块结构邻域的作业车间调度优化[J]. 机械工程学报,2010,46(22):182-188. PAN Quanke,WANG Ling,GAO Liang,et al. Differential evolution algorithm based on blocks on critical path for job shop scheduling problems[J]. Journal of Mechanical Engineering,2010,46(22):182-188.
[2] GAREY M R,JOHNSON D S,SETHI R. The complexity of flowshop and jobshop scheduling[J]. Mathematics of Operations Research,1976,1(2):117-129.
[3] 唐国春,张峰,罗守成,等. 现代排序论[M]. 上海:上海科学普及出版社,2003. TANG Guochun,ZHANG Feng,LUO Shoucheng,et al. Modern scheduling theory[M]. Shanghai:Shanghai Popular Science Press,2003.
[4] VAN LAARHOVEN P J M,AARTS E H L,LENSTRA J K. Job shop scheduling by simulated annealing[J]. Operations Research,1988, 40(1):113-125.
[5] BALAS E. Machine sequencing via disjunctive graphs:an implicit enumeration algorithm[J]. Operations Research,1969,17(17):941-957.
[6] MATSUO H,SUH C J,SULLIVAN R S. A controlled search simulated annealing method for the general job-shop scheduling problem[J]. Annals of Operations Research,1988,21(1):85-108.
[7] GRABOWSKI J,NOWICKI E,SMUTNICKI C. Block algorithm for scheduling operations in a job-shop system[J]. Przeglad Statystyczny,1988,35(1):67-80.
[8] GRABOWSKI J,NOWICKI E,ZDRZALKA S. A block approach for single-machine scheduling with release dates and due dates[J]. European Journal of Operational Research,1986,26(2):278-285.
[9] DELL'AMICO M,TRUBIAN M. Applying tabu search to the job-shop scheduling problem[J]. Annals of Operations Research,1993,41(3):231-252.
[10] NOWICKI E,SMUTNICKI C. A fast taboo search algorithm for the job shop problem[J]. Management Science,1996,42(6):797-813.
[11] BALAS E,VAZACOPOULOS A. Guided local search with shifting bottleneck for job shop scheduling[J]. Management Science,1998,44(2):262-275.
[12] ZHANG C Y,LI P G,GUAN Z L,et al. A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem[J]. Computers & Operations Research,2007,34(11):3229-3242.
[13] ZHANG R,WU C. A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective[J]. Computers & Operations Research,2011,38(5):854-867.
[14] KUHPFAHL J,BIERWIRTH C. A study on local search neighborhoods for the job shop scheduling problem with total weighted tardiness objective[J]. Computers & Operations Research,2016,66:44-57.
[15] 赵诗奎. 基于新型邻域结构的混合算法求解作业车间调度[J]. 机械工程学报,2016,52(9):141-151. ZHAO Shikui. A hybrid algorithm with a new neighborhood structure for the job shop scheduling problem[J]. Journal of Mechanical Engineering,2016,52(9):141-151.
[16] TOPALOGLU S,KILINCLI G. A modified shifting bottleneck heuristic for the reentrant job shop scheduling problem with makespan minimization[J]. International Journal of Advanced Manufacturing Technology,2009,44(7-8):781-794.
[17] QIAN B,LI Z H,HU R,et al. A hybrid differential evolution algorithm for the multi-objective reentrant job-shop scheduling problem[C]//10th IEEE International Conference on Control and Automation (ICCA),Hangzhou,2013:485-489.
[18] CHEN S F,QIAN B,LIU B,et al. Bayesian statistical inference-based estimation of distribution algorithm for the re-entrant job-shop scheduling problem with sequence-dependent setup times[C]//10th International Conference on Intelligent Computing (ICIC),Taiyuan,2014. Lecture Notes in Computer Science, Springer, Cham,2014,(8589):686-696.
[19] YANG X S. Flower pollination algorithm for global optimization[C]//International Conference on Unconventional Computation and Natural Computation. Springer-Verlag,2012:240-249.
[20] WENNINK M. Algorithmic support for automated planning boards[D]. Eindhoven,Netherlands:Technische Universiteit Eindhoven,1995.
[21] KURDI M. An effective new island model genetic algorithm for job shop scheduling problem[J]. Computers & Operations Research,2016,67:132-142.

基于块结构性质的花粉算法求解可重入作业车间调度问题

Flower Pollination Algorithm Based on Block Structure Properties for Reentrant Job Shop Scheduling Problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	章新杰, 汪路航, 郭孔辉, 刘阳, 金耿瑞, 姚全. 主动外倾前束悬架系统协同优化设计方法[J]. 机械工程学报, 2026, 62(8): 21-32.
[2]	陈俊杰, 唐禹洲, 杨树军, 邬明宇. 双层帘线增强空气弹簧橡胶气囊各向异性超-黏弹性本构模型[J]. 机械工程学报, 2026, 62(8): 49-59.
[3]	彭闪闪, 贺林, 徐子昂, 王铭哲, 魏宇江, 石琴. 无感线控转向阻力矩比积观测器与转角反步控制[J]. 机械工程学报, 2026, 62(8): 114-124.
[4]	熊璐, 胡旭歌, 吕浩然, 唐辰. 面向车辆运动控制的路面不平度识别综述[J]. 机械工程学报, 2026, 62(8): 139-156.
[5]	吴建洋, 王俊业, 杨波, 丁晓林, 刘欣, 张雷. 多轴重载分布式电驱动车辆全轮转向控制研究[J]. 机械工程学报, 2026, 62(8): 317-331.
[6]	肖跃, 贺宜, 张鸣. 基于分层式MPC的分布式四轮驱动车辆轨迹跟踪控制方法[J]. 机械工程学报, 2026, 62(8): 475-488.
[7]	王裕祥, 高阳, 蒋恩超, 董娜, 陈旭东, 彭凡, 王立闻. 基于GAF-MACNN的风机叶片健康状态监测方法[J]. 机械工程学报, 2026, 62(7): 139-149.
[8]	雷卓, 乔百杰, 王亚南, 杜军, 梁俊, 刘元是, 伏宇, 陈雪峰. 基于SPOQ正则项的叶端定时信号稀疏重构[J]. 机械工程学报, 2026, 62(7): 208-220.
[9]	郭文华, 汪科, 郑稳, 王玉忠, 徐晨, 冀千瑜, 冯祖仁. 电子枪偏转电压均值估计标定方法[J]. 机械工程学报, 2026, 62(7): 385-395.
[10]	刘俊杰, 张友超, 张厚超, 张兵, 许权, 朱晓阳, 兰红波. 基于电场驱动微3D打印增减材复合制造高精度铜基柔性透明电路[J]. 机械工程学报, 2026, 62(7): 427-438.
[11]	葛正辉, 王睿, 胡启凡, 朱永伟. 铝合金表面电化学毛化处理及其粘接性能研究[J]. 机械工程学报, 2026, 62(7): 462-477.
[12]	邵健, 何安瑞, 杨荃. 宽幅热轧带钢高效集约生产与质量精益管控研究进展[J]. 机械工程学报, 2026, 62(6): 1-28.
[13]	周强, 陆红红, 郭登刚, 陈鹏万, 王宝雨. 爆炸焊接+轧制制备TA2/TC4钛合金复合材料界面微结构及力学行为研究[J]. 机械工程学报, 2026, 62(6): 100-110.
[14]	束学道, 陈宇森, 王英, 代月晨, 左锦荣, 张庆东. 铝合金空心轴形孔同步成形协调机制与智能调控[J]. 机械工程学报, 2026, 62(6): 121-131.
[15]	原源, 刘秀成, 祁攀, 曹文博, 王峥鸿, 吴斌, 高翔. 基于磁致伸缩SH₀导波传感器换能曲线的表面硬度无损检测方法[J]. 机械工程学报, 2026, 62(6): 228-236.