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

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