[發明專利]基于混合集合蛙跳與變鄰域算法的平行機調度方法及系統

有效

• 申請號: 201710440182.8
• 申請日: 2017-06-12
• 公開（公告）號: CN107102552B
• 公開（公告）日: 2018-03-09
• 發明（設計）人: 劉心報;裴軍;孔敏;陸少軍;錢曉飛;周志平
• 申請（專利權）人: 合肥工業大學
• 主分類號: G05B13/04
• 分類號: G05B13/04
• 代理公司: 北京路浩知識產權代理有限公司11002
• 代理人: 王瑩

技術領域

本發明涉及供應鏈技術領域，具體涉及一種基于混合集合蛙跳與變鄰域算法的平行機調度方法及系統。

背景技術

現有技術中提出了一些關于批處理機工件的調度問題的一些解決方案。以下進行簡要說明：

(1)批調度相關：Li等人研究了一類不相關平行批處理機工件加工問題。基于問題復雜性的考慮，他們提出了基于BFLPT的啟發式算法解決該問題。

具體參見Li X,HuangYL,Tan Q,et al.Scheduling unrelatedparallel batch processing machines with non-identical job sizes.Computers&Operations Research,2013,40(12):2983-2990.

(2)工件惡化相關：Wang等人研究了一類工件加工時間隨著其開始加工時間非線性增加的生產調度問題。基于問題性質，他們提出了用于解決該問題的最優算法以及啟發式算法。

具體參見Wang,J.,Wang,M.,2012.Single-machine scheduling with nonlineardeterioration.OptimizationLetters 6,87-98.

(3)元啟發式算法相關：Eusuff等人于2003年受到自然界青蛙捕捉食物的過程的啟發，提出了集合蛙跳算法。該算法的一般步驟為:

步驟一、初始化青蛙種群；

步驟二、依據每個個體的適應度值，將整個種群分為若干組；

步驟三、每組進行局部搜索；

步驟四、將分散的各組集合起來；

步驟五、判斷終止條件是否達到，若為達到則轉到步驟二。

該算法的優勢在于集合操作可以使得在每次迭代時各個個體能進行一定的信息交流，增強了算法的尋優能力。

具體參見Eusuff,M.M.,Lansey,K.E.,2003.Optimization of Water Distribution Network Design Using the Shuffled Frog Leaping Algorithm.Journal ofWaterResources Planning&Management 129,210-225。

在對相關技術進行研究的過程中，發明人發現：在傳統的批調度的研究中，工件時間都是一個確定的值，工件的惡化效應很少被考慮。此外，在傳統的集合蛙跳算法中，局部搜索類似于粒子群算法中的粒子的遷移策略，收斂精度低且容易陷入局部最優，不能有效地解決離散組合優化問題。這樣導致調度不夠合理。

發明內容

本發明實施例的一個目的在于提高批處理機工件的過程中調度的合理性。

第一方面，本發明實施例提供了一種基于混合集合蛙跳與變鄰域算法的多個不相關平行批處理機的協同制造方法，包括：

步驟1、輸入每個工件在每個機器上的一般加工時間，初始化算法參數，包括種群規模N，劃分的組數S，當前迭代次數L，RVNS算法最大迭代次數U_max，最大迭代次數L_max，并設置L＝1；

步驟2、初始化種群內各個青蛙的位置，記所述種群為其中表示第L代種群P^(L)中的第i個個體，表示個體在第j個維度上的位置，表示對應的工件，i＝1,2,…N，j＝1,2,…n；

步驟3、計算種群P^(L)中每個個體的適應度值；

步驟4、按照適應度值將種群平均劃分為S個組，記所述各組集合為表示上述集合中的第s個組，表示組中的第l個個體，s＝1,2,…S，l＝1,2,…(N/S)，設置s＝1；

步驟5、計算組中的最優與最差個體，分別記為和隨機選擇組的一個個體作為RVNS算法的初始解，設置u＝1；

步驟6、判斷u≤U_max是否成立，若成立，則轉到步驟9；

步驟7、隨機產生一個的第一類鄰域個體X_1，判斷X_1是否優于若成立，則將X_1賦給將u+1賦給u，轉到步驟5；否則，轉到步驟8；

步驟8、隨機產生一個的第二類鄰域個體X_2，判斷X_2是否優于若成立，則將X_2賦給將u+1賦給u，轉到步驟5；否則，轉到步驟9；

步驟9、隨機產生一個的第三類鄰域個體X_3，判斷X_3是否優于若成立，則將X_3賦給將u+1賦給u，轉到步驟5；否則，轉到步驟10；