典型車間調(diào)度問題的分析與研究

羅哲 夏余平 米雙山

摘? 要：文章針對目前車間調(diào)度問題中的兩種典型問題展開研究，即流水車間調(diào)度問題、作業(yè)車間調(diào)度問題，其中，對流水車間調(diào)度問題的基本原理和研究方法進(jìn)行了詳細(xì)闡述;對作業(yè)車間調(diào)度問題的基本原理、調(diào)度策略以及研究方法等做了分析與總結(jié)。通過文章的論述，為進(jìn)一步拓展這兩個典型車間調(diào)度問題的深入研究提供了有益參考。

關(guān)鍵詞：流水車間調(diào)度;作業(yè)車間調(diào)度;調(diào)度策略;調(diào)度方法

中圖分類號：TP391? ? ? ? ?文獻(xiàn)標(biāo)志碼：A? ? ? ? ?文章編號：2095-2945（2020）09-0054-02

Abstract： This paper studies two typical problems in the current job shop scheduling problem， namely， the flow shop scheduling problem and the job shop scheduling problem， in which the basic principles and research methods of the flow shop scheduling problem are described in detail. The basic principles， scheduling strategies and research methods of the job shop scheduling problem are analyzed and summarized. Through the discussion of this paper， it provides a useful reference for further expanding the in-depth study of these two typical job shopscheduling problems.

Keywords： flow shop scheduling; job shop scheduling; scheduling strategy; scheduling method

1 概述

車間調(diào)度問題指的是如何在有限的資源環(huán)境里，通過合理安排車間生產(chǎn)任務(wù)，進(jìn)而滿足一至多個性能指標(biāo)的過程。隨著經(jīng)濟(jì)社會的不斷發(fā)展，企業(yè)之間的競爭也愈發(fā)激烈，生產(chǎn)車間的生產(chǎn)規(guī)模也越來越大，如何合理安排車間調(diào)度也越來越復(fù)雜，車間調(diào)度業(yè)已成為智能制造的基礎(chǔ)組成部分。對于車間調(diào)度的優(yōu)化問題研究已經(jīng)成為工業(yè)發(fā)展的重點研究問題之一，對車間調(diào)度進(jìn)行優(yōu)化是提升現(xiàn)代制造技術(shù)和企業(yè)管理水平的重要內(nèi)容。開展車間調(diào)度研究，尋求良好的生產(chǎn)車間調(diào)度問題求解方案具有十分巨大的理論價值和實際應(yīng)用價值[1]。本文針對兩種典型的生產(chǎn)車間調(diào)度問題，就基本原理、研究方法等展開探討與分析。

2 流水車間調(diào)度

流水車間調(diào)度問題是加工制造業(yè)中的一類重要的規(guī)劃問題，多數(shù)情況下研究流水車間調(diào)度問題的加工任務(wù)中的作業(yè)個數(shù)都要大于3，這時候的車間調(diào)度問題是NP-hard問題。在過去的幾十年里國內(nèi)外學(xué)者對這個問題做了大量的研究，相應(yīng)的提出了許多解決這一問題的方法。這些方法大致可分成精確算法、啟發(fā)式算法和元啟發(fā)式算法三種。由于NP-hard問題的復(fù)雜性，所以，精確算法無法對規(guī)模較大的問題進(jìn)行求解，只能解決一些規(guī)模較小的流水車間調(diào)度問題。啟發(fā)式算法的優(yōu)點是能夠快速構(gòu)造問題的解，但是通常得到的這些解的質(zhì)量較差，無法滿足要求。元啟發(fā)式算法能夠在較短的時間里面得到較高質(zhì)量的解，所以，廣泛采用這種算法來對流水車間調(diào)度問題進(jìn)行求解。

2.1 流水車間調(diào)度的主要特點

