范營營，劉海彬，趙博選，張 培

(西安交通大學(xué) 制造系統(tǒng)與質(zhì)量工程研究所，陜西 西安 710049)

基于多任務(wù)的車間生產(chǎn)調(diào)度算法的研究

范營營，劉海彬，趙博選，張 培

(西安交通大學(xué) 制造系統(tǒng)與質(zhì)量工程研究所，陜西 西安 710049)

為解決因中國機(jī)械制造業(yè)約95%的企業(yè)的生產(chǎn)類型為多品種小批量而引出的調(diào)度難題，設(shè)計(jì)了以啟發(fā)式算法為主的柔性車間調(diào)度算法，該算法對(duì)于多工藝路線的加工工件，以工件的加工相似性來劃分不同單元，以負(fù)荷平衡為依據(jù)來確定工藝路線，以緊迫系數(shù)為優(yōu)先規(guī)則來保證交貨期。該調(diào)度算法不僅考慮到車間負(fù)荷等問題，而且提供了減少設(shè)備空閑時(shí)間的優(yōu)化算法，對(duì)資源的優(yōu)化配置和科學(xué)運(yùn)作起到舉足輕重的作用。成功實(shí)現(xiàn)了“在有限的資源條件下，使加工作業(yè)任務(wù)在合理的時(shí)間內(nèi)加工完成”，縮短了產(chǎn)品在車間的流動(dòng)時(shí)間，減少了在制品庫存，在保證交貨期的前提下最大限度地提高了資源利用率，使派工層面科學(xué)化、正規(guī)化。

生產(chǎn)調(diào)度；柔性車間；啟發(fā)式

隨著企業(yè)信息化水平的不斷提高，在CMIS基礎(chǔ)上發(fā)展起來的制造執(zhí)行系統(tǒng)在計(jì)劃排產(chǎn)方面起到了核心作用。在傳統(tǒng)的生產(chǎn)系統(tǒng)中，生產(chǎn)過程存在著許多問題，如生產(chǎn)過程穩(wěn)定性差、缺乏柔性等，這些問題導(dǎo)致生產(chǎn)過程中的反應(yīng)弧過大，造成產(chǎn)品堆積、生產(chǎn)效率低下等情況的發(fā)生。MES(Manufacturing Execution System)作為企業(yè)資源計(jì)劃和自動(dòng)控制之間的面向制造過程的集成車間生產(chǎn)管理控制系統(tǒng)，它的信息及時(shí)性應(yīng)該能夠較好地適應(yīng)生產(chǎn)運(yùn)行變化迅速這一情況。提高企業(yè)生產(chǎn)調(diào)度的科學(xué)性和車間運(yùn)作的信息化水平，對(duì)企業(yè)發(fā)展不僅具有客觀的現(xiàn)實(shí)價(jià)值，而且還具有巨大和深遠(yuǎn)的理論意義。

1 算法研究

1.1柔性車間調(diào)度問題的描述

產(chǎn)品的工藝路線柔性主要體現(xiàn)在2個(gè)方面：一是加工工藝的柔性，產(chǎn)品的某些部分可以選用不同的加工工藝進(jìn)行實(shí)現(xiàn)，而不同的加工工藝所需要經(jīng)過的工序種類是不同的，這也可根據(jù)車間的實(shí)際生產(chǎn)狀況動(dòng)態(tài)抉擇； 二是工序的柔性，產(chǎn)品的某道工序可以在多臺(tái)設(shè)備上加工完成，可以根據(jù)實(shí)際情況動(dòng)態(tài)選擇。

1.2總算法流程及實(shí)例說明

在零件存在多工藝路線、工序存在多可選設(shè)備的基礎(chǔ)上，綜合考慮加工時(shí)間、加工順序、生產(chǎn)批量、設(shè)備能力、任務(wù)交貨期等實(shí)際生產(chǎn)約束條件，以最短加工時(shí)間、最佳設(shè)備及單元平衡、最少跨單元加工等作為優(yōu)化目標(biāo)，提出了單元構(gòu)建技術(shù)與啟發(fā)式算法相結(jié)合的混合算法。如圖1所示。

圖1 總算法流程

第1步：初始設(shè)備單元?jiǎng)澐帧?/p>

