車間調度問題研究現狀與發展趨勢

羅哲　朱光宇

摘? 要：文章從車間調度問題的實際應用特性出發，綜述了當前車間調度問題在國內外的研究現狀，在總結分析當前研究車間調度問題的相關方法與技術的基礎上，指出了當前在車間調度問題研究中存在的問題與不足，并提出了幾個車間調度問題研究的發展趨勢，以期為后續車間調度問題的不斷深入以及更好地為生產實際服務提供可借鑒的方向。

關鍵詞：車間調度;生產計劃;調度方法

中圖分類號：TP278? ? ? ? 文獻標志碼：A? ? ? ? ?文章編號：2095-2945（2020）23-0123-02

Abstract： Starting from the practical application characteristics of the workshop scheduling problem， this paper summarizes the current research status of the workshop scheduling problem at home and abroad， and on the basis of summarizing and analyzing the relevant methods and technologies of the current research on the workshop scheduling problem， this paper points out the problems and deficiencies existing in the research of workshop scheduling problem， and puts forward the development trend of several workshop scheduling problems， in order to provide a reference direction for the continuous deepening of the follow-up workshop scheduling problems and for the production of actual services.

Keywords： workshop scheduling; production planning; scheduling method

1 概述

生產調度指的是企業在生產過程中，以生產為中心，通過對有效的資源進行合理指揮、控制和調節，進而達到提高經濟效益目的的過程。近年來隨著科學技術的發展，人們已經成功地將加工制造技術與現代管理技術、自動化技術、信息技術以及系統工程技術等學科相融合，提出了許多先進的制造模式，這些模式都是通過內外資源合理的分配、縮短加工時間以及降低成本等方法來解決諸多企業所面臨著的許多共性問題。而生產調度的主要作用就是要對有限的資源進行有效合理配置和優化，使待加工的作業能夠均衡地安排到每臺處理機上， 在滿足加工系統約束條件的前提下最大程度上滿足客戶和企業所需求的指標。因此，生產調度就成為了各種先進加工制造模式的核心內容和重要組成部分。

自1945年Johnson提出了流水車間調度的問題之后，許多的研究學者逐漸開始注重車間調度問題的研究，并針對解決車間調度問題的算法的有效性和復雜度展開研究。在以后的幾十年里，隨著對車間調度研究的逐漸深入，許多的專家學者將應用數學、運籌學、工程技術等領域中的方法應用到車間調度問題中，在此期間形成了許多解決問題的理論和方法，并解決了許多典型的調度優化問題。本文分別就國內外在車間調度問題上的研究現狀，以及發展趨勢進行探討。

2 車間調度問題國外研究現狀

國外對車間調度的研究開始得很早，研究成果也比較多，主要的研究方法有：

2.1 傳統的調度方法

主要有1999年Rios R.Z.等人運用運籌學的方法解決一類多機器的流水車間調度問題，并結合分支定界法對其進行求解。2001年Rabadi G.等也是應用了分支定界法解決有公共交貨期和獨立調整時間的單機提前/拖期調度問題，從而得到了令人滿意的結果。2002年chen M等人使用了混合整數規劃模型對制造生產過程最小化加工時間調度問題進行優化，并得到了很好的結果。

由于單純的運籌學方法的計算復雜度較大，只能對小規模的車間調度問題進行求解。因此，在解決大規模的車間調度問題時，將運籌學與其它算法相結合的方法來降低計算復雜程度。主要代表有： 2003年Mohanasundaram K.M等提出了基于調度優先規則來解決最大流程時間、階段延遲和最大作業拖期的一類多層制造作業車間問題等。

2.2 智能調度方法

實際生產過程中，調度問題是一個規模較大，約束較多的問題，在這種情況下要尋找車間調度的最優解是比較困難的，因此只能通過一種方法能夠在較短的時間內找到問題的近似解。20世紀80年代以來由于神經網絡、遺傳算法等人工智能方法的逐漸提出，很多學者和專家將這些人工智能算法應用到生產調度問題上并得到了很大的發展。主要的方法有：

（1）基于統計式全局搜索技術的智能算法，主要包括模擬退火算法、禁忌搜索算法等，代表文獻有： 2004年Armentano V.A等應用禁忌搜索算法來解決雙目標流水車間調度問題。2006年Mohammad S.M等用禁忌搜索算法方法來解決最大完工時間最小依賴于設置的柔性作業車間調度問題。2008年Olivier L等人提出了一種新的禁忌搜索方法來取代自由搜索的目標函數來解決生產項目調度問題。

（2）神經網絡方法，它是根據生物神經網絡的行為特征提出的一種并行信息處理的智能搜索算法。在車間調度中應用的代表為：2005年Akyol D.E等人提出了雙層反饋神經網絡，以此來解決最小化提前和拖期連接權的多機調度問題。2006年Noorul H等將神經網絡的方法用來解決雙目標流水車間調度問題等等。