流水車間調(diào)度問題的主要特點是一個生產(chǎn)任務(wù)內(nèi)包含一些代加工的作業(yè)，這些作業(yè)在處理機(jī)上的加工順序都相同，因此也被稱為同順序調(diào)度問題。流水車間調(diào)度問題的基本思路為：將一個加工任務(wù)中所有的待加工作業(yè)合理的安排到加工企業(yè)內(nèi)的處理機(jī)上，使得整個加工過程的某一項或者某幾項指標(biāo)達(dá)到最優(yōu)的目的。其中，每個作業(yè)在處理機(jī)上的準(zhǔn)備時間和加工時間、每個作業(yè)的交貨期等都是已知的，且要求每臺處理機(jī)上加工工件的順序相同。在某一時段內(nèi)每臺處理機(jī)只能對一個工件進(jìn)行操作，操作過程不能中斷直到作業(yè)的這一個操作完成為止。從對流水車間調(diào)度的描述可以看出它是許多實際流水線生產(chǎn)調(diào)度問題的簡化模型，是目前研究最廣泛的一類典型調(diào)度問題，受到了許多研究學(xué)者的重視，且提出了許多針對該問題的求解方法。但是主要的研究還是集中在單目標(biāo)的流水車間調(diào)度問題上，而在實際生產(chǎn)環(huán)境中，流水車間調(diào)度問題存在著多個相互沖突的目標(biāo)需要進(jìn)行優(yōu)化，因此開展多目標(biāo)流水車間調(diào)度問題的研究更加符合實際。

2.2 混合流水車間調(diào)度

混合流水車間調(diào)度是一種相對比較復(fù)雜的流水車間調(diào)度。它是根據(jù)石油工業(yè)的背景提出來的。在被提出后的幾十年里，許多研究學(xué)者對這一類問題進(jìn)行了研究，得到了許多解決這一問題的方法?；旌狭魉囬g調(diào)度問題就其本質(zhì)而言，可以分為兩類經(jīng)典調(diào)度問題：標(biāo)準(zhǔn)的流水車間調(diào)度問題和并行機(jī)調(diào)度問題。它的主要特征是：待加工作業(yè)的某些操作可以在幾臺并行處理機(jī)上進(jìn)行加工，因此混合流水車間調(diào)度也被稱為多機(jī)多階段流水車間調(diào)度問題[2]?；旌狭魉囬g調(diào)度問題經(jīng)常出現(xiàn)在柔性流水線的流程工業(yè)中，所以它也被稱為柔性流水車間調(diào)度問題，其研究目的即對工序進(jìn)行有效的排序，使得所選擇的某個性能指標(biāo)達(dá)到最優(yōu)，進(jìn)而實現(xiàn)企業(yè)效益最優(yōu)[3]。由于其在理論研究領(lǐng)域的代表性和在諸多工業(yè)領(lǐng)域的廣泛應(yīng)用背景，近年來得到許多研究者的重視。

混合流水車間調(diào)度的特點為多目標(biāo)性、多約束性、多階段性以及非線性。其本質(zhì)是由一系列加工過程組成，加工過程中的某些階段可能只有一臺處理機(jī)，但在整個加工過程中至少存在一個階段有兩臺或者兩臺以上的并行處理機(jī)可以對其進(jìn)行加工。待加工的工件可由并行處理機(jī)中的任一臺進(jìn)行加工，工件在車間里必須是單向流動的?；旌狭魉囬g調(diào)度在流程加工制造行業(yè)中應(yīng)用比較廣泛，如鋼鐵企業(yè)加工工藝大概可以分為煉鋼、連鑄和熱軋三個階段，每個階段都會存在多個并行處理機(jī)可以對其進(jìn)行操作。

3 作業(yè)車間調(diào)度

作業(yè)車間調(diào)度問題是計算機(jī)集成加工制造領(lǐng)域的一個重要組成部分，是最經(jīng)典的離散制造系統(tǒng)調(diào)度問題，從數(shù)學(xué)規(guī)劃的角度來看又是一類困難的組合優(yōu)化問題[4]。由于作業(yè)車間調(diào)度是源于制造業(yè)生產(chǎn)的實際需要，所以近年來作業(yè)車間調(diào)度成為一個研究熱點。

