JobShop生產計劃與調度的集成建模和優化綜述

劉思成+王艷紅

摘 要：制造業的核心是生產管理技術，而如何制定好生產計劃與調度也正是生產管理技術的重中之重。文章結合制造業對人們在現實生活中的影響，分別針對生產計劃與調度的集成方法、生產計劃與調度問題的集成模型以及生產計劃與調度問題的算法進行了研究與總結。

關鍵詞：生產計劃；調度；建模；集成優化

中圖分類號：F406 文獻標志碼：A 文章編號：2095-2945（2017）19-0127-02

引言

根據目前制造業的發展情況再結合計算機、通訊和網絡的發展需求，一個企業是否具有新型的生產經營和管理理念是決定這個企業能否在激烈的環境中生存下來的前提條件。實際在生產過程中，生產面臨的問題較多，產品制造過程較為復雜，大多數的單一的生產計劃模型不好表達，也不好計算。所以階梯分解的方式不實用，但可通過在系統理論中進行分解和協調，并運用遞階分解方式制定生產計劃，從而進行計算，可以避免這種弊端?，F在根據理論概念，并結合該方法的使用，制定出的車間生產調度計劃和調度集成優化方案能夠確保最終形成的計劃有一個合適的調度，從而能夠計算出可行性較高的生產計劃。在實際生產過程中，生產計劃的缺陷常常采用制造過多的產品或增加交貨周期進行解決，但這僅僅解決了表面現象，問題沒有從根本解決。所以開展生產計劃、調度集成優化方案、模型和計算方法的研究是非常重要的。

1 生產計劃與調度問題分析

1.1 定義和內涵

在生產系統功能模塊中：（1）計劃層是核心部門，根據總的生產計劃，制定詳細的Job Shop短期生產計劃，該計劃詳細記錄了具體的生產時間、使用的設備或其他資源類型、加工的零部件種類和加工量等信息[1]。（2）調度層，主要的工作職責是控制和安排加工車間日常生產活動[2]，他們在收到計劃層下達的生產計劃后，根據零部件的類型，數量，交貨日期等信息，依據車間的生產能力和實際情況，制定出車間的加工計劃和產品加工步驟，進行資源的合理利用[3]。（3）控制層是連接調度層和執行層的重要紐帶，依據調度層下達的生產指令，結合車間實際生產情況來控制生產；處理來自調度層的調度信息；隨時監控車間生產情況，及時發現生產中的問題以及生產相關信息，并向調度層實時匯報。

1.2 生產計劃與調度問題的分類

（1）制造業的生產計劃按生產周期的長短一般來說可以分為三類：長期計劃、中期計劃和短期計劃。

長期計劃是戰略層制定的計劃，根據企業的發展戰略以及外部環境情況，整合企業所有的資源，制定企業長遠的發展計劃和戰略目標。

中期生產計劃是企業管理層制定的計劃，是管理層根據企業長期的生產計劃，對市場情況進行評估而制定的詳細生產指標和生產計劃。

短期生產計劃為企業作業層計劃，是中期生產計劃進行分解細化后的小生產計劃，它充分考慮車間設備以及人員的實際狀況，包括制定所需生產品種類別、每批產量、生產順序、各工序的時間進度的決策，生產周期大約幾天到幾周的時間。

（2）加工車間的調度問題受如下四個因素的影響：任務，資源，時間和性能指標。由于其各種要素的特點不同，種類也大相徑庭。依據車間所加工零部件的特征，將車間調度問題分為四種[4]：a.單機調度，指的是作業和機器作業順序的調度（不包括車輛、人員、路徑和時間等方面的調度），加工工序僅有這一臺加工設備，但需要加工的全部零部件有多個加工工序，且都在這一臺設備上加工。b.并行機床調度，人們可能將并行機調度考慮為一個兩階段過程。第一階段需要將工作任務分配至設備上，第二階段要決定每臺機器產品的加工順序。c.流水加工車間的調度，在流水車間中加工工序進行流水作業，因此，該工作調度需要很多項操作，而這些操作經常要按照同樣的順序執行，即這些工作都具有相同的作業流程。d.加工車間調度，其復雜程度最高、代表性最強的調度，該車間加工系統有多個功能不同的機床，需要加工的零部件需要進行多道工序加工，并且各零部件的加工線路均不同。

隨著Job Shop調度問題的深入研究，調度的分類也越來越細：a.動態調度：處理突發性加工時間；b.柔性調度：是否一道工序可以在多臺設備上進行加工，具體又分全柔性和部分柔性；c.依據性能指標集的特征，劃分為多目標調度、模糊目標調度等；d.依據生產過程，考慮生產過程中的不確定因素的調度稱為模糊調度。

2 生產計劃與調度問題的集成方法

目前，大多數文獻將集成的方法分為整體法和遞階法。（1）整體法是通過生產計劃和調度整體建模，再計算求解。（2）遞階法，對計劃和調度分層求解，將遞階優化的各個層次構成一個閉環形式，從而得出可行解。

