延遲時間最小化

吳蘇寒

[摘 要] 多任務(wù)處理與排序論的跨領(lǐng)域組合，可以解決現(xiàn)實生活中許多面臨尋找“最優(yōu)解”或“近似解”的問題。旨在討論解延遲時間最小化問題。選取經(jīng)典排序論模型，考察資源與工作之間通過合理的時間安排，以實現(xiàn)目標(biāo)函數(shù)的要求。經(jīng)典算法中常用SPT排序和EDD排序來解決單機器排序問題，但對某些問題則只能給予近似解，因此在此基礎(chǔ)上由SPT與EDD排序方法產(chǎn)生了很多啟發(fā)式算法。因為基本問題的總時間（∑T）本身為NP-hard問題，所以我們用一種啟發(fā)式算法——禁忌搜索（Tabular Search）算法實現(xiàn)單機器以總延遲最小為目標(biāo)函數(shù)在兩種特殊情形下的近似解?？紤]到多任務(wù)處理的情況，額外增加了轉(zhuǎn)換時間模塊（f（·））與打斷時間模塊（g（·）），目標(biāo)函數(shù)因此變化為∑（Cj-Tj）·Uj。

[關(guān) 鍵 詞] 多任務(wù)處理（multitasking）；排序論（scheduling）；總延遲時間最?。╩inimize total tardiness time）

[中圖分類號] G712 [文獻標(biāo)志碼] A [文章編號] 2096-0603（2018）05-0084-02

一、研究背景及現(xiàn)狀

排序是指將多項工作按照一定的順序進行安排，即根據(jù)不同的需求和影響因素，排序計劃也不盡相同。多任務(wù)處理是指由一臺處理器同時對兩個及以上的工作進行作業(yè)，所有被處理的工作均可在任何時間點進行停止和繼續(xù)處理，多任務(wù)處理能力則被描述為“處理器同時處理多項工作的表現(xiàn)”（Merriam-Webster Online 2014）。Loeb和Alluisi（1977）提到，可以通過工作速度的加快來增加價值。Pinedo（2012）提出了經(jīng)典搶占式調(diào)度的概念，得到了一些多項式時間的算法。而Jarrehult（2012）在多項行業(yè)研究中得到，每當(dāng)工作數(shù)量由1增加為2時，生產(chǎn)力損失約20%；當(dāng)增加為3個工作時，生產(chǎn)力損失約為50%。介于不同工作進行更替作業(yè)的過程中，由于多種原因，會有部分時間被浪費，這些被浪費的時間即使是電腦進行多任務(wù)處理也會產(chǎn)生（Samia 2007）。

Hall等人（2014）總結(jié)，現(xiàn)今機器處理過程與多任務(wù)排序問題主要有四種常見目標(biāo)函數(shù)，即1mt∑WjCj，1mtLmax，1mt∑Uj，1mt∑WjUj。若我們對約束條件不加以約束，以上問題中1mtLmax，1mt∑Uj，1mt∑WjUj均為NP-hard，若我們約束g（·），則可得到最優(yōu)解。因此我們思考，在多任務(wù)排序問題中，對約束條件g（·）進行合理的假設(shè)，雖然部分降低了結(jié)論的普遍性，但在很大程度上使問題的復(fù)雜度得到了質(zhì)的變化。

二、研究內(nèi)容

我們選擇研究的問題是“總延遲時間最小”，目標(biāo)函數(shù)為：T=∑（cj-dj）·Uj。我們選擇研究這個問題的出發(fā)點在于，這個問題不屬于最常見的四種研究問題中，在單機器排序問題中雖然有較為深刻的研究，并且由于是NP-hard暫時只有啟發(fā)式算法，但在多任務(wù)領(lǐng)域方面研究較少，屬于比較空白的區(qū)域，但這個問題仍能在許多現(xiàn)實生活中使用到。

本文擬依據(jù)Nicholas G.Hall、Joseph Y.T.Leung、Chung-Lum Li的工作，將模型中的“資源”與“工作”在時間軸中進行排序，并且建立定量化模型，在兩種特殊情形下，給出算法，并分析其可行性，通過構(gòu)造并移動初始解的方法，實現(xiàn)不同資源之間的價值比較，并評估排序效果。

