[發明專利]一種改良的帝國主義競爭算法求解作業車間調度問題

在審

• 申請號: 201610169626.4
• 申請日: 2016-03-22
• 公開（公告）號: CN106611235A
• 公開（公告）日: 2017-05-03
• 發明（設計）人: 姜艾佳;胡成華
• 申請（專利權）人: 四川用聯信息技術有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種改良的帝國主義競爭算法求解作業車間調度問題，本發明涉及作業車間調度領域，具體地涉及用算法求解作業車間調度問題，其特征是：該算法的步驟如下：

步驟1：初始化帝國主義競爭算法參數：初始化國家數量 、帝國主義國家、殖民地國家，其中，帝國主義國家用機器來表示，殖民地國家用作業來表示：

；

步驟2：計算帝國的相對勢力：用機器處理作業能力來刻畫：

其中，Ncn表示所有有可能等待某臺機器Mn處理的作業數量，Mcn表示可以處理這Ncn個作業的機器數量；

步驟3：計算帝國主義國家的勢力：第n個帝國主義國家的勢力大小定義為：

式中，為第i項作業的在第n臺機器的運行時間，即代價值；

步驟4：初始化帝國主義集團：根據帝國的勢力將不同數量的殖民地國家分配給帝國主義國家，帝國國家勢力越大，該帝國所擁有的殖民地國家就越多，帝國和它所擁有的殖民地組成一個帝國集團，在車間調度問題中，帝國所擁有的殖民地等于該機器實際處理的作業數，因此，殖民地分配方法按式：

式中，代表第n個帝國所擁有的殖民地；

步驟5：計算帝國集團的總勢力：一個帝國集團的總勢力包括兩部分，一部分為帝國主義國家的勢力，另一部分為它所擁有的殖民地國家的勢力，在這兩部分中，帝國主義國家的勢力對勢力有更大的影響，因此，一個帝國的總勢力計算方式如下：

式中，為第n個帝國集團的總代價函數值，為第n個帝國主義國家的代價函數值，為帝國集團的殖民地的代價函數值，即車間調度問題中作業的在某臺機器的運行時間，，是個實數，一般情況下取；

步驟6：殖民地向所屬帝國移動：當帝國集團形成后，每個帝國集團中的帝國主義國家試圖增加其殖民地的數量，在ICA算法中，殖民地國家沿著指向其所屬帝國的方向靠近帝國，在該過程中，部分國家會產生革命，即殖民地隨機的發生位置上的改變，殖民地向其所屬帝國靠近方式如下：

為了使殖民地從各個方向向其所屬帝國移動，增強帝國到達全局最優的收斂性，設立兩個服從于正態分布的隨機參數：

式中，d是殖民地與帝國之間的距離，是一個大于1的數，會使殖民地國家從四面八方向其所屬帝國移動，一般取；

步驟7：帝國集團的競爭：帝國主義的競爭過程發生在帝國集團之間，因為每一個帝國集團都試圖占有其他帝國的殖民地并且控制他們，通過競爭使得強大的帝國集團更加強大，弱小的帝國集團更加弱小，在ICA算法中，最弱帝國集團中的最弱一個殖民地國家將被其他帝國集團通過競爭去占有，每一個帝國集團都有可能占有最弱的國家，這種可能性的大小由下式定義得到：

式中，為第n個帝國集團的相對代價函數值，定義如下：

向量P：

向量R是與向量P相同規格的向量：

向量D由以下得到：

在向量D中最大的元素所對應的帝國集團將會占有上述最弱的殖民地國家；

步驟8：殖民地國家的滅亡：在帝國的侵犯過程中，存在殖民地國家滅亡，

在車間調度問題中，殖民地滅亡即表示訂單處理完畢或是暫停操作，此時，殖民地數目會減少：

k為消亡的殖民地數量,e為社會進化第e次；

步驟9：新殖民地國家的產生：在社會進化過程中，會有新的殖民地產生，

在車間調度問題中，新殖民地的產生極為訂單的增加，此時，殖民地數目會增加：

h為增加的殖民地數量，e為社會進化第e次；

步驟10：弱勢帝國的滅亡：在帝國競爭中，失去勢力的帝國集團將會滅亡，而且它所擁有的殖民地將被其他帝國集團所瓜分，在車間調度問題中，機器故障、機器完工都可用帝國的滅亡來表示，帝國滅亡，則帝國數目減少：

l為減少的帝國數量，e為社會進化第e次；

步驟11：新帝國的產生：在帝國競爭中，會有新的帝國產生，在車間調度問題中，增加新機器即為新帝國的產生：

g為新增的帝國數量，e為社會進化第e次；

步驟12：計算帝國存活率：用機器利用率來刻畫，如下定義：

e為社會進化第e次。