【文章內(nèi)容簡介】 有任務所包括的操作順序是相同的即相當于具有相同 的工藝路線。若每臺機器對任務的加工順序都 相同 ,則退化為置換調(diào)度問題。單件車間作 業(yè)計劃問題是最一般的調(diào)度問題。包括多臺機器 ,每個任務包括多個操作 ,操作的順序不 盡相同。顯然 ,平行機調(diào)度問題和流水車間作業(yè)計劃問題均是單件車間作業(yè)計劃問題是特 例。 ..平行機調(diào)度問題模型 平行機問題是車間作業(yè)計劃問題的一個子集 ,是最為活躍的研究分支之一。一般平 行機問題可描述為 :給定機器集和工件集 ,。其中 ,機器數(shù)量 ,可以為同型機或同 類機 ,機器不存在準備時間即零時刻可用。各工件互相獨立 ,投放時間為零 ,不存在交 貨期約束。每個工件只包括一道加工工序。只需要在機器集中的 一臺機器上加工一次。 工件的加工遵從不搶占規(guī)則。要求將工件集 /分派到機器集上 ,并且確定加工次序 ,使 得某項目標達到最優(yōu)。 ..流水線車間作業(yè)模型 流水車間作業(yè)計劃一般可以描述為 :刀個工件在臺機器上加工 ,一個工件分為道 工序 ,每道工序要求不同的機器加工。刀個工件在臺機器上的加工順序是相同 ,工件 在機器 ,上的加工時間是給定的 ,設(shè)為甜 ,?,盯 。,?,。調(diào)度問 題的目標函數(shù)是求個工件的最優(yōu)加工順序 ,使最大流經(jīng)時間最小。 對流水線車間作業(yè)計劃問題常作如下假設(shè) : 每個工件在機器上的加工順序相同 ,且是確定的 。 每臺機 器在每個時刻只能加工某個工件的某道工序 。 一個工件不能同時在不同機器上加工 。 工序的準備時間與順序無關(guān) ,且包含在加工時間中。 ..單件車間作業(yè)計劃問題模型 單件車間作業(yè)計劃問題是一類與制造過程中實際生產(chǎn)調(diào)度密切相關(guān)的組合優(yōu)化問題。 許多具體的單件車間作業(yè)計劃問題都是通過對實際問題的分析和抽象 ,在基本的單件車間 作業(yè)計劃問題模型的基礎(chǔ)上提出來的。為研究單件車間作業(yè)計劃首先必須細致分析企業(yè)的 生產(chǎn)環(huán)境、生產(chǎn)過程及生產(chǎn)特點 ,從而建立起與企業(yè)實際生產(chǎn)過程、生產(chǎn)環(huán)境及生產(chǎn)特點 相適應的動態(tài)單件車間作業(yè)計劃模型。 經(jīng)典 的單件車間作業(yè)計劃問題的數(shù)學問題描述為 :設(shè)該系統(tǒng)生產(chǎn) ,個工件 ,表示為集 合 ,?,刀 ,生產(chǎn)系統(tǒng)內(nèi)有朋臺機器 ,表示為集合 ,?,聊 ,每個工件需要經(jīng)過碩士學位論文 第頁 武漢科技大學 若干個工序完成 ,若磕表示第個工件的射道工序在第臺機器上加工的工序 ,其開始加 工時間和需要加工的時間分別記為 %和 %。工件的最后一道工序的開始加工時間和需要 加工時間分別記為 amp。和砭。 。工件的投放時間和交貨期分別記為和西 。是工件有序工 序?qū)Α疽?,%】集合 ,其中 ,%優(yōu)先于 %。風是使用機器后的所有工序 %的集合。如果目標 函數(shù)為最小化最大完工 時間 ,或者最小生產(chǎn)周期 ,即如何安排加工使得加工所有工件的時 間最短。車間作業(yè)計劃問題采用整數(shù)線性規(guī)劃模型描述為 : ∈ . 朋瓦。 . ∈ . 『 ,∈ ,?他 ‰一歌≥ % 【 %,%】∈只 ,∈ 七∈ . %一歌≥‰或‰一‰≥‰ 【 %,%】∈墨 ∈ 七∈ ∈ ,?啊 . ,。≤ :嗽≤西一 其中 ,式 .表示工序順序約束 ,式 .表示資源約束 ,式 .表示投放時間和交貨 期約束。 對于上述經(jīng)典的車間作業(yè)計劃問題 ,除工藝約束之外 ,需要對工件、機器、加工時間 和緩沖器等還將引入的一些假設(shè)【】 : 對工件的假定包括 : 從加工過程開始起 ,工件即可被加工 ,或者 ,也可將此假設(shè)減弱為 ,對不同類 型的工件需要有一個固定的相應準備時間 ,經(jīng)過準備時間后即可開始加工 。 每一個操作限定為不能由多于一臺的機器來進行加工 。 每個操作一旦開始 ,直到完成為止 ,不會被另外的操作所中斷 。 不存在可選工藝路線即各個工件必須按照指定的工藝路線依次在機器上加工 。 各類工件之間不存在加工上的優(yōu)先數(shù) ,即對生產(chǎn)線而言 ,每類工件加工的重要 程度被認為是等同的 。 對每個操作均允許等待。也就是說 ,如果前一個操作還未完成即仍在進行 ,那 么后繼的操作將需要等待。這意味著 ,中間等待時間或者 庫存被認為是允許的 。 整個加工過程中 ,每個工件只能被一臺機器加工一次。 對機器的假定包括 : 在從加工過程開始的計劃時間內(nèi) ,所有臺機器均為有效的。也即 ,所有機器 從一開始就處于可加工狀態(tài) ,且在計劃時間內(nèi)不會出現(xiàn)損壞和需要修理的情況 。 在生產(chǎn)線中 ,只有一臺同一類型的機器 ,不用機器之間彼此獨立 。 在同一時刻 ,每臺機器只能從事一個操作 。 機器之外的其他資源無限制 。 對加工時間的假定包括 : 對每個操作 ,其作業(yè)時間是事前給出的 ,且在整個計劃時間內(nèi)保持為常數(shù) 。 除非特別說明 ,一般總認為 ,加工時間中已經(jīng)包括了設(shè)置時間 ,即已經(jīng)包括了第頁 武漢科技大學 碩士學位論文 工件在機器之間的傳送時間和裝卸時間 。 對緩沖器的假定包括 : 除非特別加以說明 ,緩沖器的容量均假設(shè)為充分大。 按照車間作業(yè)計劃問題的特點及分類 ,依據(jù)本文研究的對象單件訂貨型企業(yè)的車間級 作業(yè)調(diào)度 ,文中研究的車間作業(yè)計劃問題即是指開環(huán)動態(tài)基于調(diào)度性能的單件車間作業(yè)計 劃問題。 .車間作業(yè)計劃問題的求解策略 車間作業(yè)計劃問題屬于典型的組合優(yōu)化問題 ,雖然對該問題求解策略的研究已經(jīng)有幾 十年的歷史了 ,提出了一大批調(diào)度 算法 ,但至今尚未形成一套系統(tǒng)的理論和方法?？傮w來 說 ,這些算法可分為兩大類 :精確算法和近似算法。其中精確算法包括 :解析法、枚舉法。 近似算法包括 :構(gòu)造方法、鄰域搜索方法和人工智能方法。接下來將研究車間作業(yè)計劃問 題目前的若干求解方法 : 解析法。指針對簡單小規(guī)模調(diào)度問題的解析求解方法。 枚舉法。枚舉法是隱含枚舉整個空間的搜索方法 ,搜索效率低 ,但求解實際問題的 計算量太大。采用枚舉法 ,表達清晰 ,易于在計算機上求解 ,但生產(chǎn)環(huán)境具有很多不確定 性因素 ,存在建模不確定性和求解空間太大的問題 ,造成計算困難 ,特別是不能反 映特定 調(diào)度領(lǐng)域的自然結(jié)構(gòu) ,所以很難應用經(jīng)驗知識去處理調(diào)度問題。傳統(tǒng)的分支定界法【】 ,它是求解組合優(yōu)化問題的為數(shù)不多的有效方法之一。 構(gòu)造性方法。這類方法能夠快速構(gòu)造解 ,但優(yōu)化質(zhì)量一般較差。主要有移動瓶頸方 法、優(yōu)先規(guī)則方法【喊、插入方法等【’。移動瓶頸方法能夠取得較好的優(yōu)化質(zhì)量 ,但求 解過程和算法實施很復雜 ,且難以移植到其它類型的問題 ,同時相對其它方法而言比較難 理解。優(yōu)先規(guī)則調(diào)度是指系統(tǒng)運行時 ,根據(jù)一定的規(guī)則和策略來決定下一步操作的調(diào)度方 法。它是動態(tài)調(diào)度的典型 ,對于實際生產(chǎn)系統(tǒng)中 ,復雜的大規(guī)模的車間 作業(yè)計劃來說 ,具 有很大的優(yōu)越性。 人工智能方法。近年來 ,人工智能技術(shù)被引入生產(chǎn)調(diào)度領(lǐng)域 ,成為解決調(diào)度問題的 有效途徑 ,成為一個熱門課題。人工智能方法是采用人工智能研究領(lǐng)域提供的方法解決各 類生產(chǎn)調(diào)度問題方法的總稱。該類方法利用人工智能的原理和技術(shù)進行搜索 ,譬如將優(yōu)化 過程轉(zhuǎn)化為智能系統(tǒng)動態(tài)的演化過程 ,基于系統(tǒng)動態(tài)的演化來實現(xiàn)優(yōu)化。人工智能方法主 要包括專家系統(tǒng)方法、神經(jīng)網(wǎng)絡方法和蟻群系統(tǒng)等【也】。專家系統(tǒng)的方法通過收集操作人 員經(jīng)驗構(gòu)成數(shù)據(jù)庫 ,然后在線尋優(yōu)。這類方法構(gòu)成簡單 ,使用方便靈活 ,但經(jīng)驗的搜集往 往非常困難 ,很難覆蓋所有方面 ,同時由于一般難以量化 ,故該方法一般作為其他方法的 輔助。而神經(jīng)網(wǎng)路和蟻群系統(tǒng)等方法優(yōu)化時間性能較差 ,而優(yōu)化質(zhì)量嚴重依賴于網(wǎng)路參數(shù) , 甚至可能產(chǎn)生非法調(diào)度。 領(lǐng)域搜索方法。這類方法【從若干解出發(fā) ,對其領(lǐng)域的不斷搜索和當前解的替換第頁 碩士學位論文 武漢科技大學 來實現(xiàn)優(yōu)化。其中模擬退火方法、遺傳算法、禁忌搜索等方法能夠取得較滿意的優(yōu)化質(zhì)量 , 但其性能對算法參數(shù)有較強依賴性 ,且優(yōu)化時間通常較長 ,而簡單地將它們與優(yōu)先規(guī)則相 結(jié)合的混合方法對優(yōu)化質(zhì)量的改善程度比較有限。 因此 ,考慮到車 間作業(yè)計劃問題的復雜性和規(guī)模 ,目前最為實用而有效的算法仍然是 啟發(fā)式調(diào)度規(guī)則算法。它是動態(tài)調(diào)度的典型代表 ,它的優(yōu)點是直觀、簡單實用 ,且花 費的求解時間較少、易于實現(xiàn) ,這類算法雖然在調(diào)度解的優(yōu)化性能方面欠佳 ,但對于本文 的研究對象單件訂貨型企業(yè)這樣的動態(tài)、隨機、復雜的車間作業(yè)計劃問題而言 ,求解速度 快、容易得到滿意甚至近優(yōu)的調(diào)度解啟發(fā)式調(diào)度規(guī)則仍是目前的首選算法。啟發(fā)式調(diào)度規(guī) 則也稱為調(diào)度規(guī)則 ,分派規(guī)則、優(yōu)先規(guī)則。但是 ,啟發(fā)式調(diào)度規(guī)則具有全局敏感性 ,利用 不同的啟發(fā)式調(diào)度規(guī)則可產(chǎn)生不同的調(diào)度方案 ,而且規(guī)則在不 同的場合所起的作用也不相 同 ,調(diào)度系統(tǒng)的性能取決與啟發(fā)式調(diào)度規(guī)則的選擇。因此 ,在接下來將對啟發(fā)式調(diào)度規(guī)則 的性能進行分析。 .本章小結(jié) 本章給出車間作業(yè)計劃問題的研究的特點分類、提出三種不同的作業(yè)調(diào)度問題模型 , 給出了車間作業(yè)計劃的數(shù)學描述。對車間作業(yè)計劃問題現(xiàn)有的各種求解策略做了逐一的探 討 ,并在對比分析了不同的求解算法的基礎(chǔ)上 ,提出了啟發(fā)式調(diào)度規(guī)則在解決動態(tài)車間作 業(yè)計劃問題時的可行性。第頁 武漢科技大學 碩士學位論文 第三章啟發(fā)式調(diào)度規(guī)則及其調(diào)度算法設(shè)計 。對于強困難的調(diào)度問 車間作業(yè)調(diào)度問題是強困難 問題百 題 ,從實際系統(tǒng)的復雜性、規(guī)模性和可操作性角度考慮 ,啟發(fā)式調(diào)度規(guī)則仍然是目前最可 行和有效的求解方法。但是 ,啟發(fā)式調(diào)度