典型車間調度問題的分析與研究

羅哲 夏余平 米雙山

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

關鍵詞：流水車間調度;作業車間調度;調度策略;調度方法

中圖分類號：TP391? ? ? ? ?文獻標志碼：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 概述

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

2 流水車間調度

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

2.1 流水車間調度的主要特點

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

2.2 混合流水車間調度

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

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

3 作業車間調度

作業車間調度問題是計算機集成加工制造領域的一個重要組成部分，是最經典的離散制造系統調度問題，從數學規劃的角度來看又是一類困難的組合優化問題[4]。由于作業車間調度是源于制造業生產的實際需要，所以近年來作業車間調度成為一個研究熱點。

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

3.1 作業車間調度的策略

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

3.2 作業車間調度的研究方法

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

4 結束語

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

參考文獻：

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

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

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

[4]閆旭，葉春明，姚遠遠.量子鯨魚優化算法求解作業車間調度問題[J].計算機應用研究，2019，36（4）：975-979.

[5]楊恒.基于改進粒子群算法的作業車間調度優化[J].機械設計與制造工程，2019，48（2）：73-76.