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

发布时间：2024-04-12 05:55

　　针对可重入作业车间调度问题(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的有效性。提出...

【文章页数】：13 页

【部分图文】：

图1222的RJSSP的析取图表1222的RJSSP(“—”表示不在相应的机器上加工)

集合；RO为重入工序的集合；TOnmr为总的工序数，虚拟工序0的开始加工时间和加工时间设定为零；A为合取弧集合，合取弧描述同一个工件工艺路线的顺序约束，为单向；U为尾弧，描述每个工件最后一个工序指向虚拟节点0，为单向；E为析取弧集合，描述在同一台机器上加工工序的前后关系，在调度之....

3操作图7、8中工序1、7、9、2、10、8是机器1M上

4操作图10、11中工序6、2、10、3、11、8是机器1M

5操作图13、14中工序2、9、6、10、4、7是机器1M

3INS3,11,8操作之后。图103INS3,11,8操作之前图113INS3,11,8操作之后②邻域结构4：4INS,,。不满足式(25)时，将和插入到前，在之前。11iiiipFJpFJpFJ111iiiiFJFJpFJp(25)如图12所示，表示一个块结构上的6个工序，工....

本文编号：3951767