順序依賴并行機調度問題介紹

生產調度問題是指：給定一個加工任務，根據已有的生產條件，對有限的系統(tǒng)資源進行分配，對產品的加工步驟進行安排，使得某項性能指標最優(yōu)。在實際生產過程中，所涉及的約束條件主要有：機器的加工能力，機器的數(shù)量，加工的產品數(shù)量，產品的加工順序，產品的交貨時間，生產原料的數(shù)量，成本限制，機器故障，產品投產期等。考慮的性能指標主要有：產品交貨時間最短，加工時間最短，生產周期最短，成本最少，設備利用率最高等，實際的生產過程一般要平衡多個性能指標[1]。

問題分類：

根據加工能力的不同，調度問題可以分為單機調度、并行機調度、流水車間調度和作業(yè)車間調度等多種類型。其中單機調度只有一臺機器參與加工，最終要找到一個最優(yōu)工序排列；并行機調度是指有多臺性能一樣的并行機可以參與加工，所有加工任務只有一道工序，加工任務可以在其中的任意一臺加工完成；流水車間調度指的是，對應于不同的加工工件，有著相同的加工順序，各工件的加工時間可以相同或不同；作業(yè)車間調度指的是，每個工件都有自己的加工線路，任意的工件之間其加工順序和加工時間都可以不同[2]。

圖1 并行機調度示意圖

由于不同的調度問題所涉及的機器、工件的性質及所要求的目標不同，出現(xiàn)了形式多樣的調度模型，Graham等在1979年提出了目前通用的三參數(shù)表示方法，三參數(shù)方法a|b|g由三個域組成，其中a表示機器的環(huán)境及性質，b域表示工件的性質及對加工影響的約束條件，g域表示需要優(yōu)化的目標[3]。常見的域參數(shù)見下表。

表 1 調度問題模型域參數(shù)

域

參數(shù)

描述

a

1

單機，single machine

P

并行機，parallel machines

F

流水車間，flow ? shop

J

任務車間，job ? shop

b

序列無關的生產準備成本，

sequence-independent setup time

序列依賴的生產準備成本，

sequence-dependent setup time

可批量序列依賴的生產準備成本，

Batch sequence-dependent setup time

各工件交貨期相同，即具有公共交貨期，common due date

表示各工件權重相同，即具有公共權重，common weight

表示加工時間在一個區(qū)間內變動，即具有加工時間窗

g

最大制造周期，makespan

最大延遲（拖期），maximum ? tardiness

完工時間總和

加權完工時間總和

延遲時間總和

加權延遲總和

單機調度問題可以描述為，相互獨立的任務需要在系統(tǒng)中的一臺機器上序貫處理，每項任務都有加工時間、交貨期等參數(shù)，此外還要滿足一些調度環(huán)境和約束條件的要求，調度目標就是要找到一個最優(yōu)的任務序列使得系統(tǒng)總成本最小。

其中處理順序無關的單機調度問題是指工件的準備時間相同或固定，此時工件的加工準備時間是順序無關的，稱為順序無關的單機調度問題。處理順序依賴的單機調度問題是，任務的加工準備時間依賴與前一個加工任務，如兩個任務共享部分模具時，其換型時間會縮短，此時問題稱為順序依賴準備時間的單機調度問題。

批量加工單機調度問題是指，加工任務可以分為若干種類，同種加工任務是相同的，之間不用換型；而非批量加工單機調度問題是指，每個加工任務都是不同的，無法合并為一個連續(xù)任務加工。

并行機調度作為單機調度問題的延伸，除了考慮單機調度的特點外，還需要考慮設備性能的問題，和環(huán)境的因素。按照設備性能的不同，可以分為等同并行機調度與不相關并行機調度。其中等同并行機調度是指所有機器皆可對工件進行加工，并且每臺機器加工同一工件的時間相同。而不相關并行機又稱為不相關并行機，即同一種工件可以在任意一臺機器上加工，但是在不同機器上工件的加工時間不同。按照環(huán)境的不同可以分為靜態(tài)調度與動態(tài)調度。其中靜態(tài)調度將并行機車間生產加工過程理想化，僅考慮工件在機器上的加工時間，不考慮外界突發(fā)因素和約束條件的影響。而動態(tài)調度需要考慮外界各種突發(fā)因素和實際工況存在的約束條件，如機器故障、訂單修改等，動態(tài)調度需要根據外界突發(fā)因素和實際工況環(huán)境的變化對規(guī)劃進行改動，以便保持規(guī)劃的優(yōu)度[4]。

求解算法：

由于P||STsd|Cmax問題本身NP-難的性質，精確方法難以在短時間內有效求解，因此，其求解方法可以總結為啟發(fā)式規(guī)則方法和元啟發(fā)式算法。

啟發(fā)式規(guī)則依據一定的規(guī)則和策略來決定下一步需要調度的工作，從而產生較好的調度解。優(yōu)點是簡單實用，計算代價小，但面臨復雜的調度問題時，難以得到全局最優(yōu)解。針對不同的問題，業(yè)內提出了各種調度規(guī)則[5,6]。

1、EDD規(guī)則：最早工期（earliest due date）優(yōu)先，按照工期從小到大排列，該規(guī)則對1||Lmax是最優(yōu)的。

