延遲時間最小化

吳蘇寒

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

[關 鍵 詞] 多任務處理（multitasking）；排序論（scheduling）；總延遲時間最小（minimize total tardiness time）

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

一、研究背景及現狀

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

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

二、研究內容

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

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

三、數學模型

我們用國際通用的三參數法αβγ來表示約束條件和目標函數，α其中表示機器環境，β表示工件特性，γ表示目標函數。

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

（一）主任務、副任務基本假設

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

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

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

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

（二）打斷模塊基本假設

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

我們現做如下兩種約束：

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

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

（三）轉換模塊基本假設

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

四、特殊情形下的最優任務序列算法的可行性分析

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

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

假設有兩個任務，用下圖表示流程圖：

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

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

類似可推導得，當有n個任務時，目標函數為：

■Tj=■Cj-■dj

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

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

我們先求解兩個任務的排序規則：

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

目標函數：T=ca-da+cb-db

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

排序a、b狀態下，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狀態下，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個式子并不能簡單聯立求解，因為其中h（a），h（b），pa，pb并不相同。令a、b排序目標函數為Tab，b、a排序目標函數為Tba.

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

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

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

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

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

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

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

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

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

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

假設有兩個任務，由前所述，總目標值為：c1-d1+c2-d2

我們仍舊討論兩個相鄰的工作pj和pj+1：

我們通過如下判斷求解兩個任務的排序規則：

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

目標函數：T=ca-da+cb-db

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

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

排序b、a狀態下，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表示兩者進入排序前為完成的處理時間。

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

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

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

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

五、結論

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

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

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

綜上可知，在未來的研究中，我們仍可討論cidi+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].數學理論與應用，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）.