吳蘇寒

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

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

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

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

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

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

二、研究內(nèi)容

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

假設(shè)有兩個(gè)任務(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個(gè)任務(wù)時(shí)，目標(biāo)函數(shù)為：

■Tj=■Cj-■dj

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

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

我們先求解兩個(gè)任務(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個(gè)式子并不能簡單聯(lián)立求解，因?yàn)槠渲衕（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表示兩者進(jìn)入排序前為完成的處理時(shí)間。

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

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

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

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

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

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

易知每當(dāng)一個(gè)主任務(wù)被完成時(shí)，所有未完成任務(wù)剩余處理時(shí)間都會(huì)變短。由于當(dāng)我們?cè)O(shè)置g（pi）=D·g（p′i）時(shí)，所有工作剩余時(shí)間按比例減少100D%，因此我們不必考慮p′排序。在下面我們令p′i=gi（p′i），我們將需要考慮每次更新之后的p′排序問題。又因?yàn)槊看胃潞髉′總是減小或不變的，因此我們可以通過逐次更新cK從而實(shí)現(xiàn)排序。實(shí)現(xiàn)過程如下：（1）我們?cè)O(shè)置空集R用于存放排序的工作。在每次插入工作jK至R之前，我們分別計(jì)算：每個(gè)工作的剩余時(shí)間、每個(gè)工作作為主任務(wù)時(shí)的轉(zhuǎn)換模塊fK（·）及其處理模塊gK（·）；（2）我們?cè)O(shè)置變量i=0，并在開始時(shí)，置R為空集；（3）我們分別計(jì)算每個(gè)工作的剩余時(shí)間hK（i）、當(dāng)此工作作為主任務(wù)時(shí)的轉(zhuǎn)換時(shí)間為f（n-i-1），處理時(shí)間為∑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為空集，則表示所有工作均已排序。此時(shí)集合R即為工作的新的排序序列。

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

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

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

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

我們通過如下判斷求解兩個(gè)任務(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表示兩者進(jìn)入排序前為完成的處理時(shí)間。

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

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

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

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

五、結(jié)論

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

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

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

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

參考文獻(xiàn)：

[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ī)排序問題的改進(jìn)禁忌搜索算法[J].中國水運(yùn)，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）.