作業(yè)車間調(diào)度ppt課件

.,車間調(diào)度問題,.,主要內(nèi)容,一、研究背景和意義二、國內(nèi)外研究現(xiàn)狀三、車間調(diào)度問題的概述四、車間調(diào)度問題的研究方法五、作業(yè)車間調(diào)度問題5.1柔性作業(yè)車間調(diào)度問題5.2不確定性作業(yè)車間調(diào)度問題5.2.1模糊作業(yè)車間調(diào)度問題5.2.2隨機(jī)作業(yè)車間調(diào)度問題5.3動態(tài)作業(yè)車間調(diào)度問題六、車間調(diào)度問題存在的問題七、車間調(diào)度問題的發(fā)展趨勢致謝,.,一、研究的背景和意義,背景：企業(yè)間的激烈競爭，市場需求和顧客需求的多樣化生產(chǎn)規(guī)模大型化和生產(chǎn)過程連續(xù)化車間調(diào)度已成為生產(chǎn)過程的關(guān)鍵瓶頸之一意義：生產(chǎn)作業(yè)調(diào)度問題的研究對于有效的優(yōu)化企業(yè)生產(chǎn)資源配置，縮短產(chǎn)品加工時(shí)間，降低產(chǎn)品生產(chǎn)成本，提高企業(yè)生產(chǎn)效率等研究有著重要的實(shí)際應(yīng)用價(jià)值。車間作業(yè)調(diào)度問題的研究對推動企業(yè)生產(chǎn)調(diào)度管理的發(fā)展，提升我國制造業(yè)的競爭力具有重大意義。,.,二、國內(nèi)外研究狀況,自從1954年Johnson發(fā)表了兩臺機(jī)床流水車間調(diào)度問題以來，已有2000多篇論文被發(fā)表。工業(yè)調(diào)度問題為以后的研究奠定了堅(jiān)實(shí)的基礎(chǔ)。多數(shù)研究的是單目標(biāo)的、靜態(tài)的調(diào)度。目前對動態(tài)的、柔性的、不確定性的、多目標(biāo)的調(diào)度研究越來越多。國內(nèi)外學(xué)者采用了很多種算法解決了很多種類型的車輛調(diào)度問題。,.,三、車間調(diào)度問題的概述,3.1車間調(diào)度問題的描述3.2車間調(diào)度問題的特點(diǎn)3.3車間調(diào)度問題的分類,.,3.1車間調(diào)度問題的描述,車間調(diào)度問題就是對一個可用的制造資源集在時(shí)間上進(jìn)行加工任務(wù)(加工工件)集的分配，將作業(yè)(加工操作)均衡地安排到各機(jī)器，并合理地安排作業(yè)的加工次序和開始時(shí)間，同時(shí)優(yōu)化一些性能指標(biāo)，在執(zhí)行這些作業(yè)或者任務(wù)時(shí)需要滿足某些限制條件，如作業(yè)的到達(dá)時(shí)間、完工的限定時(shí)間、作業(yè)的加工順序、資源對加工時(shí)間的影響等。從數(shù)學(xué)規(guī)劃的角度看，車間調(diào)度問題可表達(dá)為在等式或不等式約束下，對一個或多個目標(biāo)函數(shù)的優(yōu)化。,.,3.2車間調(diào)度問題的特點(diǎn),復(fù)雜性：NP難題；問題規(guī)模大動態(tài)隨機(jī)性：作業(yè)時(shí)間不準(zhǔn)確；工件隨機(jī)到達(dá)；設(shè)備問題（突發(fā)）；交貨期改變等。多目標(biāo)性：(1)基于作業(yè)交貨期的目標(biāo)(2)基于作業(yè)完成時(shí)間的目標(biāo)(3)基于生產(chǎn)成本的目標(biāo)多約束性：資源的數(shù)量、緩存的數(shù)量、工件的加工時(shí)間和加工順序等。,.,3.3車間調(diào)度問題的分類,根據(jù)加工系統(tǒng)的復(fù)雜程度可分為：單機(jī)、多臺并行機(jī)、FlowShop、OpenShop和JobShop。根據(jù)性能指標(biāo)分為：基于調(diào)度成本調(diào)度問題和基于調(diào)度性能調(diào)度問題根據(jù)生產(chǎn)環(huán)境的特點(diǎn)分為：確定性車間調(diào)度和不確定性車間調(diào)度問題根據(jù)作業(yè)的加工特點(diǎn)分為：靜態(tài)車間調(diào)度和動態(tài)車間調(diào)度,.,四、車間調(diào)度問題的研究方法,4.1精確求解方法4.2近似求解方法,.,4.1精確求解方法,1.數(shù)學(xué)方法整數(shù)規(guī)劃混合整數(shù)規(guī)劃分解方法拉格朗日松弛法2.分支定界法Balas在1969年提出基于析取圖的枚舉算法是最早應(yīng)用于求解調(diào)度問題的分支定界方法。,.,4.2近似求解方法,1.構(gòu)造性方法優(yōu)先分配規(guī)則法基于瓶頸的啟發(fā)式方法插入方法2.人工智能方法神經(jīng)網(wǎng)絡(luò)專家系統(tǒng)3元啟發(fā)式算法基于生物啟發(fā)的群體算法：遺傳算法、粒子群優(yōu)化算法和蟻群算法局部搜索算法：禁忌搜索算法、模擬退火算法和多起點(diǎn)局部搜索,.,五、作業(yè)車間調(diào)度問題,5.1柔性作業(yè)車間調(diào)度問題5.2不確定性作業(yè)車間調(diào)度問題5.3動態(tài)作業(yè)車間調(diào)度問題,.,五、作業(yè)車間調(diào)度問題,描述：Jobshop調(diào)度問題研究n個工件在m臺機(jī)器上的加工過程，Oijr表示工件i的第j道工序在機(jī)器r上加工，相應(yīng)的操作時(shí)間tij為已知，事先給定各工件在各機(jī)器上的加工次序（稱為技術(shù)約束條件），要求確定與技術(shù)約束條件相容的各機(jī)器上所有工件的加工次序，使加工性能指標(biāo)達(dá)到最優(yōu)。約束條件：每個機(jī)器在同一時(shí)刻只能加工一個工件；每個工件只能在一臺機(jī)器上加工；每個工件的工序加工先后次序是預(yù)先給定的，不同的工序之間沒有順序約束；操作一旦開始就不能中途停止；,.,解的表式方法：甘特圖和析取圖（1）甘特圖,.,（2）析取圖,.,調(diào)度性能指標(biāo)：(1)基于完成時(shí)間的指標(biāo)(2)基于交貨期的指標(biāo)(3)基于成本的指標(biāo)生產(chǎn)成本在制品存儲成本拖期懲罰成本成品存儲成本(4)基于設(shè)備負(fù)荷的指標(biāo)最大負(fù)荷設(shè)備總負(fù)荷,.,5.1柔性作業(yè)車間調(diào)度問題,描述：假定車間有m臺機(jī)器和n個需加工工件，每個工件包含s道工序，工件的工序順序是預(yù)先確定的，每道工序可以在多臺不同的機(jī)器上加工，工序的加工時(shí)間隨機(jī)器的性能不同而不同。調(diào)度目標(biāo)是為每道工序選擇最合適的機(jī)器，以及確定各機(jī)器上所有工件的加工次序，得到一種具有最優(yōu)性能指標(biāo)的調(diào)度方案。特征：FJSP問題區(qū)別于經(jīng)典JSP問題的最大特征就是工序調(diào)度前需要首先為工序分配設(shè)備。分為機(jī)器分配問題和工序調(diào)度問題。（1）允許某道工序在多臺機(jī)器上加工；（2）一臺機(jī)器可以加工多種類型的工序。,.,柔性的含義：操作柔性：就是同一個操作（工序）可以在不同的機(jī)器上運(yùn)行。順序柔性：在滿足拓?fù)渑判虻那疤嵯拢谔幚磉^程中操作可以選擇不同的處理順序。處理柔性：要完成某段加工過程，可以選擇不同的操作組合及其加工順序的組合。,.,求解方法：,（1）分步法：分步求解FJSP中的機(jī)器分配和工序調(diào)度兩個子問題的方法1993年，Brandimarte首次采用分步法求解多目標(biāo)FJSP問題，他先用分派規(guī)則法求解機(jī)器分配問題，然后利用禁忌搜索法求解工序調(diào)度問題。2005年，夏蔚軍等采用微粒群優(yōu)化法和模擬退火法集成的思想求解多目標(biāo)FJSP問題:用效用函數(shù)法把多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題，用微粒群優(yōu)化法求解機(jī)器分配問題，用模擬退火法求解工序調(diào)度問題。,.,（2）集成法：是指同時(shí)求解FJsP的機(jī)器分配問題和工序調(diào)度問題的方法。1997年Dauzere-peres等人定義了鄰域結(jié)構(gòu)方法不區(qū)分分配問題和調(diào)度問題并且基于該鄰域結(jié)構(gòu)提出了禁忌搜索過程求解FJSP。2000年，趙偉等人研究了JobShop類型柔性制造系統(tǒng)的調(diào)度問題，其中每個工件都有多個可替代的工藝計(jì)劃，并且每個操作均可在多個機(jī)器上選擇加工，建立了多目標(biāo)混合整數(shù)規(guī)劃模型，利用遺傳算法進(jìn)行求解。Mati等采用貪婪算法、Loukil和Maqrini等采用模擬退火算法同時(shí)求解FJSP的機(jī)器分配和工序調(diào)度兩個子問題。,.,5.2不確定性作業(yè)車間調(diào)度問題,5.2.1模糊作業(yè)車間調(diào)度問題5.2.2隨機(jī)作業(yè)車間調(diào)度問題,.,5.2.1模糊作業(yè)車間調(diào)度問題,描述：n個工件在m臺機(jī)器上加工，每個工件包含由多道工序組成的一個工序集合，以及一個與客戶滿意度相關(guān)聯(lián)的模糊交貨期，每道工序有一個模糊加工時(shí)間；要求在一定的調(diào)度目標(biāo)下，保證工件交貨期和滿足工藝約束條件下，找出在各機(jī)器上工件工序的加工順序，即找到一種可行的調(diào)度方案。約束條件：每個機(jī)器在同一時(shí)刻只能加工一個工件；每個工件同一時(shí)刻只能在體態(tài)機(jī)器上加工；工件有預(yù)先確定的加工順序，不同的工序之間沒有順序約束；操作一旦開始就不能中途停止。,.,模糊調(diào)度的三個階段：模糊交貨期Ishii等人第一次提出交貨期的模糊化，并對開環(huán)車間中的雙機(jī)調(diào)度和同型機(jī)調(diào)度兩個難題進(jìn)行了研究模糊加工時(shí)間（1）王成堯等人研究了多個工件迭加的聯(lián)合隸屬函數(shù)所對應(yīng)的性質(zhì)，并根據(jù)這些性質(zhì)研究了一種單機(jī)模糊加工時(shí)間的調(diào)度模型；（2）唐國春等人就模糊加工時(shí)間排序問題進(jìn)行了詳盡的研究。綜合考慮模糊加工時(shí)間與模糊交貨期MasatoshiSakawa較早研究了同時(shí)考慮模糊加工時(shí)間和交貨期窗口的JobShop調(diào)度，并采用三角模糊數(shù)對模糊加工時(shí)間、模糊懲罰函數(shù)等問題進(jìn)行了分析。,.,模糊調(diào)度的研究方法：經(jīng)典分派規(guī)則的直接模糊化方法基于模糊排序的模糊調(diào)度基于啟發(fā)式近似算法的模糊調(diào)度模糊JSP調(diào)度研究存在的問題及其發(fā)展趨勢：在針對模糊JSP建模過程中，大量簡化真實(shí)實(shí)驗(yàn)環(huán)境和參數(shù)，不能很好解決實(shí)際問題。大多數(shù)對模糊JSP問題的研究，僅將目標(biāo)設(shè)置為加工時(shí)間和交貨期上，但是實(shí)際上，決策者對比如生產(chǎn)效率、成本、利潤等問題更為關(guān)心，所以對于多目標(biāo)車間作業(yè)調(diào)度問題的研究將會是未來研究的一個重要方向；隨著社會需求越來越高，生產(chǎn)過程中不確定因素越來越多，因此動態(tài)模糊JSP在未來會越來越重要。,.,5.2.2隨機(jī)作業(yè)車間調(diào)度問題,特征：加工時(shí)間、交貨期時(shí)間等都是隨機(jī)變量已有成果：1991年，GhoshWells研究了單機(jī)環(huán)境下隨機(jī)加工時(shí)間和交貨期的調(diào)度問題，目標(biāo)是最小化加權(quán)延遲工件的數(shù)量、1999年，LuhpeterB等人考慮了加工時(shí)間、到達(dá)時(shí)間,交貨期為離散隨機(jī)變量的JobShop模型,采用Lagrangian松弛法將機(jī)器能力約束松弛,問題分解為多個獨(dú)立的工件層子問題,再將技術(shù)約束條件松弛,問題分解為多個獨(dú)立的工序?qū)幼訂栴},然后利用動態(tài)規(guī)劃的方法進(jìn)行了求解。2003年，Yoshitomi與Yamaguchi考慮加工時(shí)間隨機(jī)的車間調(diào)度問題，并設(shè)計(jì)適合隨機(jī)優(yōu)化的遺傳算法進(jìn)行求解。2005年，Tavakkoli-Moghaddam建立了加工時(shí)間為隨機(jī)變量,機(jī)器的作業(yè)成本和閑置成本作為目標(biāo)函數(shù)的非線性規(guī)劃模型,并采用基于神經(jīng)網(wǎng)絡(luò)和模擬退火的混合算法進(jìn)行求解。2007年，朱顥和唐萬生求解了加工時(shí)間為連續(xù)隨機(jī)變量的加工車間調(diào)度問題。,.,5.3動態(tài)作業(yè)車間調(diào)度問題,特點(diǎn)：(l)能在線產(chǎn)生實(shí)時(shí)調(diào)度;(2)對隨機(jī)擾動能在線識別，并快速重新調(diào)度。動態(tài)調(diào)度的需求：（1）在普通訂單和急件訂單并存條件下，具有常規(guī)的動態(tài)調(diào)度與協(xié)調(diào)能力。（2）針對車間生產(chǎn)復(fù)雜性和動態(tài)性的特點(diǎn)，具有處理異常事件和隨機(jī)事件的動態(tài)調(diào)度能力動態(tài)調(diào)度分類：（1）自適應(yīng)調(diào)度（2）實(shí)時(shí)調(diào)度（3）在線調(diào)度,.,求解方法：(l)仿真方法(2)人工智能方法(3)滾動窗口再調(diào)度方法動態(tài)調(diào)度策略：(l)事件驅(qū)動調(diào)度策略(2)周期性驅(qū)動調(diào)度策略(3)周期性驅(qū)動與事件驅(qū)動的混合調(diào)度策略,.,已有成果：Matsuura提出的重調(diào)度算法，首先用分支定界法產(chǎn)生一個調(diào)度，當(dāng)工況發(fā)生變化時(shí)再用調(diào)度規(guī)則來分配工件。Abumizar等提出一種重調(diào)度算法，當(dāng)擾動發(fā)生時(shí)，不是全部重新調(diào)度，也不是等擾動解除后再繼續(xù)原調(diào)度，而是僅僅重新調(diào)度那些直接或間接受擾動影響的工件，從而減少了由于擾動引起的生產(chǎn)周期的增加。武漢科技大學(xué)機(jī)械自動化學(xué)院的熊禾根等人提出一類考慮工序相關(guān)性的、工件批量到達(dá)的動態(tài)Jobshop調(diào)度問題。基于ISIS開發(fā)的OPIS是現(xiàn)有的基于知識的車間調(diào)度系統(tǒng)中最成熟的系統(tǒng)之一，它根據(jù)情況使用而向資源或面