車間調(diào)度問題研究現(xiàn)狀與發(fā)展趨勢

羅哲　朱光宇

摘? 要：文章從車間調(diào)度問題的實際應(yīng)用特性出發(fā)，綜述了當(dāng)前車間調(diào)度問題在國內(nèi)外的研究現(xiàn)狀，在總結(jié)分析當(dāng)前研究車間調(diào)度問題的相關(guān)方法與技術(shù)的基礎(chǔ)上，指出了當(dāng)前在車間調(diào)度問題研究中存在的問題與不足，并提出了幾個車間調(diào)度問題研究的發(fā)展趨勢，以期為后續(xù)車間調(diào)度問題的不斷深入以及更好地為生產(chǎn)實際服務(wù)提供可借鑒的方向。

關(guān)鍵詞：車間調(diào)度;生產(chǎn)計劃;調(diào)度方法

中圖分類號：TP278? ? ? ? 文獻標(biāo)志碼：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 概述

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

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

2 車間調(diào)度問題國外研究現(xiàn)狀

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

2.1 傳統(tǒng)的調(diào)度方法

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

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

2.2 智能調(diào)度方法

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

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

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

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

3 車間調(diào)度問題國內(nèi)研究現(xiàn)狀

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

4 車間調(diào)度研究存在的問題與發(fā)展趨勢

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

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

參考文獻：

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

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

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

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

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

[6]朱光宇，楊志峰，陳旭斌.基于灰熵并行分析法的多目標(biāo)作業(yè)車間調(diào)度優(yōu)化[J].計算機系統(tǒng)應(yīng)用，2015，24（4）：176-183.

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