單機(jī)加工問(wèn)題在一般條件下的算法研究

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

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

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

中圖分類號(hào)：O211.6? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：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í)間通常被視為事先給定的常數(shù)。但是在很多實(shí)際情況下，作業(yè)的加工時(shí)間會(huì)受到加工開始時(shí)間或所在隊(duì)列位置的影響而縮短，這一現(xiàn)象被稱為“學(xué)習(xí)效應(yīng)”。

帶有學(xué)習(xí)效應(yīng)或惡化效應(yīng)的排序模型在生產(chǎn)調(diào)度中有著廣泛的體現(xiàn)。同類工件的加工時(shí)間會(huì)隨著機(jī)器磨合度的增加而縮短;相同程序進(jìn)程的執(zhí)行時(shí)間會(huì)隨著計(jì)算機(jī)資源的占用而導(dǎo)致運(yùn)行時(shí)間延長(zhǎng)。一批相似工作的耗時(shí)會(huì)因?yàn)楣と说氖炀毝仍黾佣s短，也會(huì)因?yàn)槠诔潭鹊脑黾佣娱L(zhǎng)。

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

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

2 分枝定界算法

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

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

2.1遍歷搜索

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

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

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

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

2.2下界

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

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

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

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

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

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

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

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

3 啟發(fā)式算法

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

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

3.1 WSPT

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

3.2 SPT

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

3.3 EDD

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

3.4 ECT

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

3.5 EST

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

3.6針對(duì)特定問(wèn)題的其他規(guī)則

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

4 總結(jié)

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

參考文獻(xiàn)

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

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

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

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

[5] 白靜，劉璐，王吉波.具有截?cái)鄬W(xué)習(xí)效應(yīng)和工件帶準(zhǔn)備時(shí)間的單機(jī)排序問(wèn)題[J].運(yùn)籌與管理，2014.23（06）：152-156.

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

[7] 劉洋.具有學(xué)習(xí)效應(yīng)和退化效應(yīng)的單機(jī)排序問(wèn)題[D].沈陽(yáng)師范大學(xué)，2011.

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

[9] 胡晨晨，趙玉芳.同時(shí)帶有安裝時(shí)間和送出時(shí)間的單機(jī)排序問(wèn)題[J].沈陽(yáng)師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2015.33（03）：351-357.

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

[11] 王吉波，劉璐.帶準(zhǔn)備時(shí)間的任務(wù)單機(jī)學(xué)習(xí)效應(yīng)排序問(wèn)題[J].大連理工大學(xué)學(xué)報(bào)，2013，53（06）：930-936.

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