2、EDDF規(guī)則：同產品族內優(yōu)先（EDD within families），同種任務類型內部按照EDD規(guī)則進行排序。

3、EDDB規(guī)則：產品批量最早工期優(yōu)先（EDD for batches），不同批次間的任務按照EDD規(guī)則排序。

4、ATC規(guī)則：明顯滯后成本（apparent tardiness cost）規(guī)則。該規(guī)則針對1||∑wjTj問題具有較好效果。ATC根據一項指數(shù)每次調度一項工作。每次機器空閑時，選擇具有最高排序指數(shù)的工作作為下一個加工的工作。指數(shù)定義如下：

其中，K是由經驗確定的比例規(guī)則參數(shù)，是剩余工作的平均加工時間。

5、NEH規(guī)則

NEH規(guī)則方法是Nawaz、Enscore和Ham提出的NEH啟發(fā)式規(guī)則，其主要步驟如下[7]：

步驟1：計算各工件在各臺機器上加工時間的總和并且進行降序排列；

步驟2：排列序列中的前兩個工件，保存具有較好部分目標函數(shù)值得排列，固定這兩個工件的順序；

步驟3：從第三個工件開始，依次取出第k個工件，將其插入到之前固定的k-1個工件排序中所有可能的k個位置上，保存具有最優(yōu)部分目標函數(shù)值得工件序列，并固定這k個工件的位置。

6、多插入啟發(fā)規(guī)則[8]

多插入啟發(fā)規(guī)則來源于對旅行商問題的求解，其主要步驟如下：

步驟1：計算各任務修正加工時間；

步驟2：對各個加工任務按照修正加工時間降序排列；

步驟3：按照步驟2的順序依次安排各個加工任務的順序

步驟3.1：安排任務j至每臺機器上的每個可能位置；

步驟3.2：計算任務j引起的增量完成時間；

步驟3.2：安排任務j至最小增量完成時間的機器和位置。

常見的用于并行機調度的元啟發(fā)式算法有遺傳算法（Genetic Algorithm，GA）、人工蜂群算法（Artificial Bee Colony，ABC）、和迭代貪婪算法（Iterated, Greedy，IG）等。

文獻[10]針對考慮預防性維修的不相關并行機調度問題，設計了一種以最小最大完工時間為目標的人工蜂群算法。通過多個子蜂群的設計，平衡了算法的全局搜索與局部搜索，通過計算驗證算法在計算時間方面相比傳統(tǒng)遺傳算法有一定優(yōu)勢。

文獻[12]在迭代貪婪的框架下設計了一種的解的編碼方式，利用高效的啟發(fā)式構造方法快速實現(xiàn)對任務的分批與調度，取得了比蟻群算法和模擬退火算法更優(yōu)的求解質量。

綜上所述，基于啟發(fā)式算法通常能夠較快的獲得一個可行解，但解的質量不容易得到保證；基于元啟發(fā)式算法能夠對解進行提升，但通常要花費較多的時間。在實際問題處理中，往往需要結合兩種方法，在元啟發(fā)式算法的框架內，設計高效的啟發(fā)式方法，在一定時間內獲得優(yōu)度指標內的解。

參考文獻

[1] 趙詩奎. 基于遺傳算法的柔性資源調度優(yōu)化方法研究[D]. 浙江大學, 2013.

[2] 徐建有. 基于智能優(yōu)化算法的生產調度問題研究[D]. 2015.

[3] Graham R L , Lawler E L , Lenstra J K , et al. Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey[J]. Annals of Discrete Mathematics, 1979, 5(1):287-326.

[4] 邴孝鋒. 考慮機器調整時間的并行機分批優(yōu)化調度研究[D].昆明理工大學,2019.

[5] 鄧冠龍. 基于元啟發(fā)式算法的調度問題若干研究[D]. 華東理工大學.

[6] Baker K R. Heuristic procedures for scheduling job families with setups and due dates[J]. Naval Research Logistics (NRL), 1999, 46(8): 978-991.

[7] Nawaz M, Enscore Jr E E, Ham I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem[J]. Omega, 1983, 11(1): 91-95.

[8] Kurz M E, Askin R G. Heuristic scheduling of parallel machines with sequence-dependent set-up times[J]. International journal of production research, 2001, 39(16): 3747-3769.

[9] Vallada E, Ruiz R. A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times[J]. European Journal of Operational Research, 2011, 211(3): 612-622.

[10] 劉美瑤, 雷德明. 基于新型人工蜂群算法的分布式不相關并行機調度[J]. 控制理論與應用, 2020, 037(005):1080-1089.

[11] Fanjul-Peyro L, Ruiz R. Iterated greedy local search methods for unrelated parallel machine scheduling[J]. European Journal of Operational Research, 2010, 207(1): 55-69.

[12] Arroyo J E C, Leung J Y T, Tavares R G. An iterated greedy algorithm for total flow time minimization in unrelated parallel batch machines with unequal job release times[J]. Engineering Applications of Artificial Intelligence, 2019, 77: 239-254.

運籌優(yōu)化 EI創(chuàng)新孵化Lab

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。