三、數(shù)學(xué)模型

我們用國際通用的三參數(shù)法αβγ來表示約束條件和目標(biāo)函數(shù)，α其中表示機器環(huán)境，β表示工件特性，γ表示目標(biāo)函數(shù)。

對每一個序列中的任務(wù)，當(dāng)任務(wù)i作為主任務(wù)時，被插入兩個額外時間段：f（·）與g（·）。且當(dāng)i≠1時，p′i≠pi，總處理時間為p′i+f（i）+gi（p′i）。為簡化表達式，且■（pi+f（i）+gi（p′i））=■Cj，因此，對我們要考慮的最小總時間問題，將通過總時間T=∑（cj-dj）·Uj取最小值來體現(xiàn)。

（一）主任務(wù)、副任務(wù)基本假設(shè)

主任務(wù)：在任務(wù)序列加工時，依次以某個任務(wù)被加工完成為目標(biāo)實現(xiàn)任務(wù)處理過程，在此期間若這個任務(wù)不為最后一個任務(wù)，這個任務(wù)會被其他任務(wù)打斷，使這個任務(wù)在此加工期間時間變長，我們將當(dāng)前狀態(tài)下需要被加工完成的任務(wù)稱之為主任務(wù)。

在這個任務(wù)序列中，每個任務(wù)都會且僅會有一次成為主任務(wù)。

副任務(wù)：當(dāng)主任務(wù)被處理時，打斷主任務(wù)的其他任務(wù)的集合為副任務(wù)。每完成一個主任務(wù)，主任務(wù)和副任務(wù)將被更新。

特別地，任務(wù)序列中第一個任務(wù)在過程中不作為副任務(wù)，序列中第二個任務(wù)有一次作為副任務(wù)……第n個任務(wù)有n-1次作為副任務(wù)。

（二）打斷模塊基本假設(shè)

我們用g（·）表示打斷模塊。

我們現(xiàn)做如下兩種約束：

約束一：當(dāng)每個主任務(wù)被加工時，插入的副任務(wù)打斷部分與相對應(yīng)的副任務(wù)的剩余時間成正比，且每次比例恒定為D（0<1

約束二：當(dāng)每個主任務(wù)被加工時，插入的副任務(wù)打斷部分為固定時間K，若對某個副任務(wù)有g(shù)′

（三）轉(zhuǎn)換模塊基本假設(shè)

我們用f（·）表述轉(zhuǎn)換模塊，可以為正值、零或者負(fù)值。其中正值表示轉(zhuǎn)換過程需要耗費額外時間，即轉(zhuǎn)換過程需要對工作進行新的認(rèn)識等過程；轉(zhuǎn)換時間為負(fù)值表示轉(zhuǎn)換過程兩者存在一定的相關(guān)性；轉(zhuǎn)換模塊為零，表示主任務(wù)與副任務(wù)之間的切換過程可能不存在轉(zhuǎn)換摩擦。

四、特殊情形下的最優(yōu)任務(wù)序列算法的可行性分析

穩(wěn)定打斷指打斷模塊的判斷條件為：不改變副任務(wù)剩余處理時間序列順序。下面，我們就一種特殊情形，進行算法可行性分析。

特殊情形：ci>di & ci+1>di+1，？坌ji∈N，cj>dj（ji∈N）

假設(shè)有兩個任務(wù)，用下圖表示流程圖：

其中黑色部分分別表示f（1）和f（2），白色部分分別表示g（1）和g（2）。

則總目標(biāo)值為：[p1+f（1）+g（1）-d1]+[p1+f（1）+g（1）+（1-D）p1+f（2）+g（2）-d2]=c1-d1+c2-d2

類似可推導(dǎo)得，當(dāng)有n個任務(wù)時，目標(biāo)函數(shù)為：

■Tj=■Cj-■dj

（一）gi（p′i）=D·p′i

我們討論兩個相鄰的工作pj和pj+1，簡單起見，令j=1：

我們先求解兩個任務(wù)的排序規(guī)則：

