JobShop生產(chǎn)計(jì)劃與調(diào)度的集成建模和優(yōu)化綜述

劉思成+王艷紅

摘 要：制造業(yè)的核心是生產(chǎn)管理技術(shù)，而如何制定好生產(chǎn)計(jì)劃與調(diào)度也正是生產(chǎn)管理技術(shù)的重中之重。文章結(jié)合制造業(yè)對(duì)人們?cè)诂F(xiàn)實(shí)生活中的影響，分別針對(duì)生產(chǎn)計(jì)劃與調(diào)度的集成方法、生產(chǎn)計(jì)劃與調(diào)度問題的集成模型以及生產(chǎn)計(jì)劃與調(diào)度問題的算法進(jìn)行了研究與總結(jié)。

關(guān)鍵詞：生產(chǎn)計(jì)劃；調(diào)度；建模；集成優(yōu)化

中圖分類號(hào)：F406 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：2095-2945（2017）19-0127-02

引言

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

1 生產(chǎn)計(jì)劃與調(diào)度問題分析

1.1 定義和內(nèi)涵

在生產(chǎn)系統(tǒng)功能模塊中：（1）計(jì)劃層是核心部門，根據(jù)總的生產(chǎn)計(jì)劃，制定詳細(xì)的Job Shop短期生產(chǎn)計(jì)劃，該計(jì)劃詳細(xì)記錄了具體的生產(chǎn)時(shí)間、使用的設(shè)備或其他資源類型、加工的零部件種類和加工量等信息[1]。（2）調(diào)度層，主要的工作職責(zé)是控制和安排加工車間日常生產(chǎn)活動(dòng)[2]，他們?cè)谑盏接?jì)劃層下達(dá)的生產(chǎn)計(jì)劃后，根據(jù)零部件的類型，數(shù)量，交貨日期等信息，依據(jù)車間的生產(chǎn)能力和實(shí)際情況，制定出車間的加工計(jì)劃和產(chǎn)品加工步驟，進(jìn)行資源的合理利用[3]。（3）控制層是連接調(diào)度層和執(zhí)行層的重要紐帶，依據(jù)調(diào)度層下達(dá)的生產(chǎn)指令，結(jié)合車間實(shí)際生產(chǎn)情況來控制生產(chǎn)；處理來自調(diào)度層的調(diào)度信息；隨時(shí)監(jiān)控車間生產(chǎn)情況，及時(shí)發(fā)現(xiàn)生產(chǎn)中的問題以及生產(chǎn)相關(guān)信息，并向調(diào)度層實(shí)時(shí)匯報(bào)。

1.2 生產(chǎn)計(jì)劃與調(diào)度問題的分類

（1）制造業(yè)的生產(chǎn)計(jì)劃按生產(chǎn)周期的長短一般來說可以分為三類：長期計(jì)劃、中期計(jì)劃和短期計(jì)劃。

長期計(jì)劃是戰(zhàn)略層制定的計(jì)劃，根據(jù)企業(yè)的發(fā)展戰(zhàn)略以及外部環(huán)境情況，整合企業(yè)所有的資源，制定企業(yè)長遠(yuǎn)的發(fā)展計(jì)劃和戰(zhàn)略目標(biāo)。

中期生產(chǎn)計(jì)劃是企業(yè)管理層制定的計(jì)劃，是管理層根據(jù)企業(yè)長期的生產(chǎn)計(jì)劃，對(duì)市場(chǎng)情況進(jìn)行評(píng)估而制定的詳細(xì)生產(chǎn)指標(biāo)和生產(chǎn)計(jì)劃。

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

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

隨著Job Shop調(diào)度問題的深入研究，調(diào)度的分類也越來越細(xì)：a.動(dòng)態(tài)調(diào)度：處理突發(fā)性加工時(shí)間；b.柔性調(diào)度：是否一道工序可以在多臺(tái)設(shè)備上進(jìn)行加工，具體又分全柔性和部分柔性；c.依據(jù)性能指標(biāo)集的特征，劃分為多目標(biāo)調(diào)度、模糊目標(biāo)調(diào)度等；d.依據(jù)生產(chǎn)過程，考慮生產(chǎn)過程中的不確定因素的調(diào)度稱為模糊調(diào)度。

2 生產(chǎn)計(jì)劃與調(diào)度問題的集成方法

目前，大多數(shù)文獻(xiàn)將集成的方法分為整體法和遞階法。（1）整體法是通過生產(chǎn)計(jì)劃和調(diào)度整體建模，再計(jì)算求解。（2）遞階法，對(duì)計(jì)劃和調(diào)度分層求解，將遞階優(yōu)化的各個(gè)層次構(gòu)成一個(gè)閉環(huán)形式，從而得出可行解。

