針對可重入作業(yè)車間調度問題(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)編碼規(guī)則,將花粉算法的實數矢量個體轉變?yōu)榕帕惺噶?使其可對問題解空間進行全局搜索,以發(fā)現存在優(yōu)質解的區(qū)域。然后,定義8種鄰域結構,并基于最大費用流問題特性分析塊結構內部性質,得到前4種鄰域結構能改進TWT的判定條件,可用于避免對無效區(qū)域的搜索,進而提出融合多種鄰域的高效局部搜索,對全局搜索發(fā)現的優(yōu)質解區(qū)域進行細致搜索。試驗和算法比較驗證FPA_BSP的有效性。提出...

【文章頁數】：13 頁

【部分圖文】：

圖1222的RJSSP的析取圖表1222的RJSSP(“—”表示不在相應的機器上加工)

集合；RO為重入工序的集合；TOnmr為總的工序數，虛擬工序0的開始加工時間和加工時間設定為零；A為合取弧集合，合取弧描述同一個工件工藝路線的順序約束，為單向；U為尾弧，描述每個工件最后一個工序指向虛擬節(jié)點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