設(shè)有任務(wù)ja，jb，pa>pb且ca>da，cb>db.a、b之前的任務(wù)為ja-1.

目標(biāo)函數(shù)：T=ca-da+cb-db

先令約束條件：gi（p′i）=D·p′i

排序a、b狀態(tài)下，ca=ca-1+p′a+D·h（a）

cb=ca+p′b+D·h（b）=ca-1+p′a+D·h（a）+p′b+D·h（b）

排序b、a狀態(tài)下，cb=ca-1+p′b+D·h（b）

ca=cb+p′a+D·h（a）=ca-1+p′b+D·h（b）+p′a+D·h（a）

需要注意的是，上面4個式子并不能簡單聯(lián)立求解，因為其中h（a），h（b），pa，pb并不相同。令a、b排序目標(biāo)函數(shù)為Tab，b、a排序目標(biāo)函數(shù)為Tba.

于是，Tab-Tba=D·（p′a+p′b），其中p′a，p′b表示兩者進入排序前為完成的處理時間。

由此得到結(jié)論，在da=db，pa>pb，前提下，先排序處理時間短的工作。

通過遍歷的方式，我們得到了兩者之間的排序關(guān)系，下面證明三者聯(lián)立關(guān)系：

假設(shè)存在三個工作ja，jb，jc，da=db=dc，pa>pb>pc，a、b、c之前的任務(wù)為ja-1。

首先我們假設(shè)存在工作路徑a、b、c，做如下局部調(diào)整：（1）觀察最小工作時間工作jc，當(dāng)ja固定在序列第一位時，即將ja作為上面證明中存在的ja-1，則問題變?yōu)閖b，jc的兩者排序問題。因為在序列a、b、c與a、c、b中，Ta不變，Tb，Tc會因位置的改變而改變。同時我們觀察到，若交換b、c位置，對其他工作均無影響，并且顯然序列a、c、b更優(yōu)，兩種排序方式ΔT=D·（p′b+p′c）。（2）在新的序列a、c、b中繼續(xù)優(yōu)化jc位置，顯然jc應(yīng)當(dāng)和ja交換位置，得到新的排序為c、a、b，在這里我們直接給出ΔT=D·（p′a+p′c）。（3）尋找p次小的工作，為jb。交換b、c位置，得到排序c、b、a。ΔT=D·（p′a+p′b），完成排序。

我們可以看到，當(dāng)符合約束條件時，多個任務(wù)的多任務(wù)排序策略為SPT排序。分析約束條件為：gi（p′i）=D·p′i，D∈（0，1），？坌ji∈N，cj>dj。

以上第一條約束條件使多任務(wù)排序的打斷規(guī)則簡單化，第二條約束令Uj取值單一化。

易知每當(dāng)一個主任務(wù)被完成時，所有未完成任務(wù)剩余處理時間都會變短。由于當(dāng)我們設(shè)置g（pi）=D·g（p′i）時，所有工作剩余時間按比例減少100D%，因此我們不必考慮p′排序。在下面我們令p′i=gi（p′i），我們將需要考慮每次更新之后的p′排序問題。又因為每次更新后p′總是減小或不變的，因此我們可以通過逐次更新cK從而實現(xiàn)排序。實現(xiàn)過程如下：（1）我們設(shè)置空集R用于存放排序的工作。在每次插入工作jK至R之前，我們分別計算：每個工作的剩余時間、每個工作作為主任務(wù)時的轉(zhuǎn)換模塊fK（·）及其處理模塊gK（·）；（2）我們設(shè)置變量i=0，并在開始時，置R為空集；（3）我們分別計算每個工作的剩余時間hK（i）、當(dāng)此工作作為主任務(wù)時的轉(zhuǎn)換時間為f（n-i-1），處理時間為∑i∈N＼Rg（l）-g（pk）；（4）我們選取min{hk（i）+f（n-i-1）+∑i∈N＼Rg（l）-g（pk）}k的任務(wù)k，將其從N中取出，并且放入R中；（5）i的值增加1，若N不為空集，則返回步驟4；若N為空集，則表示所有工作均已排序。此時集合R即為工作的新的排序序列。

