單機加工問題在一般條件下的算法研究

王文禹 段怡丹 陳正瀟 張沐瑤

摘 要 Biskup首次將學習效應(yīng)的約束條件引入排序模型，此后帶有學習效應(yīng)的相關(guān)排序問題受到了眾多學者的關(guān)注。大量學者研究了特定條件下帶有學習效應(yīng)的單機排序問題，并給出了多項式算法的證明。對于更為一般條件下的此類問題，通常使用分枝定界法和啟發(fā)式算法進行求解和對比驗證。本文重點介紹分枝定界算法在帶有學習效應(yīng)的單機排序中的應(yīng)用和幾種常用的啟發(fā)式算法，并給出了一些后續(xù)的研究方向。

關(guān)鍵詞 排序問題 學習效應(yīng) 分枝定界算法 啟發(fā)式算法

中圖分類號：O211.6? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼：A ? ?DOI：10.16400/j.cnki.kjdkx.2020.01.022

Abstract Since Biskup firstly introduced the constraints of learning effects into the scheduling model， the related scheduling problems with learning effects has attracted the attention of many scholars. A large number of scholars have studied the single-machine scheduling problem with learning effects under certain conditions， and the proof of the polynomial algorithm is given. For the scheduling problem under more general conditions， the branch and bound method and the heuristic algorithm are usually used to solve the problem and verify by comparison. This paper focuses on the application of branch and bound algorithm in the single machine scheduling problem with learning effect， summarizes several commonly used heuristic algorithms， and gives some follow-up research directions.

Keywords scheduling problem; learning effect; branch and bound algorithm; heuristic algorithm

1 研究背景

在經(jīng)典調(diào)度模型中，作業(yè)的加工時間通常被視為事先給定的常數(shù)。但是在很多實際情況下，作業(yè)的加工時間會受到加工開始時間或所在隊列位置的影響而縮短，這一現(xiàn)象被稱為“學習效應(yīng)”。

帶有學習效應(yīng)或惡化效應(yīng)的排序模型在生產(chǎn)調(diào)度中有著廣泛的體現(xiàn)。同類工件的加工時間會隨著機器磨合度的增加而縮短;相同程序進程的執(zhí)行時間會隨著計算機資源的占用而導(dǎo)致運行時間延長。一批相似工作的耗時會因為工人的熟練度增加而縮短，也會因為疲勞程度的增加而延長。

自Biskup[1]首次將學習效應(yīng)這一約束條件引入排序模型以來，帶有學習效應(yīng)的排序問題受到了眾多學者的關(guān)注和研究。對于一些具有準備時間、截止日期、群組調(diào)度等不同條件下的單機排序問題，文獻[2-9]等給出了特定情形最優(yōu)解的多項式算法。對于未被證明是多項式問題的具有更一般條件的排序問題，文獻[10-12]使用分枝定界的方法尋找問題的全局最優(yōu)解，提出啟發(fā)式算法快速求出局部最優(yōu)解，并對比與局部最優(yōu)解的誤差進行檢驗。

本文重點介紹分枝定界算法在帶有學習效應(yīng)的單機排序問題中的應(yīng)用，總結(jié)了幾種常用的啟發(fā)式算法，并給出一些后續(xù)的研究方向。

2 分枝定界算法

排序問題是一類組合最優(yōu)化問題。對于具有一般條件的學習效應(yīng)單機排序問題，其計算的復(fù)雜性無法得到解決。已有研究通常使用分枝定界的方法尋找問題的全局最優(yōu)解，這類算法在解決小規(guī)模問題時具有良好的表現(xiàn)。

在極小化目標函數(shù)的排序問題研究中，分枝定界法通常包含遍歷搜索、下界和優(yōu)勢性質(zhì)三個部分。

2.1遍歷搜索

單機排序問題的分支定界法中，每一個節(jié)點對應(yīng)一種完整的排序，以節(jié)點所在層數(shù)為界分為前后兩部分。前半段的作業(yè)排序確定，后半段的作業(yè)排序處于未知狀態(tài)。對于作業(yè)總數(shù)為n的排序問題，以1個全部排序未知的節(jié)點為根節(jié)點，個全部排序已知的節(jié)點為第n層葉節(jié)點，組成排序問題的搜索樹。

節(jié)點的搜索有廣度優(yōu)先搜索（BFS） 和深度優(yōu)先搜索（DFS）兩種搜索算法。應(yīng)用在排序問題當中，兩種算法以不同的方式從頂?shù)较卤闅v整顆搜索樹以找到全局最優(yōu)解。由于計算機實現(xiàn)方式的差異，兩者具有各自的優(yōu)缺點。