作業(yè)車間調(diào)度問題的基本思路為：將一個加工任務(wù)中所有的待加工作業(yè)合理的安排到加工企業(yè)內(nèi)的處理機(jī)上，使得整個加工過程的某一項或者某幾項指標(biāo)達(dá)到最優(yōu)的目的[5]。要求每個作業(yè)的操作都需要占用處理機(jī)或其它資源才能完成加工過程，在這個過程中必須滿足各個作業(yè)的工藝路線、工藝次序要求進(jìn)行加工。在加工過程中每臺處理機(jī)可以加工作業(yè)的若干操作，并且在不同處理機(jī)上能加工的操作集可以是不同的，這是作業(yè)車間調(diào)度與流水車間作業(yè)調(diào)度最大的不同，因而使作業(yè)車間調(diào)度更加復(fù)雜。簡而言之，作業(yè)車間調(diào)度的本質(zhì)是確定一個滿足各種約束的調(diào)度，該調(diào)度能在某個特定的時間段將每個工序分配到對應(yīng)的處理機(jī)上，然后找到可以最小化加工成本和時間等某幾個性能的調(diào)度。

3.1 作業(yè)車間調(diào)度的策略

基于作業(yè)車間調(diào)度問題的復(fù)雜性，根據(jù)具體情況選擇相應(yīng)的解決方案，為了能夠得到更好的調(diào)度，可以從策略上對作業(yè)車間調(diào)度進(jìn)行研究。目前形成的策略主要有以下幾種：（1）并行和分布策略：從車間調(diào)度的描述就可以看出它是一個比較復(fù)雜的問題，所以求解大規(guī)模的作業(yè)車間調(diào)度問題來說是一件是非常困難的事情?；诖嗽S多的研究學(xué)者提出用并行或分解的策略來解決車間調(diào)度問題。這種策略主要應(yīng)用在不同車間控制結(jié)構(gòu)和高度問題等復(fù)雜性的作業(yè)車間調(diào)度問題。（2）分解和成組策略：利用分解生產(chǎn)計劃的策略，可以降低作業(yè)車間調(diào)度計算的復(fù)雜性和規(guī)模，經(jīng)過分解后的作業(yè)調(diào)度問題更加容易得到好的解，同時還可以優(yōu)化系統(tǒng)的一些性能指標(biāo)。這種方法在制造系統(tǒng)應(yīng)用的比較廣泛?；舅枷胧歉鶕?jù)工件和機(jī)器之間的相似性對它們進(jìn)行分類，然后利用組內(nèi)的相似性來提高工作效率。（3）多目標(biāo)權(quán)衡調(diào)度策略：在實際生產(chǎn)過程中，以多目標(biāo)的作業(yè)車間調(diào)度問題為主。如最大化生產(chǎn)效率、最小化生產(chǎn)周期、最小化加工成本等等，其中有些目標(biāo)還是相互影響、相互沖突的，所以要對多目標(biāo)進(jìn)行權(quán)衡分析，得到一個均衡的調(diào)度。（4）生產(chǎn)計劃與調(diào)度集成策略：應(yīng)用這種策略可以對作業(yè)車間調(diào)度的全局優(yōu)化和生產(chǎn)系統(tǒng)的柔性進(jìn)行提升，所以生產(chǎn)計劃與調(diào)度集成策略符合先進(jìn)制造模式的思路。（5）人機(jī)交互策略：由于作業(yè)車間調(diào)度問題的多目標(biāo)性和各種因素的影響，為了能夠得到好的調(diào)度結(jié)果，往往需要與調(diào)度決策者的經(jīng)驗知識相結(jié)合來尋找最優(yōu)的調(diào)度。人機(jī)交互的策略可以減少系統(tǒng)的搜索空間，能夠更好更快的找到復(fù)雜的作業(yè)車間調(diào)度問題的最優(yōu)解。

