吴苏寒

[摘 要] 多任务处理与排序论的跨领域组合，可以解决现实生活中许多面临寻找“最优解”或“近似解”的问题。旨在讨论解延迟时间最小化问题。选取经典排序论模型，考察资源与工作之间通过合理的时间安排，以实现目标函数的要求。经典算法中常用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）.