（3）遺傳算法，它是根據生物群體的物競天擇的進化理論提出的一種具有較好的并行性和魯棒性特征的優化算法，所以遺傳算法被廣泛的應用在實際生產調度問題中。同時遺傳算法可以與其他算法相結合，能夠更好地解決車間調度問題，典型代表有：2006年chen K.J.通過訂單的信息確定了以最小化機器空閑時間和提前/拖后懲罰為目標的動態車間調度，將凍結間隔的優先規則和遺傳算法結合的方法解決這個問題。2008年Vicente V.等人應用混合遺傳算法對資源受限的項目調度問題進行求解。2010年L. De Giovanni等采用一種改進的遺傳算法來解決分布式柔性作業車間調度問題。

3 車間調度問題國內研究現狀

由于我國在加工制造業技術上存在滯后，所以在生產過程中一般主要還是依靠調度人員長期積累的經驗對加工作業進行分配。但隨著國外對車間調度研究方法的不斷傳入，國內也掀起了一股研究車間調度問題的熱潮。研究工作主要集中在一些重點高校的實驗室，而目前這些實驗室還處于開發試運行的初始階段，主要的研究成果有：2005年徐震浩將模糊數學理論引入到免疫算法中提出了模糊免疫調度算法來解決一種不確定條件下的流水車間調度問題[1]。2006年牛剛剛等根據細胞分裂和變異的思想提出了一種免疫算法解決靜態作業車間調度問題[2]。2009年張長勝提出了一種將遺傳操作引入到粒子群算法中的自適應混合粒子群進化算法來解決最小化加工完工時間的流水車間調度問題[3]。2010年李俊青等人提出了一種帶有Pareto檔案集的混合禁忌搜索算法來解決最小化最大完成時間、總機床負荷和最大機床負荷的一種多目標柔性作業車間調度問題[4]。2011年王偉玲等提出一種將正逆序調度方法與生成調度活動的遺傳算法相結合的雙種群遺傳算法來求解多目標作業車間調度問題[5];2015年朱光宇等利用灰熵并行關聯度作為優化計算的適應度值計算策略，采用差分算法與遺傳算法相結合的混合優化算法解決多目標作業車間調度問題[6];2019年宋存利等提出一種改進貪婪遺傳算法求解針對最小化最大完成時間的帶有不相關并行機的流水車間調度問題[7]。

4 車間調度研究存在的問題與發展趨勢

國內外針對不同類型的生產調度問題展開研究已有30多年的歷史，研究的內容和應用的范圍也極其廣泛，但多數研究的是單機單目標調度和多機單目標調度，而對多目標調度的研究還很少，而現實生活當中車間調度問題的多目標性一直普遍存在，而這種多目標性更加符合現實生產情況。企業一般在生產加工時，不僅要求減少工件的空閑時間、客戶的等待時間、產品的生產周期，而且還要減少延期費用、存儲費用等，所以實際的生產調度問題是一種復雜的多目標優化問題。雖然國內外的一些專家學者對多目標車間調度問題也有一些研究，但是在對多個目標的均衡問題上，如何避免主觀人為因素的影響，對于具體問題能夠準確合理的確定每個目標的權重比較困難，這將是后續車間調度問題研究的一個重點。

大多數的車間調度問題屬于一類非常復雜的組合優化問題，且在實際生產過程當中車間調度經常會受到各種各樣的因素干擾，如機器故障，需求市場的波動和客戶對產品要求的變更等等。由于這些因素的影響使得我們無法精確的求出車間調度問題的最優解，只能尋找一種能夠得到近似最優解的方法。而人工智能算法能在合理的時間內產生令人相對滿意的調度，所以這些方法已經廣泛應用于實際生產調度中。在實際車間調度中還存在另一個問題，這就是生產車間計劃與生產車間調度通常是分開進行的，這可能造成車間計劃在實際調度中產生不可行的情況，所以對車間調度的進一步研究還要綜合考慮這個兩方面，以便能夠得到總體的優化。現在的加工都是在柔性制造環境下進行的，柔性車間作業調度問題也將會成為接下來研究的重點和方向。

參考文獻：

[1]徐震浩，顧幸生.不確定條件下的flow shop問題的免疫調度算法[J].系統工程學報，2005，20（4）：374-380.

[2]牛剛剛，孫樹棟，余建軍，等.免疫進化算法求解靜態job-shop調度[J].機械工程學報，2006，42（5）：87-91.

[3]張長勝，孫吉貴，歐陽丹彤，等.求解車間調度問題的自適應混合粒子群算法[J].計算機學報，2009，32（11）：2137-2146.

[4]李俊青，潘全科，王玉亭.多目標柔性車間調度的Pareto混合禁忌搜索算法[J].計算機集成制造系統，2010，16（7）：1419-1426.

[5]王偉玲，李俊芳，王晶.求解多目標作業車間調度問題的雙種群遺傳算法[J].計算機集成制造系統，2011，17（4）：808-815.

[6]朱光宇，楊志峰，陳旭斌.基于灰熵并行分析法的多目標作業車間調度優化[J].計算機系統應用，2015，24（4）：176-183.

[7]宋存利.求解混合流水車間調度的改進貪婪遺傳算法[J].系統工程與電子技術，2019，41（5）：1079-1086.