3.2 作業(yè)車間調(diào)度的研究方法

作業(yè)車間調(diào)度是生產(chǎn)調(diào)度問題中的典型代表，很多領(lǐng)域中具體的組合優(yōu)化問題都可以抽象為作業(yè)車間調(diào)度問題進(jìn)行求解。所以各領(lǐng)域的研究學(xué)者對作業(yè)車間調(diào)度問題進(jìn)行了深入而廣泛的研究，并應(yīng)用到各自的領(lǐng)域當(dāng)中，取得了令人滿意的結(jié)果。特別是機(jī)械、自動化、計算機(jī)和數(shù)學(xué)等不同領(lǐng)域的結(jié)合交叉，為解決作業(yè)車間調(diào)度問題提出了眾多新的研究理論和新的研究方法。這些方法主要有三種類型：精確算法、近似算法以及智能搜索算法：（1）精確算法：這類方法雖然從理論上能夠?qū)ふ业阶顑?yōu)解，但由于計算復(fù)雜度較高的一些原因，使得精確求解方法只適用于規(guī)模不大的問題和性質(zhì)并不十分復(fù)雜的優(yōu)化問題。而在實際生產(chǎn)環(huán)境中存在許多不確定性的因素會對問題的求解帶來很大的困難，所以很難應(yīng)用精確方法去處理實際調(diào)度問題。（2）近似算法：由于大多數(shù)的作業(yè)車間調(diào)度問題屬于NP-hard問題。精確求解方法無法解決一些計算量大的復(fù)雜問題，所以許多研究學(xué)者研究這一問題采用各種近似或者啟發(fā)式的方法來對問題進(jìn)行求解。近似求解方法能在有限的時間內(nèi)找到相對滿意的次優(yōu)解，這種方法可以用來解決較大規(guī)模的實際調(diào)度問題。（3）智能搜索算法：這種方法是根據(jù)生物種群特有的一些屬性而抽象出來的一類算法。這類方法的特點是通用性強(qiáng)、求解的速度快且無需問題的任何特殊信息等。這種算法雖也是近似方法，但他們可以找到解空間中的最優(yōu)調(diào)度方案。

4 結(jié)束語

隨著智能制造的不斷發(fā)展，車間調(diào)度問題的研究也越來越深入，車間調(diào)度在實現(xiàn)智能制造方面起著舉足輕重的作用。本文分別從流水車間調(diào)度問題與作業(yè)車間調(diào)度問題的基本原理、主要特點以及調(diào)度策略等方面展開分析，并對混合流水車間調(diào)度問題的應(yīng)用背景與主要特點進(jìn)行了簡要介紹。綜述了作業(yè)車間調(diào)度問題常見的五種調(diào)度策略，以及其三種類型的研究方法。通過本文的分析與闡述，為后續(xù)車間調(diào)度問題的研究拓展提供了良好參考。

參考文獻(xiàn)：

[1]包云，姜華，鄭麗萍.基于和聲搜索的阻塞流水車間調(diào)度問題的算法優(yōu)化[J].計算機(jī)工程與科學(xué)，2013，35（7）：108-112.

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

[3]王建朝，袁逸萍，李曉娟，等.關(guān)鍵鏈約束理論解決柔性車間調(diào)度問題[J].機(jī)械設(shè)計與制造，2019（2）：30-33.

[4]閆旭，葉春明，姚遠(yuǎn)遠(yuǎn).量子鯨魚優(yōu)化算法求解作業(yè)車間調(diào)度問題[J].計算機(jī)應(yīng)用研究，2019，36（4）：975-979.

[5]楊恒.基于改進(jìn)粒子群算法的作業(yè)車間調(diào)度優(yōu)化[J].機(jī)械設(shè)計與制造工程，2019，48（2）：73-76.