針對可重入作業(yè)車間調(diào)度問題(Reentrant job shop scheduling problem, RJSSP),提出一種基于塊結(jié)構(gòu)性質(zhì)的花粉算法(Flower pollination algorithm based on block structure properties,FPA_BSP),用于最小化總加權(quán)延誤時間(Totalweighted tardiness, TWT)。首先,建立RJSSP基于析取圖的數(shù)學模型,并證明在確定析取弧方向后,該模型的對偶模型為最大費用流問題模型。其次,設(shè)計擴展RSOV (Reentrant-smallest-order-value, RSOV)編碼規(guī)則,將花粉算法的實數(shù)矢量個體轉(zhuǎn)變?yōu)榕帕惺噶?使其可對問題解空間進行全局搜索,以發(fā)現(xiàn)存在優(yōu)質(zhì)解的區(qū)域。然后,定義8種鄰域結(jié)構(gòu),并基于最大費用流問題特性分析塊結(jié)構(gòu)內(nèi)部性質(zhì),得到前4種鄰域結(jié)構(gòu)能改進TWT的判定條件,可用于避免對無效區(qū)域的搜索,進而提出融合多種鄰域的高效局部搜索,對全局搜索發(fā)現(xiàn)的優(yōu)質(zhì)解區(qū)域進行細致搜索。試驗和算法比較驗證FPA_BSP的有效性。提出...

【文章頁數(shù)】：13 頁

【部分圖文】：

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

集合；RO為重入工序的集合；TOnmr為總的工序數(shù)，虛擬工序0的開始加工時間和加工時間設(shè)定為零；A為合取弧集合，合取弧描述同一個工件工藝路線的順序約束，為單向；U為尾弧，描述每個工件最后一個工序指向虛擬節(jié)點0，為單向；E為析取弧集合，描述在同一臺機器上加工工序的前后關(guān)系，在調(diào)度之....

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操作之后②鄰域結(jié)構(gòu)4：4INS,,。不滿足式(25)時，將和插入到前，在之前。11iiiipFJpFJpFJ111iiiiFJFJpFJp(25)如圖12所示，表示一個塊結(jié)構(gòu)上的6個工序，工....

本文編號：3951767