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

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