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

在審

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

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

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

步驟1.1：根據TOC原理判斷瓶頸資源

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

步驟2：優化瓶頸：利用一種基于K_means算法優化車間瓶頸工藝加工的調度，具體流程如下：

步驟2.1：初始化算法參數：初始個體（作業工序）數量機器數量K，

步驟2.2：初始化聚類，具體如下：

隨機選取K個工序作為聚類中心

以這K個工序作為中心點，計算工序群體中每個工序與這K個工序的相異度，相異度用作業的操作時間來刻畫

聚類

步驟2.3：利用線性規劃對這K個聚類中心進行全局最優判定

步驟3：得到滿意結果或迭代次數達到一定值，輸出最優解，算法結束，否則，以當前聚類的平均值作為中心，返回步驟2.2。

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

步驟2：優化瓶頸：利用一種基于K_means算法優化車間瓶頸工藝加工的調度，具體流程如下：

步驟2.1：初始化算法參數：初始個體（作業工序）數量，機器數量K

步驟2.2：初始化聚類，具體如下：

（1）隨機選取K個工序作為聚類中心

（2）以這K個工序作為中心點，計算工序群體中每個工序與這K個工序的相異度，相異度用作業的操作時間來刻畫，具體為：

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

相異度：

其中，為任意工序的代價，為中心工序的代價

（3）聚類如果則，第i個工序就聚到相應的c中心一類中，這時得到K

步驟2.3：利用線性規劃對這K個聚類中心進行全局最優判定，具體如下：

目標函數：

約束條件：

其中，式（1）表示目標函數，即完成時間（Makespan）；式（2）表示工藝約束條件決定的每個工件的操作的先后順序；式（3）表示加工每個工件的每臺機器的先后順序；式（4）表示完工時間變量約束條件；式（5）表示變量可能的取值大小，上述公式中所涉及的符號定義含義如下：分別為第o個訂單（或階數）中的第i個工件在機器k上的完成時間點和加工時間長度；M是一個足夠大的整數；分別為指示系數和指示變量，其含義為：

式（6）表示第o個訂單的所有工件最大完成時間小于訂單周期的時間約束

步驟2.4：如果的結果滿意，則輸出當前中心點作為當前時間決策方，否則，以當前聚類的平均值作為中心，返回步驟2.2。