車間作業(yè)調(diào)度算法初步研究

《車間作業(yè)調(diào)度算法初步研究》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、一種車間作業(yè)調(diào)度算法的初步研究摘要：車間作業(yè)調(diào)度是MES的核心模塊，直接關(guān)系著企業(yè)的經(jīng)營、生產(chǎn)和管理效率,冇效的調(diào)度方案能最人限度地降低生產(chǎn)成木，提高企業(yè)競爭力。車間作業(yè)調(diào)度問題也是一種典型的組合優(yōu)化問題，關(guān)于它的研究具有很大的現(xiàn)實意義,也有一定的理論意義。論文介紹一種基于規(guī)則的優(yōu)化調(diào)度算法，以相對剩余工吋最長為條件或調(diào)度規(guī)則,進行優(yōu)化調(diào)度操作。關(guān)鍵詞：MES,不間作業(yè)調(diào)度，調(diào)度規(guī)則，相對剩余工時Abstract:TheworkshopschedulingmanagementisthecoremoduleofMES,whichgreatlyaffectstheefficiency,operat

2、ionandmanagementofworkshop.Effectiveschedulingcanreduceproductioncostandenhanceenterprisecompetitiveness.Theworkshopschedulingisatypicalcombinatorialoptimizationproblem?Ithasbothpracticalsignificanceandtheoreticalvalueforstudyingit.Thepaperintroducesarule-basedoptimizationalgorithm,withtheIongestdur

3、ationasaconditionofrelativerestorschedulingrulestooptimizetheschedulingoperations.Keywords:MES,Job-shopscheduling,Schedulingrules,Remainingduration1引言目前，在離散型制造企業(yè)中，多采用小批量、單件、多品種為生產(chǎn)方式，而單件車間調(diào)度問題是一個代表性的作業(yè)調(diào)度問題。關(guān)于單件車間的調(diào)度問題，目前的研究的成果也較多，比如遺傳算法、神經(jīng)網(wǎng)絡(luò)方法和分支定界法等。在理論上這些方法的探索較多，并且對小規(guī)模的調(diào)度與應(yīng)用效果較好。但是，由于車間調(diào)度問題的復(fù)雜性，當(dāng)工件

4、數(shù)量與機器數(shù)量都比較多的情況下，上述算法在PC上運行的時間比較長，工程實際中的應(yīng)用也不太理想。在業(yè)界基于啟發(fā)式規(guī)則的調(diào)度算法被公認(rèn)為最具有工程實用價值，所謂規(guī)則調(diào)度是安裝一定的準(zhǔn)則對加工的設(shè)備和加工的任務(wù)進行優(yōu)先級的排序。目前，投入使用的調(diào)度系統(tǒng)大多采用規(guī)則調(diào)度算法。啟發(fā)式優(yōu)先分配的方法有較小的時間復(fù)雜性和容易實現(xiàn)的特點，因而在實際求解調(diào)度問題中經(jīng)常使用這個方法。而規(guī)則調(diào)度算法的關(guān)鍵問題是要選擇好優(yōu)先分配的規(guī)則，本文將剩余工期最大且工期較短作為分配的規(guī)則。2調(diào)度規(guī)則車間作業(yè)調(diào)度問題(Job-ShopSchedulingProblem,JSSP)是一個典型組合優(yōu)化的問題。所謂組合優(yōu)化問題，就是指

5、從組合問題的可行解集合中尋找最優(yōu)解。此問題有三個基本的要素，即變量、約束和目標(biāo)函數(shù)。例如在實際調(diào)度過程中，對工序的加工排序以及對相應(yīng)設(shè)備的選擇都是調(diào)度過程中的變量，工序的工藝路線以及其相互間的關(guān)系都是對變量的約束，作業(yè)調(diào)度的目標(biāo)有加工總時間最短、設(shè)備利用率最高、工件按期交貨等。關(guān)于在加臺設(shè)備上加工72個工件的調(diào)度問題，最有效的方法之一是按優(yōu)先規(guī)則進行排序。以某些方式評價各競爭工序是優(yōu)先規(guī)則的目的，從而方便在加工設(shè)備空閑的情況下，可以確定下一個需要調(diào)度執(zhí)行的工序。此方法不僅可以簡化排序的過程、減少工作量和提高排序的速度，而且能夠給出比較優(yōu)的方案。2.1描述問題的變量關(guān)于車間作業(yè)調(diào)度問題可以描述為

6、，"個不同的工件和加臺不同的機器，每一個工件都是由一個或多道工序組成的工序集合，并且同一工件工序的順序是給定的，在工件所要求的機器和固定的工期下,完成每一個工序。機器與工件間的約束有，某一個工序開始之后不能被中斷、屬于不同工件的工序沒有先后開工的約束，某個機器最早開工時間及實際已經(jīng)下達的加工工序的結(jié)束時間會影響工序的最早開工時間、每一臺機器同時只能加工一個工件或被一個工件使用。在描述問題的時候，用到的變量有，m-機器的數(shù)量、n-任務(wù)的數(shù)量、任務(wù)叱所包含的工序的數(shù)目、叱廠表示任務(wù)必的第丿道工序、Cfj-在調(diào)度階段乙工序必）的完工日期、S[j-在調(diào)度階段t，工序“°?的開工日期、T-調(diào)度的總階段數(shù)

7、,其等于工序的總數(shù)量nxm、厶廠工序叱）的工期丄訂=?廠S’Dfj?工序必）對應(yīng)的任務(wù)i在調(diào)度階段t的完工時間、TGt-機器i需要加工的任務(wù)集合，匸1,2,…,m、EB「任務(wù)i最早的可能開工日期、G〔-在階段/,對機器K形成競爭的可以調(diào)度的工序集合、0G〔-在階段r,與喙相對應(yīng)的已經(jīng)調(diào)度的工序的集合。2.2描述調(diào)度算法的定義根據(jù)算法實現(xiàn)的基本思想，可以作出幾個定義：定義1.如果工序B后于a加工，B