[發明專利]一種基于構造型啟發式算法的流水車間生產線調度方法

無效

• 申請號: 201210068836.6
• 申請日: 2012-03-16
• 公開（公告）號: CN102621951A
• 公開（公告）日: 2012-08-01
• 發明（設計）人: 唐聃;舒紅平;劉奎;羅飛;曹亮
• 申請（專利權）人: 成都信息工程學院
• 主分類號: G05B19/418
• 分類號: G05B19/418
• 代理公司: 成都賽恩斯知識產權代理事務所(普通合伙) 51212
• 代理人: 朱月仙

技術領域

本發明涉及自動控制與信息技術領域，尤其涉及一種基于構造型啟發式算法的流水車間生產線調度方法。

背景技術

流水車間生產線調度是制造企業生產過程中非常重要的問題，良好的調度策略將極大的提高生產效率。總完工時間(makespan)是調度過程中一個非常重要的性能指標，總完工時間最小可使得資源更加有效利用、任務更迅速傳遞及在制品庫存最小。目前的流水車間生產線調度方法分為兩種類型，一種為窮舉法，如動態規劃法、分支定界法等，雖然可以對工件的加工順序得到最優的調度，但是這些方法的搜索空間會隨著工件數量的增加呈指數式急劇增長，計算復雜度高，對機器硬件的要求較高，難以應用在大規模的流水車間生產線調度上；另一種方法為啟發式算法，包括元啟發式算法與構造型啟發式算法，目前提出的構造型啟發式算法如(1)Palmer算法——Palmer?D?S.Sequencing?Jobs?through?a?Multi-Stage?Process?in?the?Minimum?Total?Time-a?Quick?Method?of?Obtaining?a?near?Optimum[J].Operational?Research?Quarterly，1965，16：101-107；(2)Gupta算法——Gupta?J.A?Functional?Heuristic?Algorithm?for?the?Flowshop?Scheduling?Problem[J].Operational?Research?Quarterly，1971，22：39-47；(3)CDS算法——Campbell?H?G，Dudek?R?A，Smith?M?L.A?Heuristic?Algorithm?for?the?n-Job，m-Machine?Scheduling?Problem.[J].Management?Science，1970，16：630-637；(4)RA算法——Dannenbring?D?G.An?Evaluation?of?Flow?Shop?Sequencing?Heuristics[J].Management?Science，1977，23(11)：1174-1182；(5)NEH算法——Nawaz?M，Enscore?E，Ham?I.A?Heuristic?Algorithm?for?the?m?Machine，n?Job?Flow?Shop[J].OMEGA：The?International?Journal?of?Management?Sciences，1983，11(1)：91-95等，以上幾種構造型啟發式算法中以NEH算法的性能最佳。然而，NEH算法在實現過程中需要通過多次計算擬定工件序列的總完工時間并進行比較，因此，計算復雜度將遠大于其他構造型啟發式算法。

發明內容

針對現有技術存在的問題，本發明的主要目的在于提供一種具有較高的調度性能，同時計算復雜度較低的基于構造型啟發式算法的流水車間生產線調度方法。

為實現上述目的，本發明提供一種基于構造型啟發式算法的流水車間生產線調度方法的實施例，該方法包括如下步驟：

S1、若n個工件在m臺機器上加工，設p_i，j為第j個工件在第i臺機器上的執行時間，構成矩陣P，其中i＝1，2，Λ，m；j＝1，2，Λ，n，工件之間的初始排序為π′＝[P₁，P₂...P_j...P_n]，工件之間的最終排序為π，π初始為空；

S2、定義其中1≤i＜j≤n，1≤u＜v≤m；

S3、判斷是否存在R(P_i，P_j)＝1或0，若存在，則進入步驟S31；否則，進入步驟S32；

S31、判斷R(P_i，P_j)＝1是否成立，若成立，則將P_i的加工順序置于P_j之前，同時將P_i，P_j加入π中，并從π′中刪除，若不成立，則將P_j的加工順序置于P_i之前，同時將P_j，P_i加入π中，并從π′中刪除；

S313、從π′中取出一列P_k；