在實(shí)際生產(chǎn)環(huán)境下：運(yùn)用遞階法將問題拆分成兩個(gè)子問題，分別為制定生產(chǎn)目標(biāo)的計(jì)劃子問題和具體的調(diào)度問題。通過計(jì)劃子問題的以數(shù)據(jù)形式將信息傳遞給調(diào)度子問題，并將調(diào)度層的信息向計(jì)劃層人員匯報(bào)。通過計(jì)劃與調(diào)度相互交叉計(jì)算求解，同時(shí)優(yōu)化計(jì)劃與調(diào)度方案，這個(gè)方法的不足之處是通常情況下僅能尋找到局部的最優(yōu)解[5]。通過整體法使具體的調(diào)度約束成為計(jì)劃問題資源的約束，與此同時(shí)，通過轉(zhuǎn)化調(diào)度的性能指標(biāo)，使生產(chǎn)費(fèi)用運(yùn)用到計(jì)劃問題的目標(biāo)函數(shù)里，成立計(jì)劃和調(diào)度問題的統(tǒng)一模型，該模型含有生產(chǎn)過程要求的全部信息。

3 生產(chǎn)計(jì)劃與調(diào)度問題的模型

3.1 生產(chǎn)計(jì)劃與調(diào)度問題的性能指標(biāo)

將現(xiàn)有車間調(diào)度的性能指標(biāo)進(jìn)行集中后分成三類：時(shí)間指標(biāo)、成本指標(biāo)、時(shí)間成本混合指標(biāo)。時(shí)間指標(biāo)有加工周期、最小化最大完工時(shí)間、延期完工時(shí)間，提前完工時(shí)間等等。成本指標(biāo)有加工生產(chǎn)成本費(fèi)、加班費(fèi)、庫存費(fèi)、因延遲或提前完工而產(chǎn)生的罰款和準(zhǔn)備成本費(fèi)用等等。二者的混合指標(biāo)主要有：設(shè)備使用情況、設(shè)備的最大負(fù)載能力等等。

3.2 生產(chǎn)計(jì)劃與調(diào)度問題的約束條件

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

4 生產(chǎn)計(jì)劃與調(diào)度問題的算法

在建立集成優(yōu)化模型后，應(yīng)計(jì)算出調(diào)度優(yōu)化的解，找出調(diào)度問題的過程就是計(jì)算求解的過程。由于大部分加工車間調(diào)度問題是NP-hard問題，其求解方法都是啟發(fā)式的，因此得到的解大多數(shù)不是最優(yōu)解。它們的目標(biāo)是在相對(duì)短的時(shí)間內(nèi)，在不同的生產(chǎn)環(huán)境下，找到一個(gè)合理的優(yōu)化解。

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

5 結(jié)束語

對(duì)生產(chǎn)計(jì)劃調(diào)度問題進(jìn)行了全方面的機(jī)理分析，從其定義和內(nèi)涵入手，緊接著按照其不同的方式進(jìn)行了分類。對(duì)于Job Shop生產(chǎn)計(jì)劃與調(diào)度問題的集成方法進(jìn)行了全面深刻的總結(jié)，找出了兩種方法的各自優(yōu)缺點(diǎn)。在研究集成優(yōu)化模型時(shí)，先著手研究分析性能指標(biāo)，以備性能指標(biāo)選?。蝗缓髮?duì)各個(gè)約束條件進(jìn)行了梳理。最后總結(jié)了目前生產(chǎn)計(jì)劃和調(diào)度問題的計(jì)算方法。

參考文獻(xiàn)：

[1]藍(lán)伯雄，陳暉娜.一個(gè)集成化企業(yè)生產(chǎn)計(jì)劃模型[J].系統(tǒng)工程理論與實(shí)踐，2001，21（9）：33-41.

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

[3]郭顏軍，曹巖，趙汝嘉，等.柔性制造單元集成控制和調(diào)度策略研究[J].制造業(yè)自動(dòng)化，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]楊劍峰.蟻群算法及其應(yīng)用研究[D].杭州：浙江大學(xué)，2007.

[8]徐琦.遺傳算法的改進(jìn)及其應(yīng)用研究[D].武漢：華中科技大學(xué)，2001.

[9]那加.基于自適應(yīng)變異的粒子群優(yōu)化算法的車間作業(yè)調(diào)度優(yōu)化及其軟件實(shí)現(xiàn)[J].信息與控制，2005，34（3）：365-368.