利用數(shù)學(xué)方法進(jìn)行對(duì)象的分類，利用設(shè)備之間的相似性系數(shù)表達(dá)零件工藝路線之間的相似性，把多種實(shí)際因素?fù)Q算為兩個(gè)機(jī)床的相似性系數(shù)，最后進(jìn)行計(jì)算，然后選取相似性系數(shù)的最大值，將相似值最大的兩個(gè)機(jī)床分到一個(gè)單元，反復(fù)迭代，直到把機(jī)床劃分完畢為止。

第2步：每個(gè)零件的工藝路線選擇和設(shè)備分配。

僅僅考慮零件加工路線的相似性是不夠的，還要考慮綜合工序、設(shè)備、任務(wù)等各方面因素，為此采用基于規(guī)則的啟發(fā)式優(yōu)化算法，兼顧工序的任務(wù)交貨期和設(shè)備能力等實(shí)際約束條件，利用啟發(fā)式算法，對(duì)多工藝工件的工藝路線進(jìn)行選擇，實(shí)現(xiàn)設(shè)備資源的優(yōu)化分配。過程如圖2所示。

圖2 選擇工藝與設(shè)備算法

第3步：每臺(tái)設(shè)備上的任務(wù)排序。

對(duì)設(shè)備的工序任務(wù)排序要考慮所有調(diào)度工序的最早開工日期，并且按工序的工藝路線來進(jìn)行順序調(diào)度。從問題本質(zhì)的角度，此算法考慮了工序的順序約束。例如在每個(gè)調(diào)度階段，優(yōu)先加工緊迫系數(shù)最小的任務(wù)的工序，從而達(dá)到盡量不延長流程時(shí)間的目的，整體上獲得最優(yōu)或者高質(zhì)量的近似最優(yōu)解。算法流程如圖3所示。

圖3 任務(wù)排序算法

緊迫系數(shù)是指用交付期減去當(dāng)前日期的差值除以任務(wù)的剩余加工時(shí)間，用CR表示，當(dāng)CR等于1表示加工時(shí)間剛好夠用，大于1表示加工時(shí)間富裕，小于1表示已經(jīng)拖期。當(dāng)一個(gè)作業(yè)完成后，其余作業(yè)的CR值會(huì)有變化，應(yīng)隨時(shí)調(diào)整。緊迫系數(shù)越小，其優(yōu)先級(jí)越高，故緊迫系數(shù)最小的任務(wù)先進(jìn)行加工。

第4步：優(yōu)化排序。

步驟1：遍歷所有設(shè)備，找出加工時(shí)間最長的設(shè)備。

步騾2：對(duì)該設(shè)備，遍歷其所有的工序任務(wù)隊(duì)列的加工開始時(shí)間、加工時(shí)間、加工結(jié)束時(shí)間，若所有的設(shè)備在各個(gè)工序段的間隔時(shí)間均為零，則排序結(jié)果不可調(diào)節(jié)，轉(zhuǎn)入步驟5。

步驟3：找到第一個(gè)開始前空閑時(shí)間不為零的工序P(i)，若為首工序，則直接設(shè)W為零，否則轉(zhuǎn)入步驟4。

步驟4：設(shè)P(K)在該設(shè)備上的前一加工任務(wù)為P(i)，后一加工任務(wù)為P(j)。若P(j-1)的完工時(shí)間TF(j-1)小于P(K)的開始時(shí)間TS(K)，且max{TF(j)，TS(j-1)} +Tj+TK≤TS(K+1)，則交換P(K)與P(j)在該設(shè)備上的加工順序，令TS(j)=max{TF(j)，TF(j-1)}，進(jìn)入步驟5；否則暫時(shí)置W=0，轉(zhuǎn)步驟1。

其中：P(K)表示工序K的工序名稱；TS(K)表示工序K的加工開始時(shí)間；TF(K)表示工序K的加工結(jié)束時(shí)間；TK表示工序K的加工工時(shí)。

步驟5：更新隊(duì)列，重新遍歷，恢復(fù)前面所有暫時(shí)置等待時(shí)間為零的工序的等待時(shí)間在置零前的值，找出有新的空閑時(shí)間的設(shè)備，轉(zhuǎn)步驟2，否則結(jié)果不可調(diào)節(jié)，算法結(jié)束。

第5步：檢驗(yàn)交貨期。

