羅哲 夏余平 米雙山

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

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

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

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

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

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

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

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

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

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

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

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

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

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

基于作業(yè)車間調(diào)度問題的復(fù)雜性，根據(jù)具體情況選擇相應(yīng)的解決方案，為了能夠得到更好的調(diào)度，可以從策略上對(duì)作業(yè)車間調(diào)度進(jìn)行研究。目前形成的策略主要有以下幾種：（1）并行和分布策略：從車間調(diào)度的描述就可以看出它是一個(gè)比較復(fù)雜的問題，所以求解大規(guī)模的作業(yè)車間調(diào)度問題來說是一件是非常困難的事情?；诖嗽S多的研究學(xué)者提出用并行或分解的策略來解決車間調(diào)度問題。這種策略主要應(yīng)用在不同車間控制結(jié)構(gòu)和高度問題等復(fù)雜性的作業(yè)車間調(diào)度問題。（2）分解和成組策略：利用分解生產(chǎn)計(jì)劃的策略，可以降低作業(yè)車間調(diào)度計(jì)算的復(fù)雜性和規(guī)模，經(jīng)過分解后的作業(yè)調(diào)度問題更加容易得到好的解，同時(shí)還可以優(yōu)化系統(tǒng)的一些性能指標(biāo)。這種方法在制造系統(tǒng)應(yīng)用的比較廣泛?；舅枷胧歉鶕?jù)工件和機(jī)器之間的相似性對(duì)它們進(jìn)行分類，然后利用組內(nèi)的相似性來提高工作效率。（3）多目標(biāo)權(quán)衡調(diào)度策略：在實(shí)際生產(chǎn)過程中，以多目標(biāo)的作業(yè)車間調(diào)度問題為主。如最大化生產(chǎn)效率、最小化生產(chǎn)周期、最小化加工成本等等，其中有些目標(biāo)還是相互影響、相互沖突的，所以要對(duì)多目標(biāo)進(jìn)行權(quán)衡分析，得到一個(gè)均衡的調(diào)度。（4）生產(chǎn)計(jì)劃與調(diào)度集成策略：應(yīng)用這種策略可以對(duì)作業(yè)車間調(diào)度的全局優(yōu)化和生產(chǎn)系統(tǒng)的柔性進(jìn)行提升，所以生產(chǎn)計(jì)劃與調(diào)度集成策略符合先進(jìn)制造模式的思路。（5）人機(jī)交互策略：由于作業(yè)車間調(diào)度問題的多目標(biāo)性和各種因素的影響，為了能夠得到好的調(diào)度結(jié)果，往往需要與調(diào)度決策者的經(jīng)驗(yàn)知識(shí)相結(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é)者對(duì)作業(yè)車間調(diào)度問題進(jìn)行了深入而廣泛的研究，并應(yīng)用到各自的領(lǐng)域當(dāng)中，取得了令人滿意的結(jié)果。特別是機(jī)械、自動(dòng)化、計(jì)算機(jī)和數(shù)學(xué)等不同領(lǐng)域的結(jié)合交叉，為解決作業(yè)車間調(diào)度問題提出了眾多新的研究理論和新的研究方法。這些方法主要有三種類型：精確算法、近似算法以及智能搜索算法：（1）精確算法：這類方法雖然從理論上能夠?qū)ふ业阶顑?yōu)解，但由于計(jì)算復(fù)雜度較高的一些原因，使得精確求解方法只適用于規(guī)模不大的問題和性質(zhì)并不十分復(fù)雜的優(yōu)化問題。而在實(shí)際生產(chǎn)環(huán)境中存在許多不確定性的因素會(huì)對(duì)問題的求解帶來很大的困難，所以很難應(yīng)用精確方法去處理實(shí)際調(diào)度問題。（2）近似算法：由于大多數(shù)的作業(yè)車間調(diào)度問題屬于NP-hard問題。精確求解方法無法解決一些計(jì)算量大的復(fù)雜問題，所以許多研究學(xué)者研究這一問題采用各種近似或者啟發(fā)式的方法來對(duì)問題進(jìn)行求解。近似求解方法能在有限的時(shí)間內(nèi)找到相對(duì)滿意的次優(yōu)解，這種方法可以用來解決較大規(guī)模的實(shí)際調(diào)度問題。（3）智能搜索算法：這種方法是根據(jù)生物種群特有的一些屬性而抽象出來的一類算法。這類方法的特點(diǎn)是通用性強(qiáng)、求解的速度快且無需問題的任何特殊信息等。這種算法雖也是近似方法，但他們可以找到解空間中的最優(yōu)調(diào)度方案。

4 結(jié)束語

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

參考文獻(xiàn)：

[1]包云，姜華，鄭麗萍.基于和聲搜索的阻塞流水車間調(diào)度問題的算法優(yōu)化[J].計(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è)計(jì)與制造，2019（2）：30-33.

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

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