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

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