檢驗(yàn)是否滿足交貨期，若不滿足則設(shè)備加班，或者利用外協(xié)幫助。

1.3程序運(yùn)行示例

在Windows 2007平臺(tái)上利用VS2010工具，以SQL2008為數(shù)據(jù)庫，通過C#編程實(shí)現(xiàn)了以上算法，并結(jié)合某企業(yè)生產(chǎn)數(shù)據(jù)(見表1)進(jìn)行試用。以多工藝路線的零件為示例的程序生成結(jié)果如圖4所示。該示例可以描述為已知幾個(gè)工件的多個(gè)工藝路線，通過上述的算法求解由設(shè)備資源構(gòu)成的制造單元，并把調(diào)度結(jié)果以甘特圖形式展示出來。

2 結(jié)束語

總之，隨著企業(yè)信息化的深入，作業(yè)車間的計(jì)劃調(diào)度問題的研究也取得了長足的進(jìn)步，各種方法和理論應(yīng)運(yùn)而生。作業(yè)調(diào)度算法作為MES的核心，在很大程度上考慮了柔性車間遇到的各種因素，實(shí)用性較強(qiáng)，為現(xiàn)行的企業(yè)車間生產(chǎn)管理提供了很多的方法，未來必將為我國現(xiàn)行的企業(yè)生產(chǎn)管理提供行之有效的策略。

表1 某企業(yè)工件數(shù)據(jù)表

圖4 調(diào)度結(jié)果甘特圖

[1] 王愛民，丁國智，寧汝新．制造單元快速構(gòu)建技術(shù)研究[J]．北京理工大學(xué)學(xué)報(bào)，2006，26(10)：851-854.

[2] Yin Y,Yasuda K．Manufacturing cells' design in consideration of various production factors[J]．International Journal of Production Research，2002，40(4)：885-906.

[3] 王風(fēng)儒，徐蔚文，徐洪副．用效率調(diào)度算法求解非標(biāo)準(zhǔn)作業(yè)車間調(diào)度問題[J]．計(jì)算機(jī)集成制造，2007，7(7)：13-15.

[4] 盛伯浩，羅振璧，趙宏林，等．快速重組制造系統(tǒng)(RRMS)——新一代制造系統(tǒng)的原理及應(yīng)用[J]．制造技術(shù)與機(jī)床, 2001(8):37-43.

[5] 王偉玲．離散型制造企業(yè)車間生產(chǎn)調(diào)度與控制系統(tǒng)的研究與開發(fā)[D]．沈陽：沈陽工業(yè)大學(xué)，2005.

[6] 桂歡歡．基于MES的車間生產(chǎn)調(diào)度系統(tǒng)研究[D]．南昌：南昌大學(xué)，2007.

[7] 劉艷麗，劉希玉．啟發(fā)式算法在計(jì)劃排產(chǎn)中的應(yīng)用[J]．計(jì)算機(jī)技術(shù)與發(fā)展，2008，18(3)：222-224.

TheSchedulingAlgorithmofWorkshopBasedonMulti-task

FAN Yingying, LIU Haibin, ZHAO Boxuan, ZHANG Pei

(Xi'an Jiaotong University, Shaanxi Xi'an, 710049, China)

In view of flexible workshop scheduling algorithm for the Chinese 95% machinery enterprises with small batch scheduling problem, it presents the heuristic algorithm for multi-process routes workpiece. Dividing into different units to the workpiece based on similarity, it determines the load balancing process route, ensures delivery to the urgency factor based on precedence rules. This algorithm not only takes into account issues such as shop load, but also provides optimization algorithms to reduce the idle time of equipment for optimal allocation of resources. Its goal is "under conditions of limited resources, so that the processing operations task processing is completed within a reasonable time". The application shows that the algorithm can reduce in-process inventory, maximize the resource utilization under the premise of guaranteed delivery, solve the problem of human intervention.

Production Scheduling; Flexible Workshop; Heuristic Algorithm

10.3969/j.issn.2095-509X.2014.03.013

2013-11-19

國家高技術(shù)發(fā)展計(jì)劃資助項(xiàng)目(2012AA040907)

范營營(1985—)，女，河北威縣人，西安交通大學(xué)碩士研究生，專業(yè)方向?yàn)闄C(jī)械制造及其自動(dòng)化。

THl8;TP39

A

2095-509X(2014)03-0049-03