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

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.

参考文献

[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]. 机械工程学报, 2024, 60(20): 1-23.
[2]	傅杨, 张跃, 毛颖, 唐小华, 陈祖高, 徐和武, 杨雨沛, 高斌, 田贵云. 基于Feature Boosting的管道电磁内检测多传感信号缺陷解析算法[J]. 机械工程学报, 2024, 60(20): 51-67.
[3]	吴洁, 沈以赴, 黄国强. 2024铝合金填丝TIG焊接头搅拌摩擦加工组织和性能研究[J]. 机械工程学报, 2024, 60(20): 153-161.
[4]	张志勇, 王宇翔, 黄彩霞, 吴悠, 杜荣华. 融合灰色预测和卡尔曼滤波的车辆侧向碰撞预警[J]. 机械工程学报, 2024, 60(20): 240-250.
[5]	廖贵文, 张毅, 魏凯, 刘小君, 王伟. 受限润滑界面液固二相流场结构与颗粒运动行为耦合特性分析[J]. 机械工程学报, 2024, 60(20): 351-360.
[6]	王旭, 姜兴宇, 杨国哲, 孙猛, 于沈弘, 毕凯航, 赵日铮, 刘伟军. 基于PSO-SSA的激光清洗装备人机界面布局优化研究[J]. 机械工程学报, 2024, 60(20): 372-387.
[7]	王德祥, 张宇, 江京亮, 刘新福, 刘国梁. 离子液基和棕榈油基纳米流体在镍基高温合金微量润滑磨削界面的摩擦学机理研究[J]. 机械工程学报, 2024, 60(19): 159-171.
[8]	李浦, 逯代兴. 协同仿真算法研究综述[J]. 机械工程学报, 2024, 60(19): 172-186.
[9]	王晓宇, 魏兆成, 王学勤, 王栋. 整体叶轮双列开槽五轴插铣加工的残留材料建模[J]. 机械工程学报, 2024, 60(19): 310-317.
[10]	王高见, 刘丽, 康丹丹, 叶延洪, 邓德安. Ni含量对高速列车转向架耐候钢焊缝金属微观组织、力学性能及腐蚀行为的影响[J]. 机械工程学报, 2024, 60(18): 163-172.
[11]	张明康, 师文庆, 徐梅珍, 王迪, 陈杰. 隐式曲面多孔结构压缩性能与流体压降性能研究[J]. 机械工程学报, 2024, 60(18): 394-406.
[12]	马伟佳, 朱小龙, 刘青瑶, 段星光, 李长胜. 人工智能在机器人辅助手术中的应用[J]. 机械工程学报, 2024, 60(17): 22-39.
[13]	袁小庆, 吴涛, 原勋, 王文东. 基于GSO-RF意图识别算法的全身助力外骨骼控制方法研究[J]. 机械工程学报, 2024, 60(17): 91-101.
[14]	张禹泽, 赵竞夫, 赵振伟, 康荣杰, 戴建生, 宋智斌. 面向多关节训练的并联柔索驱动下肢康复机器人设计与分析[J]. 机械工程学报, 2024, 60(17): 111-122.
[15]	梁旭, 张建勇, 李国涛, 苏婷婷, 何广平, 侯增广. 面向骨折复位手术的冗余并联机构：设计、建模与性能分析[J]. 机械工程学报, 2024, 60(17): 133-146.