在實際生產環境下：運用遞階法將問題拆分成兩個子問題，分別為制定生產目標的計劃子問題和具體的調度問題。通過計劃子問題的以數據形式將信息傳遞給調度子問題，并將調度層的信息向計劃層人員匯報。通過計劃與調度相互交叉計算求解，同時優化計劃與調度方案，這個方法的不足之處是通常情況下僅能尋找到局部的最優解[5]。通過整體法使具體的調度約束成為計劃問題資源的約束，與此同時，通過轉化調度的性能指標，使生產費用運用到計劃問題的目標函數里，成立計劃和調度問題的統一模型，該模型含有生產過程要求的全部信息。

3 生產計劃與調度問題的模型

3.1 生產計劃與調度問題的性能指標

將現有車間調度的性能指標進行集中后分成三類：時間指標、成本指標、時間成本混合指標。時間指標有加工周期、最小化最大完工時間、延期完工時間，提前完工時間等等。成本指標有加工生產成本費、加班費、庫存費、因延遲或提前完工而產生的罰款和準備成本費用等等。二者的混合指標主要有：設備使用情況、設備的最大負載能力等等。

3.2 生產計劃與調度問題的約束條件

經典的Job Shop問題包括以下9種約束：所有工件在零時刻都準備就緒；同一時間內僅能在同一臺機器上加工一個工件；所有的工序的加工依次進行，其中一道工序先通過臺機器完成后，才開始另一道工序；在同一時間內同一臺機器又能進行一個工件的加工；假如所有的工序的所需的加工時間都相同且確定，而且包含裝夾和調整的時間；假如各工序僅能通過指定的作業機器進行操作；工件的加工允許有等待時間；在整個生產過程，機器設備無異常且可連續運行；假設工序間有足夠的準備時間。一個集成模型要有明確的性能指標以及符合實際生產需求的調度約束。其中最主要的是將描述性語言變成數學語言時要規范和詳細。

4 生產計劃與調度問題的算法

在建立集成優化模型后，應計算出調度優化的解，找出調度問題的過程就是計算求解的過程。由于大部分加工車間調度問題是NP-hard問題，其求解方法都是啟發式的，因此得到的解大多數不是最優解。它們的目標是在相對短的時間內，在不同的生產環境下，找到一個合理的優化解。

目前研發出的算法可分為兩大類：精確算法和近似算法。其中解析法、枚舉法稱為精確的計算方法；構造方法、局部搜索法、智能法等方法稱為近似算法，主要分為五類方法。綜合實際生產中，效率最高的方法是智能方法，這種方法主要是找出可行性高的最優解，人工智能原理和相關技術，通過模擬動物群體活動的形式進行查找。在系統動態的變化的基礎上求得最優解，是把優化過程轉變成智能系統動態的轉變過程，如神經網絡[6]、蟻群系統[7]、遺傳算法[8]和粒子群優化[9]等。在實際生產中，蟻群算法、優先調度規則算法、遺傳算法、禁忌搜索法、模擬退火法、神經網絡法和混合計算法是目前熱點。

5 結束語

對生產計劃調度問題進行了全方面的機理分析，從其定義和內涵入手，緊接著按照其不同的方式進行了分類。對于Job Shop生產計劃與調度問題的集成方法進行了全面深刻的總結，找出了兩種方法的各自優缺點。在研究集成優化模型時，先著手研究分析性能指標，以備性能指標選取；然后對各個約束條件進行了梳理。最后總結了目前生產計劃和調度問題的計算方法。

參考文獻：

[1]藍伯雄，陳暉娜.一個集成化企業生產計劃模型[J].系統工程理論與實踐，2001，21（9）：33-41.

[2]李懷祖.生產計劃與控制（修訂版）[M].北京：中國科技出版社，2010.

[3]郭顏軍，曹巖，趙汝嘉，等.柔性制造單元集成控制和調度策略研究[J].制造業自動化，2001，23（7）：31-33.

[4]Maravelias C T， Sung C. Integration of production planning and scheduling： Overview， challenges and opportunities[J]. Computer Aided Chemical Engineering， 2009， 33（12）：1919-1930.

[5]Maravelias C T， Sung C. Integration of production planning and scheduling： Overview， challenges and opportunities[J]. Computer Aided Chemical Engineering， 2009， 33（12）：1919-1930.

[6]Fonseca D J， Navaresse D. Artificial neural networks for job shop simulation[J]. Advanced Engineering Informatics， 2002， 16（4）：241-246.

[7]楊劍峰.蟻群算法及其應用研究[D].杭州：浙江大學，2007.

[8]徐琦.遺傳算法的改進及其應用研究[D].武漢：華中科技大學，2001.

[9]那加.基于自適應變異的粒子群優化算法的車間作業調度優化及其軟件實現[J].信息與控制，2005，34（3）：365-368.