[發明專利]一種基于二維平面區域距的算法解決作業車間調度問題

在審

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

1.一種基于二維平面區域距的算法解決作業車間調度問題，本發明涉及作業

車間調度領域，具體地涉及用算法求解作業車間調度問題，其特征是：該算法的步驟如下：

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

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

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

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

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

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

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

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

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

步驟6：計算帝國地理位置占有優勢：采用基于可拓學的點到區域的距來衡量兩個帝國占有同一個殖民地的優勢的大小，占有優勢越大的帝國越有機會侵占該殖民地

步驟7：殖民地歸屬的確定: 殖民地的歸屬性質由帝國集團勢力和帝國地理位置占有優勢這兩部分因素確定

步驟8：殖民地向所屬帝國移動：當帝國集團形成后，殖民地國家沿著指向其所屬帝國的方向靠近帝國，在該過程中，部分國家會產生革命，即殖民地隨機的發生位置上的改變，殖民地向其所屬帝國靠近方式如下：

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

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

步驟9：帝國集團之間的戰爭：帝國主義的競爭過程發生在帝國集團之間，因為每一個帝國集團都試圖占有其他帝國的殖民地并且控制他們，帝國集團之間的這種戰爭，采用可拓學中任意一個點關于兩個區域的位置值來衡量

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

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

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

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

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

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

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

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

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

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

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

e為社會進化第e次.

步驟15：最后，保留最終剩余的帝國，將適應度值作為最優解。

2.根據權利要求1所述的一種基于二維平面區域距的算法解決作業車間調度問

題，其特征是：該算法的創新點為步驟6、步驟7和步驟9，具體如下：

步驟6：計算帝國地理位置占有優勢：采用基于可拓學的點到區域的距來衡量兩個帝國占有同一個殖民地的優勢的大小，占有優勢越大的帝國越有機會侵占該殖民地，具體求解過程如下：

帝國國家和殖民地國家的位置關系表示為如圖2

對于任意一個殖民地的歸屬，需要通過計算距離殖民地最近的兩個帝國集團的侵占優勢的大小來確定，優勢大的帝國有權擁有該殖民地，優勢相對小的殖民地將失去該殖民地，優勢的大小用可拓學中點到平面區域的距來衡量，可拓學中的點到平面的距綜述：

定義1：設，為平面區域D中任意二點，稱

為與之距

定義2：設與區域D之距為

在帝國主義競爭算法中，為殖民地的位置，D為帝國集團的勢力范圍

步驟7：殖民地歸屬的確定: 殖民地的歸屬性質由帝國集團勢力和帝國地理位置占有優勢這兩部分因素確定，具體求解過程如下：

（1）分別計算殖民地到帝國集團和的距：

（2）計算歸屬系數：

其中，為勢力優勢影響參數，一般的

（3）判斷歸屬性質：那個歸屬性質大，殖民地M就歸屬于那個帝國集團，即若，則殖民地M歸屬于帝國集團；若，則殖民地M歸屬于帝國集團

步驟9：帝國集團之間的戰爭，帝國集團之間的這種戰爭，采用可拓學中任意一個點關于兩個區域的位置值來衡量，可拓學中任意一個點關于兩個區域的位置值綜述：

定義3：設區域與區域之距為

定義4：若，稱

為M關于與D的位置值，稱為位值

在帝國主義競爭算法中，不存在帝國集團包含帝國集團的情況，即不存

在或的情況，故在任意一個殖民地（已被侵占和未被侵占）關于區域與區域的位置計算為：

其中，

表示殖民地M已被帝國集團侵占，它已經是改期過其中一員表示殖民地M未被帝國集團侵占

如果S>0，則被侵占的可能性要大，否則，被侵占的可能性要大。