BFS每次訪問所有已知節(jié)點中的最優(yōu)節(jié)點，直到找到全局最優(yōu)解。通過保存所有搜索過的節(jié)點信息，以減小重復(fù)訪問的計算量。優(yōu)點是搜索速度較快，缺點是會占用大量內(nèi)存。DFS訪問時只從當前節(jié)點的后續(xù)節(jié)點中選擇最優(yōu)節(jié)點，找到可行解后向上回溯，不會重復(fù)進入已經(jīng)搜索過的節(jié)點。優(yōu)點是占用內(nèi)存很小，缺點是速度相對較慢。

通過對排序算法的數(shù)值仿真可以發(fā)現(xiàn)，BFS在處理規(guī)模較大的問題時會出現(xiàn)內(nèi)存不足的問題，DFS則可以通過延長運行時間來保證得到全局最優(yōu)或較好的局部最優(yōu)解。在目前的研究中，DFS是數(shù)值仿真時常用的搜索方法。

2.2下界

下界是分枝定界算法主要的剪枝方式，其好壞程度極大的影響著分枝定界算法的效率。節(jié)點的下界與該節(jié)點的最佳值誤差很大時，分枝定界幾乎等同于窮舉;而良好的下界可以在計算時快速的進行大量剪枝，使算法在面對較大規(guī)模問題時依舊十分有效。

下界的好壞主要取決于節(jié)點下界計算結(jié)果和節(jié)點最佳值的接近程度，其次是計算過程的時間復(fù)雜度。

下界表達式的推導(dǎo)存在多種理論依據(jù)，參考部分文獻的研究過程，有以下兩種較為普遍的方式：

（1）對于具有一般性的原排序問題模型，通過取極值或特定值等方式統(tǒng)一部分參數(shù)，使得新問題的最優(yōu)解不大于原問題的最優(yōu)解，即找到原問題在更好情況下的一個特例問題（convex那篇）。若新問題是多項式可解的，例如化為指派問題，即可計算出原問題的一個下界。

（2）每個作業(yè)的開始時間受到作業(yè)準備時間和上一作業(yè)完工時間兩項約束。因此，如果只單獨考慮其中一項約束，將原目標函數(shù)縮小，此時新目標函數(shù)的最小值必定小于原問題的最優(yōu)解。當新的目標函數(shù)使用SPT等啟發(fā)式算法可以求得最優(yōu)解時，可以較為容易的得到原問題的一個下界。

2.3優(yōu)勢性質(zhì)

優(yōu)勢性質(zhì)是分枝定界法的另一個剪枝方式。假設(shè)有兩個作業(yè)加工排序A和B，其中只有兩個加工次序相鄰的作業(yè)順序不同。當作業(yè)屬性、排序順序參數(shù)滿足一定條件時，排序A必定優(yōu)于排序B。例如，一個作業(yè)如果準備時間較大且處于最先加工的位置，可以考慮先加工其他作業(yè)而不影響該作業(yè)的開工時間。

使用多條優(yōu)勢性質(zhì)對搜索樹進行剪枝，在下界計算的時間復(fù)雜度較高時，可以有效的加快最優(yōu)解的求解速度。

3 啟發(fā)式算法

已有的文獻和經(jīng)驗表明，對于一些簡單的單機排序問題，存在一些對應(yīng)的啟發(fā)式規(guī)則用于最優(yōu)解的計算。這些啟發(fā)式規(guī)則通常是根據(jù)全部作業(yè)某些屬性的數(shù)據(jù)進行排序以得到最優(yōu)序列。后續(xù)的大量研究證明，很多其他特殊情形的排序問題，同樣可以使用已有的啟發(fā)式規(guī)則得到最優(yōu)解。

對于一般條件的排序問題，使用多種啟發(fā)式規(guī)則得到一個較好的初始解序列，然后使用多項式時間的貪心算法進行遍歷搜索，可以在絕大多數(shù)情況下得到一個誤差較小的局部最優(yōu)解。下面給出了幾種常用的啟發(fā)式規(guī)則。

3.1 WSPT

加權(quán)最短加工時間優(yōu)先（weighted shortest processing time first，簡記WSPT）規(guī)則。該規(guī)則按照 /非增的順序?qū)λ腥蝿?wù)進行排序。

3.2 SPT

最短加工時間優(yōu)先（shortest processing time first，簡記SPT）規(guī)則。SPT規(guī)則按照非減的順序?qū)θ蝿?wù)進行排序，是WSPT規(guī)則在相同時的特殊情形。

3.3 EDD

