[發明專利]一種解決作業車間工藝瓶頸問題的算法

在審

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

1.一種解決作業車間工藝瓶頸問題的算法，本發明涉及調度領域，具體地涉及用算法解決作業車間工藝瓶頸問題，其特征是，包括如下步驟：

步驟1：識別瓶頸：瓶頸的識別方法如下：

步驟1.1：根據TOC原理確定瓶頸資源

步驟1.2：當需求超過能力時，排隊最長的機器就是瓶頸

步驟2：優化瓶頸：利用改進的帝國主義競爭算法優化車間瓶頸工藝加工的調度，具體流程如下：

步驟2.1：初始化社會國家數量

步驟2.2：利用改進的K_means算法對這些社會國家進行聚類，分出不同性質的國家群體，具體的，分出帝國主義國家，殖民地國家，具體方法如下：

1、初始化數據集，初始化采購商數據集國家數量集

2、選擇初始解，隨機產生一組中心解（一個帝國主義國家，一個殖民地國家）

3、聚類，把勢力相當的國家聚為一類，具體為：

（1）計算所有國家與中心國家的相異度

（2）如果相異度則第i個國家就聚到相應的c中心一類中

步驟2.3利用帝國主義競爭算法在不同類中進行調度，具體如下：

（1）初始化帝國主義競爭算法參數：初始化國家數量帝國主義國家殖民地國家

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

（3）計算帝國主義國家的勢力

（4）初始化帝國主義集團：根據帝國的勢力將不同數量的殖民地國家分配給帝國主義國家，帝國國家勢力越大，該帝國所擁有的殖民地國家就越多，帝國和它所擁有的殖民地組成一個帝國集團

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

（6）殖民地向所屬帝國移動：當帝國集團形成后，每個帝國集團中的帝國主義國家試圖增加其殖民地的數量，在ICA算法中，殖民地國家沿著指向其所屬帝國的方向靠近帝國

（7）帝國集團的競爭：帝國主義的競爭過程發生在帝國集團之間，因為每一個帝國集團都試圖占有其他帝國的殖民地并且控制他們，通過競爭使得強大的帝國集團更加強大，弱小的帝國集團更加弱小

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

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

（10）弱勢帝國的滅亡：在帝國競爭中，失去勢力的帝國集團將會滅亡，而且它所擁有的殖民地將被其他帝國集團所瓜分

（11）新帝國的產生：在帝國競爭中，會有新的帝國產生

（12）計算帝國存活率：用機器利用率來刻畫

（13）最后，保留最終剩余的帝國，即當前即將進行操作的工件。

2.根據權利要求1中所述的一種解決作業車間工藝瓶頸問題的算法，其特征是，以上所述步驟1中的具體計算過程如下：

步驟1：識別瓶頸：瓶頸的識別方法如下：

步驟1.1：根據TOC原理，建立以下模型： 且時，資源為瓶頸資源

步驟1.2：當需求超過能力時，排隊最長的機器就是瓶頸。

3.根據權利要求1中所述的一種解決作業車間工藝瓶頸問題的算法，其特征是，以上所述步驟2中的具體計算過程如下：

步驟2：優化瓶頸：利用改進的帝國主義競爭算法優化車間瓶頸工藝加工的調度，具體流程如下：

步驟2.1：初始化社會國家數量

步驟2.2：利用改進的K_means算法對這些社會國家進行聚類，分出不同性質的國家群體，具體的，分出帝國主義國家，殖民地國家，具體方法如下：

1.初始化數據集，初始化采購商數據集國家數量集

屬性(國家種類)數據集P，這里k=2

2.選擇初始解，隨機產生一組中心解（一個帝國主義國家，一個殖民地國家）

3.聚類，把勢力相當的國家聚為一類，具體為：

（1）計算所有國家與中心國家的相異度，相異度用勢力刻畫，在這里用作業車間工件工序的執行時間刻畫，第n個帝國主義國家的勢力大小定義為：

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

相異度：

其中，為任意國家的勢力，為中心國家的勢力

（2）如果則，第i個國家就聚到相應的c中心一類中

步驟2.3：利用帝國主義競爭算法在不同類中進行調度，具體如下：

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

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

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

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

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

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

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

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

式中，為第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次

（13）最后，保留最終剩余的帝國，即當前即將進行操作的工件。