我們給出這個算法復(fù)雜度為O（n2）。

（二）gi（p′i）=K，？坌ji∈N，cj>dj

假設(shè)有兩個任務(wù)，由前所述，總目標(biāo)值為：c1-d1+c2-d2

我們?nèi)耘f討論兩個相鄰的工作pj和pj+1：

我們通過如下判斷求解兩個任務(wù)的排序規(guī)則：

設(shè)有任務(wù)ja，jb，pa>pb且ca>da，cb>db. a、b之前的任務(wù)為ja-1.

目標(biāo)函數(shù)：T=ca-da+cb-db

排序a、b狀態(tài)下，ca=ca-1+p′a+（a-1）·K

cb=ca-1+p′a+（a-1）·K+p′b+bK

排序b、a狀態(tài)下，cb=ca-1+p′b+（b-1）·K

ca=ca-1+p′b+（b-1）·K+p′a+aK

于是，Tba-Tab=p′a-p′b>0，其中p′a，p′b表示兩者進入排序前為完成的處理時間。

由此得到結(jié)論，在da=db，pa>pb前提下，先排序處理時間短的工作。

通過與（一）相同的遍歷方式，我們同樣可以證明三者的聯(lián)立關(guān)系。

我們可以觀察到，不論是gi（p′i）=D·p′i或是gi（p′i）=K，由剩余工作時間p′i的角度來觀察，每進行m次打斷后，剩余時間分別為（1-D）mpi，pi-mK，對剩余時間序列并未影響，因此對gi（·）模塊，若對原本剩余工作時間排序無序列影響，則其結(jié)果并不會改變。

通過（一）與（二）的對比，我們可以提出“穩(wěn)定打斷”的概念，即副任務(wù)的打斷模塊之間存在不改變剩余時間長短排序序列的規(guī)律。

五、結(jié)論

四（一）的論述中，我們給出“穩(wěn)定打斷”的概念，目的在于對我們的假設(shè)條件之一的打斷模塊g（·）的假設(shè)予以解釋。與前人相比，我們從另一個角度討論了打斷模塊的性質(zhì)滿足其處于“穩(wěn)定打斷”狀態(tài)下即可。這樣我們就解放了g（·）的表達形式，不再局限于傳統(tǒng)的gi（p）=D·p′i或gi（p）=K。

我們在某一特殊情形（ci>di & ci+1>di+1）產(chǎn)生了在經(jīng)典排序基礎(chǔ)上加以改進的思路，并借鑒了王夢蘭的處理非多任務(wù)狀況下的改進禁忌算法，即一種模仿人類思維方式的算法，進行構(gòu)造移動，以實現(xiàn)最終得到一個對結(jié)果進行改進的目的。

此外，本文仍有許多不足之處，如（1）我們證明該算法在特殊情況下可以達到多個任務(wù)的判斷，但無法證明當(dāng)任務(wù)數(shù)量較大時，兩個相距較遠(yuǎn)的任務(wù)之間交換會產(chǎn)生怎樣的后果。即我們只能做到局部優(yōu)化，但無法證明局部優(yōu)化會不會實現(xiàn)整體最優(yōu)化，即實現(xiàn)最優(yōu)解。（2）我們的改進依賴于起始解，但本文中并未給出起始解需要什么樣的特性。（3）我們只在一種特殊情形下證實了算法的可行性，沒有推廣到一般的情況。

綜上可知，在未來的研究中，我們?nèi)钥捎懻揷idi+1，ci>di & ci+1

參考文獻：

[1]Samia Aslam Sherwani，Malik Sikander Hayat Khiyal. Real-time Scheduler for Transport Protocols[J].Information Technology Journal，2007，6（3）.

[2]唐國春.排序、經(jīng)典排序和新型排序[J].數(shù)學(xué)理論與應(yīng)用，1999（3）.

[3]王夢蘭.一類單機排序問題的改進禁忌搜索算法[J].中國水運，2013（3）.

[4]Loeb，M.，E.A. Alluisi. An update of findings regarding vigi-lance and a reconsideration of underlying mechanisms[J]. Springer US，1977（3）.