最早工期優(yōu)先 （earliest due date first，簡記EDD）規(guī)則。EDD規(guī)則按非減的順序?qū)θ蝿?wù)進行排序。

3.4 ECT

最早完工時間優(yōu)先（earliest completion time first）規(guī)則。每當處理機空閑時，在尚未排序且已經(jīng)到達的任務(wù)中，選取最早完工時間最小的任務(wù)加工。如果有多個任務(wù)的最早完工時間相同且最小，則選取最早開工時間最小的任務(wù)。

3.5 EST

最早開始時間優(yōu)先 （earliest start time first） 規(guī)則。當處理機空閑時，在后續(xù)任務(wù)中選取最早開始時間最小的任務(wù)加工。如果有多個，則選取完工時間最小的任務(wù)。

3.6針對特定問題的其他規(guī)則

除了具有代表性的啟發(fā)式算法外，一些文獻針對特定的問題，以作業(yè)參數(shù)的某種函數(shù)值作為基準，提出了新的啟發(fā)式規(guī)則。相比于基礎(chǔ)的啟發(fā)式規(guī)則，適合自身目標函數(shù)的啟發(fā)式規(guī)則通常在尋求初始解時有更好的表現(xiàn)。

4 總結(jié)

本文對于帶有學習效應(yīng)的單機排序問題的文獻進行了研究和總結(jié)，介紹了針對一般條件下的兩種求解算法。其中，分枝定界法用于求出全局最優(yōu)解，面對大規(guī)模問題時會花費難以允許的時間。啟發(fā)式算法可以在極短時間內(nèi)得到一個誤差未知的局部最優(yōu)解。其中，分枝定界的下界和啟發(fā)式算法的初始解都由多項式算法決定。因此，本文認為存在以下三個研究方向。第一，對于廣泛的排序問題，尋找多項式時間的求解算法依然重要。多項式問題數(shù)量的增加可以為分枝定界法的下界的計算表達式提供更多的方向選擇和理論依據(jù)，減小節(jié)點下界和節(jié)點最優(yōu)值的百分差，提高分枝定界法的剪枝效率。第二，對于一般條件的學習效應(yīng)單機排序問題，基于已解決的多項式問題和當前問題的特殊性質(zhì)，尋求和準確值差值更小的下界計算表達式，以增加一定時間內(nèi)的可以解決的問題的規(guī)模。第三，對于一般條件的排序問題，可以尋求誤差更小的啟發(fā)式規(guī)則計算初始解。若得到的局部最優(yōu)解的誤差在允許范圍之內(nèi)，啟發(fā)式算法和分枝定界等算法相比將在運行時間上具有巨大的優(yōu)勢。

參考文獻

[1] Biskup D. Single‐machine scheduling with learning considerations[J]. European Journal of Operational Research，1999.115（1）：173-178.

[2] 王吉波. 工件加工時間可變的現(xiàn)代排序問題[D].大連理工大學，2005.

[3] 陶明子，趙傳立.具有安裝時間和學習效應(yīng)的單機排序問題[J].運籌與管理，2010.19（04）：101-107.

[4] 胡晨晨. 帶有學習及退化效應(yīng)的排序問題[D].沈陽師范大學，2015.

[5] 白靜，劉璐，王吉波.具有截斷學習效應(yīng)和工件帶準備時間的單機排序問題[J].運籌與管理，2014.23（06）：152-156.

[6] 王利巖.工件具有學習與惡化效應(yīng)的現(xiàn)代排序問題研究[D].大連理工大學，2014.

[7] 劉洋.具有學習效應(yīng)和退化效應(yīng)的單機排序問題[D].沈陽師范大學，2011.

[8] 陶明子，趙傳立.具有學習效應(yīng)和非線性安裝時間的單機排序問題[J].沈陽師范大學學報（自然科學版），2010.28（01）：8-11.

[9] 胡晨晨，趙玉芳.同時帶有安裝時間和送出時間的單機排序問題[J].沈陽師范大學學報（自然科學版），2015.33（03）：351-357.

[10] 趙傳立.具有學習效應(yīng)的排序問題的某些新進展[J].沈陽師范大學學報（自然科學版），2014.32（4）：453-460. DOI：10.3969/j.issn.1673-5862.2014.04.001.

[11] 王吉波，劉璐.帶準備時間的任務(wù)單機學習效應(yīng)排序問題[J].大連理工大學學報，2013，53（06）：930-936.

[12] 閆萍，王吉波，趙禮強.帶準備時間的單機指數(shù)時間學習效應(yīng)排序問題[J].運籌與管理，2017.26（11）：70-76.