一種解決作業車間調度問題的排產算法的製作方法
2023-10-09 12:36:49
本發明涉及作業車間調度技術領域。
背景技術：
作業車間調度問題(Job-shop Scheduling Problem)是許多實際生產調度問題的簡化模型，具有廣泛的應用背景，譬如生產製造、交通規則、郵電通信、大規模集成電路設計等問題。作為一類滿足任務配置和順序約束要求的分配問題，JSP已被證明是一個典型的NP_hard問題，它的求解難度遠遠大於流水線調度問題。針對解決作業車間調度問題的算法一直是學術界和工程界共同關注的重要課題。
製造業的競爭日趨激烈，企業正朝著有不同完工時間和產品要求的多類型、小批量、大批量的生產模式。如何利用現有資源，滿足加工任務所需各種約束，使所有任務能儘量按時完成，即如何有效地解決JSP問題，成為一個十分現實和緊迫的問題。高效的調度算法不可以大大提高生產效率和資源利用率，從而增強企業的競爭能力，因此對JSP的研究有非常重要的理論和現實意義。
鑑於作業車間調度問題的複雜性，一般都採用最優化方法和近似方法來解決作業車間調度方案的自動生成問題。
布穀鳥搜索(Cuckoo Search,CS)算法是一種新的現代啟發式算法，由劍橋大學Yang和拉曼工程學院Deb於2009年提出的。該算法基於某些布穀鳥種類的巢寄生繁育行為和鳥類、果蠅等的萊維飛行(Levy flight)行為特徵提出。布穀鳥搜索算法是模擬布穀鳥為尋找合適的產卵的鳥窩而隨機遊走的尋窩過程。
但是，已提出的這些算法都僅僅是解決最底層的作業調度問題，沒有考慮到實際生產過程中生產資源的調度是否存在衝突，生產資源是否充足，且沒考慮到工件試裝的問題。
技術實現要素：
針對現有技術存在的上述不足，本發明要解決的技術問題是提供一種改進的布穀鳥算法和新的排產算法。
本發明的目的是克服現有技術中存在的：車間調度問題中沒有考慮生產資源、工件試裝的調度問題。
本發明為實現上述目的所採用的技術方案是：一種解決作業車間調度問題的排產算法，該算法的步驟如下：
步驟1：編碼：採用基於工序的三維編碼規則編碼。
步驟2：選擇當前最優解：按照改進布穀鳥搜索算法選擇當前最優解。
步驟3：判斷當前最優解是否滿足試裝條件，若滿足，則執行試裝操作；否則轉步驟4。
步驟4：判斷當前所選工件(當前最優解)即將執行的工序是否滿足資源充足的條件，若滿足，轉步驟5，否則轉步驟2。
步驟5：確定最優解，輸出最優解，執行加工操作。
步驟6：循環，直到滿足終止條件。
本發明的有益效果是：
1、考慮了作業車間調度問題如何調度才能夠使資源合理利用。
2、提出了一種方法解決了某些作業在加工過程存在加工到一定程度需要試裝，只有試裝通過才可進行下一步的加工的調度問題。
3、提出一種方法解決了試裝拆分的複雜過程存在的難題。
附圖說明
圖1表示該排產算法流程圖
圖2表示改進的布穀鳥搜索算法流程圖
圖3表示生產過程中的試裝過程圖
具體實施方式
該發明提出的排產算法解決了實際生產過程中以下幾個問題：
(1)資源是否充足，這些資源的考慮包括工件原材料、加工工件所需設備、加工工具所需工具、場地、工人等。
(2)資源的調度存在衝突。
(3)工件加工過程中存在加工到一定程度要試裝，只有試裝通過才可進行下一步的加工。
(4)若干個小工件試裝成一個比較大的工件，這個大工件才進行它的工序加工，當加工到一定程度(沒有完成它的所有工序)，需要把它拆開，它的小零部件工件繼續回去加工該工件還沒加工的工序，待達到一定條件以後，又組裝工件，然後繼續加工該工件所需後續工序。依次道理循環操作，直到滿足終止條件的問題，此類問題結合圖3表述如下：
工件3由工件1和工件2組裝而成，工件1有5個工序需要加工，工件2有9個工序需要加工。首先加工工件1到第5個工序，加工工件2到第4個工序，把工件1和工件2組裝起來(此過程在機械生產過程中稱為試裝)得到工件3；然後加工工件3到第2個工序，拆分工件3；接下來加工工件1的第6，第7個工序，加工工件2的第5，第6，第7個工序，完成了以後，又把工件1和工件2組裝起來得到工件3；然後加工工件3的第3，第4，第5道工序，完成了以後，拆分；工件1所有工序已經完成，這時加工工件2的第8，第9道工序，完成了以後，把工件1和工件組裝起來得到工件3。這時整個加工過程完成。
本發明解決上述問題，採用一種解決作業車間調度問題的排產算法，結合圖1到圖3，算法具體實施過程如下所述：
步驟1：首先確定編碼規則。在求解jsp問題是採用基於工序的編碼規則，即染色體由w×n×m個基因組成，他們表示一個工序的排列，在這個工序排列中每個工件號最多出現m次，其染色體是由一個二維空間點(x,y)表示，即第x個訂單的第y個工件。例如，3×4×3(訂單(或階數)×工件×機器)的實例，染色體序列為(1,1)(1,2)(2,1)(1,1)(3,1)(3,1)(3,3)(3,2)(1,2)(1,2)(1,1)(1,4)。那麼，它對應的工件加工序列為：
(J1，1，1，J1，2，1，J2，1，1，J1，1，2，J3，1，1，J3，1，2，J3，3，1，J3，2，1，J1，2，1，J1，2，2，J1，1，3，J1，4，1，)
其中，Jti，j表示第t個訂單的第i個工件的第j道工序，j表示工件i出現的次數。因此，上面例子的染色體序列表達的意思是先加工順序為：第1個訂單的第1個工件的第1道工序，加工第1個訂單第2個工件的第1道工序，在加工第2個訂單第1個工件的第1道工序，加工第1個訂單第1個工件的第2道工序，以此類推，最後加工第1個訂單第4個工件的第1道工序。因此在解碼時就可以按照工件的出現順序轉化為一個調度方案。
步驟2：選擇當前最優解：按照改進布穀鳥搜索算法選擇當前最優解。
步驟3：判斷當前最優解是否滿足試裝條件，若滿足，則執行試裝操作；否則轉步驟4。
步驟4：判斷當前所選工件(當前最優解)即將執行的工序是否滿足資源充足的條件，若滿足，轉步驟5，否則轉步驟2。
步驟5：確定最優解，輸出最優解，執行加工操作。
步驟6：循環，直到滿足終止條件。
一、所述步驟4工件所需資源是否充足的判定規則如下：
設置資源庫存池：
判定規則：
If(庫存池存在所需設備&&庫存該設備數量>＝所需該設備數量&&庫存池存在所需工具&&庫存該工具數量>＝所需該工具數量&&庫存池存在所需工種工人&&庫存該工人數量>＝所需該工人數量)滿足資源充足條件；
Else不滿足資源充足條件。
二、所述步驟2改進的布穀鳥搜索算法如下：
步驟2.1：初始化算法基本參數：設置鳥窩個數(工件數量)n,宿主發現外來鳥蛋的概率Pa(作業搶佔概率)，以及最大迭代次數MaxT或搜索精度ε。
步驟2.2：初始化鳥窩位置(工件加工完成時間)：根據加工時間長短呈上升趨勢排列。
步驟2.3：計算目標函數值：按照編碼規則將鳥窩位置(完成時間)轉換為工序排列，計算各鳥窩位置對應的目標函數值，並獲得當前最優鳥窩位置。具體實現為：
目標函數：
f(C)＝min max1≤o≤w{max1≤k≤m{max1≤i≤nCoik}} (1)
約束條件：
Coik-poik+M(1-aoihk)≥Coih
(o＝1，2，…，w；i＝1，2，…，n；h，k＝1，2，…，m) (2)
Cojk-Coik+M(1-xoijk)≥poik
(i，j＝1，2，…，n；o＝1，2，…，w；k＝1，2，…，m) (3)
Coik≥0(o＝1，2，…，w；i＝1，2，…，n；k＝1，2，…，m) (4)
xoijk＝0或1(i，j＝1，2，…，n；o＝1，2，…，w；k＝1，2，…，m) (5)
其中，式(1)表示目標函數，即完成時間(Makespan)；式(2)表示工藝約束條件決定的每個工件的操作的先後順序；式(3)表示加工每個工件的每臺機器的先後順序；式(4)表示完工時間變量約束條件；式(5)表示變量可能的取值大小。上述公式中所涉及的符號定義含義如下：Coik和poik分別為第o個訂單(或階數)中的第i個工件在機器k上的完成時間點和加工時間長度；M是一個足夠大的整數；aoihk和xoijk分別為指示係數和指示變量，其含義為：
步驟2.4：更新鳥窩位置：開始迭代，保留上代最優鳥窩位置不變，更新鳥窩位置(即全局搜索)，從而隨機產生下一代鳥窩，並評估位置更新後每個鳥窩的目標函數值，記錄當前最優鳥窩位置。具體實施方案如下數學公式所示：
其中，表示第i只布穀鳥在第t代的鳥窩位置(在車間調度問題中用Coik表示)，α是步長大小參數，一般取α＝0.1。參數S是隨機遊動的步長，計算公式如下：
S＝u+α·σ (9)
其中，
在局部搜索時對每一鳥窩位置按條件進行更新：用一個隨機數Ra作為鳥窩主人發現外來鳥蛋的概率並與Pa進行比較，若Ra>Pa，則隨機改變鳥窩位置，否則保持原來位置不變,並計算位置移動後每個鳥窩的目標函數值，記錄當前最優鳥窩位置。用如下0-1規劃模型表示：
步驟2.5：更新最優函數值：比較本次迭代和上一次迭代鳥窩位置的最優值，如果新的最優值小於原最優值，則把新的最優值賦予當前最優鳥窩位置的目標函數值。
步驟2.6：當到達最大搜索次數或滿足搜索精度時轉入步驟7，否則，轉3進行下一次搜索。
步驟2.7：輸出最優調度值和對應的調度方案(染色體序列)。