• CN:11-2187/TH
  • ISSN:0577-6686

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

• 交叉与前沿 • 上一篇    

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

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

  1. 昆明理工大学信息工程与自动化学院 昆明 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   

  1. 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

摘要: 针对可重入作业车间调度问题(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

中图分类号: