CN1218260C

CN1218260C - 用于任务分配的设备和方法

Info

Publication number: CN1218260C
Application number: CN971800049A
Authority: CN
Inventors: 戴维·勒桑; 克里斯托斯·沃多利斯; 纳德·阿扎米; 罗伯特·诺埃尔·威廉·莱思韦特; 约翰·约瑟夫·奥多诺林; 安德鲁·保罗·诺布尔; 保罗·沃克; 伊恩·斯图尔特·阿莱特松
Original assignee: VIDUSS Ltd
Current assignee: Trimble Inc
Priority date: 1996-11-22
Filing date: 1997-11-12
Publication date: 2005-09-07
Anticipated expiration: 2017-11-12
Also published as: WO1998022897A1; DE69703938T2; AU4957397A; US6578005B1; DE69703938D1; EP0938714B1; CN1238849A; EP0938714B2; EP0938714A1; HK1022539A1; JP2001504257A; ES2155678T3; ES2155678T5; DE69703938T3; AU722806B2

Abstract

通过一种方法将多个资源，典型的如服务人员，分配到多个任务，此方法首先是提供有关欲加以分配的任务和可用来完成这些任务的资源的初始信息，首先生成将资源分配给任务的初始系列规划列，然后按照更新信息修正至少一资源的个别规划，由此而能按照这样的更新信息独立于规划生成装置对个别规划作出改变。此初始系列规划可在两阶段的过程中生成，其中，一基于规则的系统(30)对被选择认为是难以分配(例如因为它们被连系到其它任务)的任务进行分配，而后一随机的(非系统的)搜索系统(31)对规划的其余部分进行编辑。可周期地中断此随机系统以便使另一基于规则的系统(39)能对直至当前所生成的规划进行分析，确定规划中的最佳部分，从而使得随机系统(31)随后致力于完善其余的规划。为了使系统能以较之为生成此规划所需时间更快的规模处理任务和资源所要求的迅速变化，配置一规划修正系统(40)以在短期限内在由规划生成系统(30，31)所传送的规划更新之间进行改变。

Description

用于任务分配的设备和方法

技术领域

本发明是关于用于优化多个资源到多个任务分配的方法，和关于用于实现这样的方法的设备。它特别适用于资源的可行性和欲完成的任务双方均动态变化的情况。这样的情况的示例是对例如救护车或计程车司机等的现场人员、车辆检查呼唤现场人力、或用于分布式系统例如供电或供水系统或者远程通信网络的维护现场人力的任务的分配。

背景技术

在这样的情况中工作负荷容易发生很大变化，和必须作任务的实时分配，因为所需响应时间为与任务本身的时间期限数量级相当，远远低于技术人员的工作日。个别任务的时间期限本身有很大不同而且常常无法预测，这影响对这些等待分配的任务的资源的可用性。

国际专利申请No.WO95/26535中描述一先有技术系统，其中对各资源估算可行的时间。每一任务均被指定一与时间相关的函数，后面称为“成本函数”。这一成本函数为在给定时间被分配给任务的资源的后续结果的量度。例如，如果一资源未能在一已对客户承诺的截止时间内被分配，可对此客户作适当的补偿。其他因素有去往、来自和在任务之间的花费时间和闲置时间(如果一资源不能立即执行下一个所分配的并且是它所能执行的任务时所发生的，例如在获得访问允许之前或在进行该系列中前一个任务之前)。可为每一个与资源相结合的任务确定一预计的成本。这一成本是针对各任务在分配到它的资源可用来执行它时的与时间相关的函数的值的总和。然后确定给出最低总和成本的组合。

在上述专利中还揭示了保证不会分配不相兼容的任务/资源组合和通过对任务和资源作优先级排列来降低计算的复杂性的另外特点。依靠周期地运行程序(例如每5分钟一次)或按照要求(例如在一技术人员要求一新任务时，或在要求把一新任务加到系统时可保持更新分配规划)。

这一系统需要大量处理功率，因为整个分配规划是每次程序运行时的快速记录构成的。这样的配置在当分配标准本身相对简单时即使可能涉及到许多单个元件(任务和资源)也是可能的。在当任务或所涉及人员间存在复杂的相互关系时问题就成为较难以处理。例如为了确定两个地点之间连接的整体性某些任务可能在不同地方同时需要二个或更多人员。在其他的环境中，任务有可能必须以指定的序列执行，和它们的执行可能要求不同的人员。

因为先有技术系统是实时进行的，可用于运行程序的时间有限，所以事先只能规划一个任务，或者最多仅非常少量的任务。这很可能导致一较长期间内的次最佳的规划，特别是如果涉及占一天的大部分或者甚至数天的任务时，因为在这样的系统中不能容易地考虑到较长期间中的资源的可用性。

采用这一实时处理的另一问题是当在具有一高优先级的任务和数个技术人员能完成它时，上述的先有技术实时过程将其规划作为一指定的个别技术人员的下一任务。这将正常地按照哪一技术人员最接近此任务的地理位置和预计谁最先完成它们当前任务的来进行选择。但是如果所选择技术人员在其当前任务上延迟了，而使得此下一任务的目标时间受到危害，可用的其他技术人员不能取代他被加以分配，除非重新进行整个规划处理。在发生这一点之前，任务将一直维持为第一技术人员的规划。

一易于处理复杂的相互关系和长期间任务的替代方法是针对全天(或者更长)建立规划。这可通过对其分配多个计算机时间来非常严密地进行(例如终夜地)。但是结果并不易于适应变化的环境，仅仅是因为专用于在第一位置准备它的大量的计算机时间。

G J Garwood和A C Robinson的“工作管理系统”(BritishTelecommunication Engineering Journal，Vol.10，Oct.1991)提出运行二不同系统，一个是按照上述二方法的每一个：-“实时”系统用于处理相对直观但是紧急的情况，它适用于作实时规划，和一“规划建立”系统用于较复杂但不太紧急的情况，它较适应复杂但慢得多的规划处理。但这有许多缺点。首先，必须作出哪些资源和任务应分配到各系统的初始决定。资源不能在系统之间来回交换(例如在一系统中执行短时间任务来在另一系统中二较大任务之间加以填补)。在此二系统之间可提供连接，以便如果一个复杂规划由于料想不到的原因可能失效，不再能执行原先的复杂规划或在原先的复杂规划中被执行的资源和任务能被转移到实时规划系统。但是，此实时规划系统不能被配置成便于处理这样的任务。特别是，实时任务规划器限于仅考虑其目标时间紧迫的任务，因为快速响应的需要而排除对任何其他任务的检验。

发明内容

按照本发明提出的任务分配设备包括：

输入装置，用于提供有关要加以分配的任务和可用于执行这些任务的资源的信息；

规划生成装置，分配资源到任务，由此为各资源生成一初始规划；

存储装置，用于存放初始规划；

更新装置，用于由输入装置接收有关任务和资源的更新信息；和

修正装置，用于响应这样的更新信息而修正至少一第一资源的初始规划，

由此，而能独立于规划生成装置响应这些更新信息来改变初始规划。

按照另一个方面提出一种将多个资源分配给多个任务的方法，此方法包括应用一计算机来执行如下功能：

提供有关欲加分配的任务和可用于执行这些任务的资源的初始信息；

对各资源生成初始规划以分配资源到任务；

存储此初始规划；

提供有关任务和资源的更新信息；和

响应这些更新信息修正至少一第一资源的初始规划；

由此即可独立于生成初始规划的处理响应这些更新信息来改变个别规划。

在这种配置中，二基本处理之间具有较之在先有技术配置中观察到的更密切的协作关系。初始规划从因某种原因难以规划的任务建立，然后利用更新信息来完成或修正这一规划。

最好周期地生成初始规划，并响应初始规划的这种周期性生成之间的数据的接收来修正如此生成的初始规划。这种周期性可由用户选择以适合其自身需要。如果相当频繁地生成此规划，用户就可利用会保证当前的初始规划为最新的占优势的初始生成过程进行处理，仅需用生成处理的运行之间的新数据修正少量规划。另一方面，如果不是频繁地生成规划，修正处理将占主导(因为从生成处理的最后一次运行起已经修正较多的规划)，但这使得更新之间能有更多时间来生成较严密的方案。

而且，用户可选择由每次处理所执行的该处理的多少。由初始处理所作的越多，所生成的规划就越严密。但这也需要更多的处理时间，这期间正在生成的规划随着输入数据的到达就成为过时的。在初始规划的周期生成期间修正处理可暂停执行，在其生成完成时更新信息被用来修正此初始规划。另一方面，在生成初始规划期间修正处理也可继续进行，在其生成完成时将这样修正的规划作为对初始规划的修正加以输入。

如果接收到重大更新数据项，这将使现有的规划或者那些当前正生成中的规划成为多余的，则此规划生成处理可以在一不同于由上面引用的周期性确定的时间被启动。

在一优选配置中，此规划生成功能包括一用于规划所选择任务的第一决定性级，和用于规划其余任务的第二优化级，而其中第二级将经第一级规划的任务作为固定的加以处理。在此优选实施例中第二级按一随机过程进行。

最好，通过第一决定性级选择涉及多于一个资源或构成一系列任务的链接任务组以编制规划。

这种体系结构使得规划可在数个阶段中进行，其中以更能变化的但也更易的方式将以不同方式处理的任务分配到较难以分配但不太易改变的任务上。此系统很方便地被配置成能周期地生成优化规划，修正处理在这样的规划的生成之间作短期改变。这使得规划生成处理能有较多时间来生成每一规划，使之能生成更理想的方案，和/或应用较之在如果其运行时间因需要实时跟踪短期变化而受限制的情况时更多的数据(例如在时间上进一步领先地)。

所述体系结构是模块式的，所以各个的规划的生成和修正阶段可以是各自适应或独立于其他可被加以置换的。

此说明书中的术语“决定性的”和“随机的”应被理解为在二级的不同操作方法之间是有区别的。决定性级按照由操作系统的人根据经验输入到系统的分配规则运行来生成局部的规划。此局部规划是用于规划那些被选择输入到它的任务的一严密地确定的理想方案。接着，优化级将另外的较易于规划的任务加到此局部规划以生成一完全的但通常不是最佳的规划，然后寻求对该非理想方案的完善，但要限制于不能改变由决定性级所生成的方案的这些部分。在所说明的实施例中，优化处理是一Simulated Annealing(模拟熟练)处理过程。这是随机搜索技术一例，即，一采用限定随机处理的搜索技术；亦即利用约束或者加权在最可能取得方案的区域而不是觉察到认为是不大可能的完整的区域中搜索的应用随机性元件的处理。这些技术有利于用在要加搜索的“方案空间”具有公知的一般特性时寻求接近最佳方案。其他的随机技术，如将说明的，例如“爬山法”(Hill Climbing)、“表格搜索”(Tabu Search)和“原生算法”(Genetic Algorithm)技术，或穷尽系统搜索可以在适当环境中应用。此规划生成装置还可以包括一第三、后优化级，在此对由优化级所生成的规划进行分析来识需要进一步优化的各个的规划，并将这样的规划输入进优化级的另一次重复作进一步优化，优化级的此另一次重复将未被这样标识的规划作为固定的对待。

规划修正处理可包括多个选择步骤，在每一步骤中对等待执行的多个任务进行评估以确定由第一资源(典型地为在要求新任务中已报告的一个)给定的适于执行的优先级的任务是否可行，并在如果被标识出则将这样的任务分配到第一资源，每一个选择步骤被配置为标识优先级降低的任务，这样使得高优先级的任务被优先于较低优先级任务加以分配，而不管是否在针对此资源的初始优化规划中。至少一个选择步骤可首先确定此资源的初始优化规划是否包括此确定优先级的可执行任务，和如果存在的话选择所述任务，或者如果此资源的初始优化规划不包含这样的任务，确定是否存在有尚未被规划的该优先级的任务，如果存在即选择这样一任务。

在此说明书中，术语“被规划的任务”是指当前临时地被分配到一资源的任务，如果该规划被修正该任务最终可能被分配到另一资源。如已讨论过的，先有技术系统预先将任务分配到特定资源，而排除即使最先成为可行的和具有另外灵活分配的任务的任何其他适合的资源。在本发明的系统中，虽然最初一高优先级任务可被规划为针对一指定的技术人员加以规划，而另一具有适当位置并能熟练完成此任务的技术人员在他首先要求时也可能被分配该任务，如果这样做能对规划产生利益。对第二技术人员的原始规划则被搁置，和在该规划中各任务将成为未被规划的直至一适合此任务的技术人员请求它。这可能是第一技术人员，如果他的技术能力和地理位置合适和如果他在此任务被分配到其他地方之前请求的话。也可能是第二技术人员(亦即，该任务最先规划的那一个)，如果在他完成第一任务时仍有时间进行它的被原先规划的任务的话。但是，一般此任务会分配给一第三技术人员，他自己的规划也将被按次序中断。

为避免对难以控制的规划传播的破坏，可将系统配置为将其变化限制到一被选择的资源和任务组。这些可以是那些具有相关特性，例如同样的当前地理位置，和/或完成当前任务的估算时间，和/或技巧，和/或他们当前被规划来执行的任务型式。被限制到以这些资源表述的“方案空间”的(资源、任务、时间、地点等的抽象多维矩阵)范围的对规划的修正保证对规划的任务任何改变均将相当缓慢地通过此方案空间传播，因此将不大可能导致规划进程的整个破坏。特别是，如果某些被标识为难以分配的任务不允许被中断，这将保证在此方案空间内存在有“稳定性安全岛”，它将趋向于降低这种中断通过方案空间传播的速率。

在生成初始编码表之后，对多个由规划修正处理所考虑的任务可能增加另外一些任务，由此使系统能以短于初始规划的生成的时间量程来分配紧急任务。

附图说明

现在参照所列附图仅作为举例地说明本发明一实施例，所列附图为：

图1表示一被配置为按照本发明运行的包括有计算机X的系统的总体配置；

图2表示图1的计算机X的组成部分；

图3用于生成一临时地将资源分配给任务的初始优化规划的初始规划生成系统的功能方框图。二基本组成为一决定性“预先任务规划器”级30和一随机“优化子系统”级31；

图4为应用由图3的规划生成系统所生成的初始优化规划随着资源成为可用时将资源实时分配到任务的规划修正子系统40的功能方框图；

图5为说明图3的预先任务规划器30的操作的流程图；

图6、7、8、9针对5种不同情况说明随着分配任务成本的时间的变化；

图10为说明图3的优化子系统的操作的流程图；

图11说明优化子系统31所用的Simulated Annealing处理；

图12、13、14为说明通过图4的分配系统根据图3系统所生成的初始优化规划和对该规划的实时修正将任务分配到技术人员的方法的流程图；和

图15～17说明本发明的系统的三种操作模式。

具体实施方式

参看图1，表示一由故障监视系统FMC所监视的以方框N所表述的远程通信系统。此故障监视系统FMC检测网络中需加注意的故障，还接收由例如作规划规划维护的操作员的输入，以生成要由现场技术人员组T1、T2、T3所执行的任务请求J1、J2、J3、J4、J5、J6、J7。这些任务请求被输入到一包括用于分配资源到任务的计算机X的形式的设备的资源分配系统，在需要时它可通过远程通信网络N与手持终端H1、H2、H3通信。如图1中所示，终端H1，当前正通过连接C与计算机X通信。每一手持终端可以是英国HuskyComputers Ltd.of Coventry生产的Husky型FS/2，但也可采用其他合适的设备。

在现实条件下将有许多技术人员(通常有数百个)和任务。一般一百个技术人员的劳动力一天中可进行6百个任务。因此通常在一天将有接近600个任务加到系统，和600个任务在它们被完成时脱离。所有新任务和完成的部分将要求对当天的程序的改变。这样，虽然各个技术人员的规划一天变化很少次，但在一8小时的工作日平均一分钟就要二次改变整个的规划。自然这一数字掩盖有相当大的波动，例如当夜间发生的故障被发现和报告时在此工作日的开始会发生大量的输入。

为了说明的目的，本示例仅有三个分别提供有终端H1、H2、H3的技术人员T1、T2、T3。现在这些技术人员正从事于任务J1、J2、J3并有4个另外在等待的任务J4、J5、J6、J7。技术人员T1、T2、T3可利用他们的终端H1、H2、H3报告一任务的完成和由计算机X接收执行下一任务的指令。

为说明目的，此三个技术人员T1、T2、T3可被看作为在远程通信网络N上执行任务的现场人力的部分。但是，欲加监视的系统不一定是远程通信系统，并可能与终端通过其与计算机X通信的远程通信系统相距十分远。

计算机X的基本组成如图2中所示。这些包括键盘21，中央处理单元(CPU)22，直观显示单元(VDU)23，存储器24和输入/输出端口25。用于控制计算机X的数据和程序存放在存储器24中。输入/输出端口25将计算机连接到提供计算机X与手持终端H1、H2、H3间的通信链路的远程通信系统。计算机X还能检查来自与远程通信网络相关联的故障监视系统的报警。

计算机X设置有用于分配技术人员到任务的主程序。此主程序被分成为一组例行程序。稍后将详细讨论程序的和个别例行程序的总体结构，和程序将技术人员分配到任务的方法。

在图1中，技术人员T1已完成任务J1和借助其终端H1和通信链路C与计算机X联系其下一个任务的指令。问题是要确定技术人员T1应被指示下一次执行的任务J4、J5、J6、J7中哪一个。由计算机X的主程序所采用的方法将考虑到：

此技术人员是否能执行各个任务；

此技术人员行进到各任务地点所需的时间；

此技术人员执行各任务所需的时间；

各任务的相关重要性，例如由受影响客户的数量和如果在一指定时间期内或者根本不执行此任务将会引起的任务经济损失所决定的；和

另外的技术人员T2、T3的可能性。

这些另外的技术人员的可能性取决于他们各自将成为可能时的时间，这又取决于他们的当前任务的长度，和取决于技术人员开始进行这些任务的时间，以及由他们的目前地点到达任务地点所需的行进时间。

接受任务的时间受制于某些不定因素的影响，因为许多情况下任务涉及到对所报告问题的研究和校正。在问题被研究之前为加以校正所需时间只能以相当大的误差量进行估算。还存在有其他可变因素，例如使得难以作精确测量的各任务的局部环境。计算机X程序所用的方法开始对各技术人员计算一临时的规划，而如果一技术人员报告任务的早期完成，或者未能在估定的时间报告，或者如果在已生成临时的规划之后要求新的任务，则能改变这些规划。

此方法针对各任务计算与时间相关的“成本函数”。这时因未满足协商的时间而造成的损失加以考虑。如果因时间不满足而可对客户补偿是可支付的则此损失可以是一真实货币成本，或“虚拟”成本，例如危及公司的信誉。此损失具有与时间相关的特性。在最简单的情况下如果满足协商时间，此函数为零，否则一固定值。在较复杂的情况下，例如补偿可按照延迟程度偿付时，它可以是某些较复杂的时间相关函数。规划一任务早于其目标时间具有偶然值(由降低失败概率所导致的任务的计划成本的降低)，亦即，如果技术人员在途中延迟或在任务占用的时间大于预期的，他仍可在目标时间之前完成任务，所以如果此任务未被规划得非常接近其目标时间，较低成本将是适宜的。

为在任务与技术人员之间进行每一种可能的分配，估算一“技术人员/任务成本”，分配一给定任务到一给定技术人员的成本。这考虑到任务失败的成本(不管谁担任都相同)和任务失败的概率(这在技术人员之间互不相同)。这种概率取决于此技术人员当前任务的预定结束时间，到达新任务所需行程时间量，新任务的估算期限，和新任务必须完成的目标时间。这些因素确定一范围，它是一其他因素可跨越而不致超过目标时间的时间量，或者如果相反，则为目标时间将错过的时间量。

其他因素，例如一指定技术人员为执行此任务所要求的非生产性时间量(例如耗费在行程中的时间，或者如果作出“没有先前”指定时间而在该地点等待访问的时间-即，在特定时间之后要发生的一个指定)也可被加以考虑。应当指出这些成本是估算的。在某些环境中，此成本取决于任务实际进行的时间可能是变化的。但在许多情况中，分配任务的实际成本实践中仅能取二个值之一，成功的值(负成本)，或失败成本，但在分配时刻并不知道它将取这些值的哪一个，因为无法预计的情况可能阻碍技术人员准时到达，或者如果他的确到达的话，可能防碍他准时执行任务。还有另外的因素，例如技术人员执行任务的能力(考虑到每一个别人员可行的技能、设备和允许访问)，这也必须被加以考虑。对于这些因素，任务失败的概率只能取值零(如果技术人员相应地称职的话，等等)或值1(如果他不是如此称职)。对工作类型的偏爱，例如因为一特定技术人员希望取得一特定技巧中的经验，也可由中间值来表示。

这些不同的因素必须规纳到一共同测量单位。通常，所有因素均可按行程时间的等值单位测量。容许一任务失败的成本可作为一等同于一技术人员合理耗时以防止该失败发生的非生产性行程时间量加以计算。另外，可应用相当的经济值。例如，如果能以一指定的比例因误约对用户进行补偿，则可估算非生产时间成本以使得能准备用来避免偿还对该补偿的时间以相等的值来估算。

此方法确定使整体“技术人员/任务成本”最小时的技术人员和任务的组合。还必须考虑不分配任务的成本，而这一点由计入一不存在的或“伪”技术人员来达到。在其他条件相同时，如果任务多于用于执行它们的资源，则将优先级最低的任务规划给此伪技术人员。例如技术人员T1现在可规划给下次执行任务J5。技术人员T2执行任务J7和技术人员T3执行任务J6。如果在他已被规划执行的任务的预计完成时间之后它的规划中剩余有足够时间，则可将任务J4规划给这些技术人员之一的另一个任务，或者将其规划给伪技术人员。在技术人员T1做出指令报告时，计算机X估算当前的规划和分配任务给技术人员T1，通过通信链接C对他指示。正常情况，所分配任务将为被规划的任务(在此情况中为J5)，但是如果一优先级高于任务J5的一新任务(未表示)被要求时，或者如果技术人员T1报告任务T1非预料地较早地完成或未能在预定时间完成一任务，则此技术人员可被分配一不同的任务，可能是任务J4、J6和J7中之一，以保证最高优先级的任务仍然准时进行。在此阶段技术人员T2和T3未被给予任何指令因为他们尚未完成他们的当前任务。对技术人员T2和T3规划任务J6和J7是临时的并可加以改变，特别是如果这些任务之一被分配到技术人员T1，或者如果临时引入一高优先级任务的话。

已知有用于分配任务到资源的各种成本分析算法，如H W Kuhn的“分配问题Hungarian算法”(Naval Research Logistics Quarterly，vol2，pages 83-97，1955)中所述的所谓的“Hungarion方法”，此法得到M BWright“加速Hungarian算法”(Computer Operations Research，vol.17，Nol，pages 95-96，1990)的进一步发展。但这些算法在现实条件下不易应用，特别对于内部相关任务。而且这些算法不能预先规划多于一个任务，而优化方案可能要求预见多于相邻的下一任务。

用于控制计算机X的程序具有二主要单元。首先有一如图3中总体表明的脱机环游(off-line tour)结构程序系统，和其次有一在图4中总体表明的联机实时规划修正系统。此二系统独立运行，但脱机系统的输出被用作为联机(实时)系统的操作的起始点。各系统通常为一由适当程序控制的计算机。一般，二系统将同时运行，实时系统40控制任务与当前的技术人员分配，而规划生成系统30、3 1为实时系统40的下一运行准备数据。下面详细说明各系统。

图3表示为生成初始优化规划的脱机系统的总体配置。这一系统利用稳定数据操作，为了准备在随后情况发展时实时系统能用作为其自身功能作用的基础的初始规划。此初始优化规划可利用一严密的但较慢的处理进行准备，因为它无需对其数据中的变化反应。例如，此初始优化规划可在夜间准备，准备用于工作日的启始。

图3中表明的为生成初始规划的系统具有二中央单元，即一决定性的(基于规则的)预先任务规划器30，和优化子系统31。预先任务规划器30分别由输入33和34取关于欲加分配资源和它们将被分配到的任务的数据。这种数据在被输入到预先任务规划器30之前在各自的输入33、34中经过某种预处理。此预先任务规划器30具有可行的技术人员的细节(输入33)和要被规划的这些任务的细节(输入34)。还需要包含参数值的配置文件。

此预先任务规划器的功能是通过规划尽可能多的被给予满足由规则存储器35给出的约束的任务在每一个技术人员计划中建立固定点。这将导致各技术人员的任务的“环游”。这些环游多半为局部环游，亦即，具有某种闲置时间的环游，因为由预先任务规划器30所规划的任务只是全部可行任务的子集。另外，此预先任务规划器30还在各技术人员的环游中布置“下一可用”时间(通常为技术人员预定应上班的时间)中止、被规划的缺席、和“工作日结束”事件(技术人员被规划应下班的时间)。

完成后，由预先任务规划器生成的结果被传送到优化子系统31。此优化子系统31接收来自预先任务规划器30的局部规划和分别由输入33和34来的关于欲加分配的资源和尚未被预先任务规划器30分配的任务的数据，和生成用于传送到存储器32的初始优化规划。预先任务规划器30和优化子系统31两者均遵循一定的规则，如下面将说明的。此规则可由一操作系统的人员通过各自的输入35和36选择或修改，操作系统的人员还控制到预处理器的输入33和34，以更新技术人员和任务的细节。

如以下将说明的，优化子系统31通过一开始围绕和在由预先任务规划器建立的固定事件(包括难以规划的任务)之间布置另外的任务来生成临时的规划，然后利用随机处理在不同技术人员之间重新规划这些另外的任务直至实现一理想的规划。

此规划生成系统的操作可通过周期地暂停优化级31的操作和运行后优化级39来加强。后优化级利用某种基于规则的标准来估算迄至目前作成的规划，标明那些标识哪些表现为接近优化的部分，将这些加到由预规划级30所生的固定的局部规划，和然后重新再运行优化子系统31。这指引优化子系统31集中于改善那些被后优化器39所标识为最不理想的规划的部分。这种步骤可重复数次。

由规划生成系统30、31所最后生成的临时规划然后被用来编程图4中示意说明的调节器40，它被编程来按照此临时规划分配任务到技术人员，但如果与临时规划中所预定的不同的实时环境在需要时，能脱离此临时规划。

图4以方框图形式表示此实时调节器40的基本特点。规划状态寄存器42、技术人员状态寄存器43和工作寄存器池44各自提供输入给、并因而可被其更新的一分配处理器47。寄存器42、43、44分别由规划存储器32和预处理器33、34接收它们的初始数据。参数输入41使操作员能设定系统所用的各种加权和其他值。

技术人员状态寄存器43和工作寄存器池44也可由其他外部源来更新，如技术人员接口T1等，和各自的网络接口45、46。

分配处理器47利用寄存器中的当前状态信息为一联机请求指示的技术人员作出发配。所得分配结果被传送到指令生成单元48，后者生成有关此新分配任务和任何相关活动的指示，供传送到技术人员T。

现参照图5-9(预先任务规划器)、图10和11(优化子系统)和图12-14(实时调节器)详细说明由预先任务规划器30、优化子系统31和实时调节器40所进行的处理。

图5中以流程图形式说明预先任务规划器30所进行的规划处理。在分配任务到技术人员之前预处理器34对数据作某些预处理。这涉及规划每一任务可能的最早和最迟的开始。当试图把任务加到环游时利用这种信息。资源预处理器33在环游中规定技术人员的下一可用性、休息、缺席、和“工作日结束”事件。

技术人员的下一可用性不仅包括例如程序在夜间运行和技术人员尚未开始白天的工作时的情况，而且还包括技术人员已在工作和要求估算他将结束他当前活动的时间的情况(如完成他正在进行的所允许缺席或从该缺席返回的任务)。在后一情况下，预先任务规划器30将利用关于当前活动的预期期限信息，加上可能涉及的行程时间的估算来计算技术人员下次可行的时间。在白天开始的情况下，将认为所有技术人员均在他们被规划上班时间开始工作。

资源数据包括为规划休息所需的细节，例如为进餐。这些休息通常为规定期间，但它们的开始(和因而结束)时间可在一指定窗内灵活变动以便适应工作需要，而它们的地点不作预先安排。对各技术人员存储的细节有休息可能开始最早时间，可能开始的最迟时间，以及其持续时间。一开始预先任务规划器30将各休息布置在其最早可能开始时间。

资源数据还包括为规划脱离岗位所需的细节。这些可以是为进行其他非规划所管理的工作，例如培训，班组会议等，以及如医疗预约等的允许的非工作缺席。这些缺席通常具有固定的开始和结束时间，和也可能具有指定的开始和结束地点(如果缺席涉及旅行这些地点就可能不同，例如带设备去维修，或搜集供应设备)。为各技术人员存储任何这样规划的缺席的时间和地点的细节。应指出，因为缺席可能与一地点有关，所以在规划中必须考虑到其间来往的旅行。

此预先任务规划器还被提供各技术人员的一天数据结束的细节(包括任何被规划的超时工作)。此预处理器将设立工作日结束或“回家”时刻以便技术人员的工作日在正确时间结束。现在即生成了各技术人员的规划中的基本固定点。

在任一时刻总的可用于分配的任务中均将会有一小部分比大部分的任务更难以规划和在环游内或之间移动。一般这些任务将比其他的具有更大的局限性。预先任务规划器规划这些任务以便能具有对随后的规划步骤可行的最大限度的灵活性。由于规划器规划的任务将不会作为由优化子系统执行的搜索处理的部分被转移到另一技术人员。

输入33将各技术人员能执行的细节传送给任务的预先任务规划器30。

任务预处理器34选择要由预先任务规划器30规划的任务的子集(亦即被认为是难以规划的任务的清单)，并将这些任务传送到预先任务规划器30。这些包括有：

a、要求单个地点不只一个人员的任务；

b、要求在不同地点的多于一个人员的任务；

c、必须以预定顺序分配到同一技术人员的所有任务；

d、具有大于一预定值的时间期限的任务；和

e、用户要求分配给一特定技术人员的任务。如果用户决定它们不应被随后的运行转移到另外的技术人员的话。这一类型可包括已在规划器的前面运行中被规划的任务例如，如果任务要求专用设备，这就可能已经被发送到该技术人员。

任何未选择进行作预处理的任务均直接传送到优化子系统31。

由预先任务规划器30进行的决定性处理如图5中所示。被选择任务首先被按优先级次序(步骤51)然后按该次序进行规划。此优先级顺序可由用户利用规则输入35选取。典型的分类次序将是：

1、任务的最早启动时间(最早的第一，那些未被规划起动时间或者最早时间已经过去的则被给予当前时间)；

2、重要性标记(最高的第一)，这可以按照这样的因素确定，例如受影响用户的数量，任务是否有安全性要求，任务经济损失等；

3、所需技术人员数量(最高的第一)；

4、目标到达时间(最早的第一)，亦即任务必须被开始以符合约定或服务保证的时间。这在如果承诺要在给定时间完成任务的话就可考虑被估算的任务持续期间(亦即到达时间＝完成时间-任务持续期间)；

5、持续期间(最长的第一)；

6、能执行此任务的技术人员数(最小数量的第一)。

这样，在任一时间均将优先级给予能被立即进行的任务，和在这一类别之内给予带最重要的标记的任务。

对每一要加以规划的任务，将能执行此任务的技术人员的清单存储进一优先级次序(步骤52)。此优先级次序考虑的因素如下：

a、此技术人员是否具有各任务所需的技巧；

b、此技术员是否具有为得到访问所需的安全许可；

c、此任务是否是技术人员所喜好的工作区；

d、成功/失败(一个任务如果在当前一技术人员的环游中的所有其他任务之后被分配给此技术人员作为其环游中的下一任务时是否仍能符合其基本承诺目标的量度。成功是符合其基本承诺的任务，失败是不符的任务)；

e、成功范围(一预期到达时间减去目标到达时间(对需要在一预定截止日期前的响应的约定)或估算的完成时间减去目标完成时间(对其他任务)的量度)。使这一范围最小将保证尚待分配的较低优先级任务不会因为较高优先级任务较早地执行而被排除在外；

f、技术人员所具有的技巧的数量(最低的第一，为保证能力最强的技术人员不会被分配到较低能力的技术人员能完成的任务)；

g、行程时间(由技术人员到达此任务中所需要的时间。如果此技术人员在其环游中已有任务或活动则将该行程由最近的位置到此任务。如果此任务是此天的第一个则行程将由此技术人员的起始地点测量)。

然后预先任务规划器30将致力于将任务规划到技术人员。首先，它试着依次将第一个任务加到各技术人员的部分环游的末尾(步骤53)做出以第一个开始的排次序的技术人员清单(步骤54)。如果此位置有效(步骤55)则此任务即被规划到该技术人员(56)。在此技术人员的环游中的布置考虑到在地点之间行进所需的时间。这样，如果一技术人员的现有局部环游在时间T结束，即在时刻T+t试图分配下一任务，其中“t”为二任务之间的行程时间。t的值对技术人员和任务的各个组合将是不同的。

如果此任务不能被加到此第一技术人员的环游的末尾，就对其他技术人员重复此处理(步骤57)。如果此任务不能被加到任一技术人员的环游的末尾则依次对每一技术人员试试倒数第二的位置(即已在此规划中最后位置的紧前面的)(步骤58)。再者，如果找到有效位置，则规划此任务。继续这种处理直至此任务被规划(步骤56)或者直至各技术人员的环游中每一个位置被试验过，和未发现任何有效位置。

如果这后一情况发生(步骤59)，预先任务规划器折回(步骤510)，通过试图重新规划被加到此规划的最后一任务，通过将其由其当前位置删除并利用与前面同样的规则由该点开始继续搜索直至发现另一有效位置。然后在需要时利用折回处理继续此搜索，直至此任务被规划为止(步骤56)。然后重复这种处理直至所有任务被规划，或者已不可能规划下一任务(步骤512)，或者直至超过一预定的运行时间。

当不可能规划下一任务时，从预先任务规划器30的输出即为直到规划大部分任务的点被生成的环游。应指出，这一环游不一定是已生成的最后的一个，因为折回可能已取消分配多于它所允许被分配的环游。

如果运行时受到限制，此规划器可被配置为仅作一单次规划各任务的努力，对该任务采用最优选的技术人员，如图5中点线(513)所表明的。

在要求多于一个人员的任务的情况中(它被作为为作这种处理的一组相连的任务对待)，进行任务的规划要使它们的开始时间对齐。在某些情况中这可能导致一技术人员具有闲置时间。

预先任务规划器利用作为在由各技术人员的个别超时极限确定的极限范围内适宜的额外时间。这些极限在输入33处输入给此预先任务规划器并包括有被规划的超时，计划的灵活时间和在工作时间中允许的其他变异。如果一任务可在一个别的允许超时之内完成，则它可由此预先任务规划器加以规划。但如果一任务超过个别的超时极限，则仅在如果此任务能被分割而能在超时的末尾之前完成的此任务的部分能在大于一预定的最小值时被加以规划。在这些环境中，任务的第一部分被规划成在被规划的工作日的末尾完成。

如果一将造成未能规划的超时的任务被规划，已被预处理布置的各技术人员的工作日标记的末尾则被移动。针对工作日标记的末尾的新位置将是技术人员完成包括有未规划的超时的任务的时间和此技术人员下班的时间中的后者。

有可能缺席会涉及行进中的技术人员(例如去往和来自一班组会议)。在确定一任务的技术人员的预期到达时间和他对一任务的预期完成时考虑这样种行程。

上述预先任务规划器30仅用于规划最难以安置的任务。如果预规划功能将用来规划整个工作程序，所需的运行时间将使得规划在它被产生的时间之前不能应用，因为在此运行时间之内对系统已有新的输入。当方案因实时环境的结果很可能要加修正时花费过量的计算机处理时间来生成完美的方案将不是很有效的。对于易于规划的任务，可能有许多可接收的虽然是不优化的方案，理想的是在有限的时间内得到接近优化的方案，而不是在一非常长的时间内生成完美的方案。在针对多维问题(例如这里指定的)生成接近优化的方案的技术中已知有多种随机技术。在Brind，Muller & Prosser的论文“用于资源管理的随机技术”(BT Technology Journal，vol.13，No.1，January 1995)讨论了其中的数个。特别是，此文说明了称为“Hill Climbing”、“SimulatedAnnealing”、“Tabu Search”和“Genetic Algorithms”的技术。

在Hill Climbing中，选择一针对问题的随机方案，然后估算与此原始方案在很多小的方面不同的“邻近”方案，和选择具有优化值的邻近方案。这种处理需要继续许多次。采用Hill Climbing方案的问题是此处理可能“被陷在”方案空间的局部优化中。

Simulated Annealing以类似Hill Climbing的方式运行，不同处在于它还允许对较不理想的方案移动。执行这一点的能力被配置为随着处理前进而降弱，从而使处理避开局部优化，但不大可能回到它。

Tabu Search处理是将随机选择的起始点的值与来自此起始点的相邻的数个可能方案相比较。然后选择具有优化值的点(可能是此起始点)，利用这一优化点作为新的起始点重复此处理。此配置是使得已被拒绝的方案在随后的周期中不再考虑。因为局部方案空间成为搜索通过的，系统必定更远地寻找可能的方案直到最后求得一较理想的方案。因而此处理最终避开方案空间中的任何局部最小值。

Genetic Algorithms试图组合目前所发现的方案、并试图标识一个胜过任一个它的个别“父”方案的方案。

也可以采用系统化技术。它们探查任务的每一种可能的置换(虽然多组置换可被集体地删除)，所以将肯定找到优化的方案。但在有限时间内随机技术总将能在短得多的时间内找到接近优化的方案。

如所引用的论文中所讨论，选择哪一种技术最适合一特定环境取决于问题的性质。对于在欠资源化和过资源化问题上的运行速度和健全性，在本发明的此实施例中最好采用Simulated Annealing技术，但应明白其他可行的优化技术也不排除在权利要求的范围外。

现在说明本实施例的优化子系统31。如图3中所示，此优化子系统31具有三个输入。第一，一个用于由决定性预先任务规划器30所产生的、对技术人员可行的一组环游的输入。在一替代配置中，此决定性预先任务规划器30可被省略而环游仅包括有被预处理器33所设定的固定点。这一输入也可被用于一递归配置中的后优化器39所生成的环游。第二，一个针对可行的技术人员37的细节的输入。第三，一个针对未规划的任务38的细节的输入(亦即，非由预处理器34选择而由预处理器30规划的那些)。

开始工作之前，优化子系统31进行数据的某些预处理。这涉及到计算出一任务可能开始的最早和最迟时间。此信息在试图加到环游时被优化子系统应用。另外，此预处理还固定了各环游中的活动、休息、缺席和工作日的结束。此优化子系统需要各种参数值，由一输入36编程。

优化子系统31的功能是力技术人员产生一组使目标成本函数最小的对环游。最终的环游通过利用单个修正数学操作对当前的规划每次进行一改变来产生。优化子系统将所产生的环游的细节传送到存储器32，从这里它们可被实时修正系统40检索。

应指出，由预先任务规划器30所规划的任务中任何一个也不能被优化子系统31转移到另一技术人员或到未规划状态(伪技术人员)，但优化子系统31能在它们的时间窗内移动这些任务和将任务插在它们前面、中间和后面。可能由优化子系统产生的最终环游具有按修改的顺序被预先任务规划器初始布置的任务(例如，如果预先任务规划器30排列二个任务以便任务A后跟任务B，只要仍然符合对二任务的各种不同约束和保持它们的次序。有可能优化子系统31会在它们之间插入另外的任务，这将导致其中一个任务或两者都重新定时。

现在解释“Simulated Annealing”方法的细节。关于此方法有4个要素：

目标函数；

修正操作符；

冷却规范(cooling regime)；和

停止规则。

现在说明此4个要素的每一个，以目标函数作开始。这提供对所访问问题的二个方案中哪一个较好的目标评估，和认为转移是改善此方案还是使其恶化用。用此函数对系统中的所有任务求总和，而不管这些任务有未被规划，和不管是预先任务规划器还是模拟熟练器将任务布置在环游中。此目标函数可认为是由4个成分组成的。这些成分是：

行程代价；

超时代价；

技能偏离代价；

分配的成本，亦即，失败的风险和成本的量度，或一意外值。

这4个成分适用于除低优先级“填满”任务外的所有任务，这些个填满任务被作为特殊情况对待和仅接收与涉及的行程量成比例的成本。

行程代价由将每单位时间的成本与估算的行程时间一起相乘来确定。这样，与分配中相关的估算行程时间越长成本越高。

超时代价以同样方式作用：每一分钟超时的成本被乘以使用的超时量。同样，所用的超时越多分配的成本就越高。

技能偏离代价在如果针对此任务的技术人员所需的技能并非用户希望的偏离规划走向技能时即将附加的成本加到目标函数来(一般为一稀有技能，使得如果可能的话在其中称职的技术人员最好不被分配到无需该技术的任务)。

将此三个成本汇集到一齐具有能保证模拟熟练器努力使行程、不反应所需的技能偏离的分配、和超时最小化的效果。

分配的成本是一任务的型式、任务的重要性成本、和此任务是否被布置以使它满足确定的截止日期的函数。通常这采取尽早完成任务来降低分配成本的方式。这在对于具有作为预期到达时间与目标到达时间之间的差的目标到达时间的任务，和对于具有作为估算完成时间与目标完成时间之间的差的目标完成时间的任务加以计算。

这些项被修正来给予此函数如下的二个另外的重要特性。首先，定义一特性“P”作为满足目标的和目标自身的预期时间与此预期时间可能超过此目标的最大时间之间的差的比例。例如一具有要在由10.30am到1pm实现的约定的任务(其中预定到达时间为11.30am)的p值为11.30am减1pm(-90分钟)被10.30am减1pm(即-150分钟)除等于-90/-150＝0.6，执行一项必须在5pm前完成的任务但也希望能在正午12点，实际能在2pm前完成。在二种情况下，目标符合所用的可用窗的40％(60％剩余)，而仅有的差别是分配的成本，这仅取决于分配各任务的重要性成本。

其次，延迟一被置于接近其将失败的点的任务的成本应高于提前一同样的时间量，是一距其将失败的时间仍很长的类似任务。例如，具有带承诺时间为5pm的两个任务，其中一个预期要在4.50pm、另一个在正午12.00完成，则造成第一个提前5分钟而使第二个延迟5分钟的移动降低总的规划成本。如果在此延迟能有非常大的收益的情况下这样延迟一已接近失败的任务的移动将只能改善目标函数。

在它们各自窗的开始分配不同的任务的成本之间的仅有差别是由于在任务的重要性记分中可能存在的任何差异。这就是说明重要性记分所表述的二任务的相对重要性不被改变。

为在目标函数中重现此第二特征，将(1+p/2)×p项引进对所有符合它们的基本承诺目标的任务的成本中。此项是指分配的成本随着任务接近其基本目标时间时增加，首先对每分钟的延迟增加很少，但在目标临近时此速率增大。对预期时间与目标时间之间的差作出成本曲线图，即得到图6-9中所示举例中那样的曲线，后面将加以说明。

某些任务必须在一规定的约定时间进行，例如与一用户协议的。另外的具有目标响应时间。对于不具有约定时间的任务，如果任务在一环游中被置于将不能达到其基本承诺目标(即保证的响应时间)的位置时此分配成本将进一步增加。还可能有一辅助承诺目标，超过它可付给客户以补偿。设定固定的成本损耗来保证失败的任务的数量最小化。没有这些成本时分配二同样的非约定任务的成本，一个耽误其目标一小时而另一个到达时多出二小时，将优于的各自超过15分钟完成二个任务。后者在业务领域显然具有优越性。带有固定的损失时可调整成本来使得所希望的业务方案是成本最低的。

对于在环游建立过程的末尾仍未加规划的约定，分配成本由以分配的重要性成本加权的固定成本来确定。保留不加规划的非指定任务根据在规划周期末尾假定的完成时间加上任务任务持续时间来计算成本。这种成本计算被用来保证将一任务加到一规划的成本总要低于让其保持不加规划时的成本。

分配一任务的重要性成本以下面的二参数修正的重要性记分(TPM)为依据：重要性记分乘数(1MU)和重要性记分索引(IEX)。以IMU^IEX×IMP进行计算。如果IMU和IEX两者被设定到1(或IEX＝0)则成本仅就就是任务的重要性记分。大于1的IMU和IEX值增加分配具有高重要性记分的任务的与低记分相比的差别成本。

填满任务在目标函数中用对各被规划任务采用成本零和对各未被规划任务采用成本1来计算成本。这一规则设定来保证规划一填满任务要比保持不作规划时总会较便宜，但它亦决不值得以延迟更重要的任务来使得能规划一填满任务。

目标函数应用以下参数：

ETT(Estimated Travel time估算行程时间，以分钟计：一般为针对技术人员由一任务行进到下一任务的估算时间)；

FTF(Failed Task Flag，失败任务标记：如果任务未实现其约定目标即为1，否则为0)；

FSP(Failed Secondary Commitment Penalty，失败辅助承诺损失)；

SCT(Secondary Commitment Time，辅助承诺时间：一晚于目标完成时间的时间，此时成本损失具有阶段变化)；

TSS(搜系统开始运行的时间)；

ETA(Estimated Time of Arrival，估算到达时间)；它作为技术人员将到达现场的时间计算，假定所有行程和任务持续时间均是准确的和每一个任务在前一任务结束时就立即被规划。但是，如果这种计算导致任务在所分配的时间窗开始之前发生，则ETA就作为该任务时间窗的准确起始而计算。一个任务的时间窗被定义为任务的最早开始时间(EST)与最迟地开始时间(LST)之间的时间；

TAT(Target Arrival Time：由任务预处理器34给定。对于一指定任务这将是约定时隙的末尾)；

UOT(Amount of unscheduled overtime，未规划超时量，以分计：为完成规划所需的超过技术人员的被规划的结束时间量)；

ETC(Estimated Time of Completion，估算完成时间：预期的技术人员将完成任务的时间。对于被规划任务计算为ETA加任务自身的持续时间。对于未规划任务计算为被规划的结束时加任务的持续期间。此值对技术人员是特定的，因为技术人员具有不同的工作速度，在技术人员预处理器33中加以指明)；

TCT(Target Completion Time，目标完成时间：为没有约定时间的任务所设置的字段。未能符合目标完成时间造成成本损失但未使任务失败)；

FSF(Failed Secondary Commitment Flag，失败辅助承诺标记：如果任务未达到其辅助承诺目标设定为1，否则设定为0)；

SBF(Skill Bias Penalty Flag，技能偏离损失标记：设定为技术人员对所规划任务的技能喜好的值，减1。例如如果一要求特定技能的任务被分配到一喜欢该技能3的技术人员，此SBF就被设定为2)；

BTF(Business Time Flag，业务时间标记：如果技术人员的预期到达时间在早于截止时间之前或在迟截止时间之后，亦即在对这样一要执行的任务的时间窗之外，设定为1，否则设定为0。预期到达时间被作为技术人员到达现场的时间加以确定，假定所有行进和任务持续期间都精确和在前一任务一结束任务就立即被分配任务，或者，如果在一使得技术人员在任务时间窗的开始到达时将任务移出其时间窗的话)；

ETP(Estimated Travel Penalty，估算行进损失：这一参数取大于或等于零的值，被用于计算出针对与各任务相关的行进的目标函数的作用。此行进作用被作为ETP乘以ETT来决定。此参数的缺省值为零)；

OTP(Unscheduled Overtime Penalty，未规划超时损失：这一参数取大于或等于零的值，被用于计算出各个引起未规划超时的任务分配将起的对目标函数的作用。其缺省值为零)；

UAP(Unallocated Appointment Penalty，未分配约定损失；参数取大于或等于0的值，被用于计算出未被分配的约定对目标函数的作用。缺省值仍为零)；

FTP(Failed Task Penalty，失败任务损失：取大于或等于零的值，表示在计算出非约定任务的目标函数的作用中所用的量。缺省值为零)；

SBP(Skill Bias Penalty，技能偏离损失：取大于或等于零的值，表示针对不反映所希望技能偏离的各任务分配的，亦即如果技能偏离标志(SBF)被置定为1时要加到目标函数的量。此参数的缺省值为零)；

ATC(Arrival Type Constant，到达型式常数；一大于零的整数，表示分配一失败“到达型”任务的成本要加倍所通过的时间周期，亦即其承诺为在给定时间到达现场的那个，与其承诺为要完成此任务的那个相区分的，成倍的)；

ITP(Infill Task Travel Penalty，填满任务行程损失：取大于或等于零的值，表示将被用于针与各个被分配的填满任务相关的行程计算出对目标函数的作用的量。此行程作用被计算为ITP乘以ETT(估算行程时间)。此参数缺省值为零)；

MIT(Maximum Infill Travel，最大填满行程：取大于或等于零的值，表示分配一填满任务的成本严格等于不分配它的成本对所超越的行程量。此值越大，一技术人员可允许行进到这样一填满任务就越远)；和

BTP(Business Time Penalty，事务时间代价；取大于或等于零的值，表示将被用来针对在估算的技术人员到达现场的时间不在指定的期间内时的非指定任务的分配计算出对目标函数的作用的量。招致这种损失的分配被标识为任何具有事务时间标志(BTF)被设定为1的分配。参数缺省值为零)。

应指出，所有时间均为分，时钟时间被设定为零＝午夜，例如，工作日1正午12点被表示为720，4.40pm为1000，工作日2的9.20am为2000，等。正常工作的之外的时间不被排除。为举例目的，这种情况下工作日被定义为8am至5pm(星期一至星期六)。一个具有TAT(目标到达时间)为星期三5pm和ETA(估算到达时间)为星期四8.01am的任务导致迟到ETA-TAT＝+901分钟后，而不是+1分钟。(正值表示迟到)

假定一具有5pm后的ETA(估算到达时间)的任务，在非工作小时被排除时，要在第二个工作日的8am完成，在本系统中不作这样的假定。例如一具有ETA(估算到达时间)为星期六(工作日)5.17pm和TAT(目标到达时间)为星期一8.12的任务，排除停工时间，将导致ETA-TAT＝-12(亦即仅仅及时完成)而不是正确值-2335。(这些值由于它们在目标时间之前到达而为负)

要加以最小化的目标函数由以下10个等式确定，取决于所涉及任务的型式：

等式1：用于被分配的指定任务，对目标函数的作用是：

(1+P/2)×P×(IMU^IEX×IMP)+(ETP×ETT)+(OTP×UOT)+(SBP×SBF)

其中，如果当前时间等于或已通过此时隙打开时间：

P＝(ETA-TAT)/(TAT-TSS)[如TAT＝TAS则P＝0]

或者，如果时隙尚未打开：

P＝min{1，(ETA-TAT)/约定时隙长(分)}

(P取由逗号分开的两值中的较小值)。

等式2：用于被分配的到达型任务，此时ETA减去TAT小于或等于零，对目标函数的作用为：

(1+p/2)×P×(IMU^IEX×IMP)+(ETP×ETT)+(OTP×UOT)+(SBP×SBF)

式中，P＝(ETA＝TAT)/(TAT-TSS)[如TAT＝TSS则P＝0]。

等式3：用于被分配的到达型任务，此时ETA-TAT大于零，对目标函数的作用为：

(P+FTP)×(IMU^IEX×IMP)+(ETP×ETT)+(OTP×UOT)+(SBP×SBF)，

式中，P＝(ETA-TAT)/ATC。

等式4：用于被分配的约定和到达型任务，其作用为：

(IMU^IEX×(IMP)×UAP。

等式5：用于被分配的承诺任务，此时ETC-TCT小于或等于0，作用为：

(1+P/2)×P×(IMU^IEX×IMP)+(ETP×ETT)+(OTP×UOT)+(SBP×SBF)+(BTP×BTF)

式中，P＝(ETC-TCT)/(TCT-TSS)。

等式6：用于分配承诺任务，此时ETC-TCT大地零，但未超过辅助承诺极限，其作用是：

(P+FTP)×(IMU^IEX×IMP)+(ETP×ETT)+(OTP×UOT)+(SBP×SBF)+(BTP×BTF)

式中，P＝(ETC-TCT)/(SCT-TCT)。

等式7：用于被分配的承诺任务，此时ETC-TCT大于零而辅助承诺极限被超过，其作用为：

(P+FSP+FTP)×(IMU^IEX×IMP)+(ETP×ETT)+(OTP×UOT)+(SBP×SBF)+(BTP×BTF)

式中，P＝(ETC-TCT)/(SCT-TCT)。

等式8：用于未分配的承诺任务，作用为：

{(ETC-TCT)/(SCT-TCT)+(FTP×FTF)+(FSP×FSF)}×(IMU^IEX×IMP)。

等式9：用于被分配的填满任务，作用是：

ETT×ITP。

等式10：用于未分配的填满任务，作用是：

MIT×ITP。

应指出，没有规划任何预料要失败的约定(亦即，技术人员在约定时隙结束之后到达现场)。另外，如果对在技术人员有可能在约定时隙打开之前到达的时间作约定规划，则认为此技术人员将代之以在时隙实际打开的时刻到达。

图6-9中说明多种不同型式的任务和情况的分配成本。它们表示分配任务的成本是如何随着任务变化的到达时间或完成时间的改变而变化。在所有情况中IEX和IMU均被设定为1。

图6说明一被指定到一特定的“时隙”的任务的情形。这一任务被指定为8am与10.30am(午夜后的480至630分钟)间的时间，因而仅只有这一范围才是到达的有效时间。严格在8am到达将产生负0.5倍的此任务的重要性记分的成本，而在准确地在10.30am到达则将得到零记分。如果任务保持未被分配并因而不被执行，则导致一损失记分UAP×IMP。UAP被设定为一正值，所以分配一约定的成本总小于不分配它的成本。

图7表示与图6类似的情况，不同的是时隙已打开和当前时间为9.40am(午夜后580分钟)，所以在时隙关闭之前仅剩余50分钟。曲线形状相同，但时间轴的值已被压缩。

图8表示一无约定时间但带有在一指定时间(5.30pm：1050分钟)前完成的承诺的任务。参数FTP被设定为1导致在超过承诺目标外成本中的阶跃改变，此阶跃的大小等于重要性记分(即50)。参数FSP被设定为2，导致超过一辅助承担时间(在此情况下为损失时间，2040分钟即工作日2的10am)的二倍重要性记分(即100)的成本中的又一阶跃改变。

图9表示针对具有重要性记分900的、具有目标到达时间的任务，分配成本是如何随时间变化。此图中，目标到达时间为中午12点(720分钟)和参数FTP值为0.1。这在任务超过中午12点时造成阶跃变化90(即重要性记分900的0.1倍)。

通过采用预规划器30所生成的局部规划和随意分配另外的任务到技术人员来建立一初始规划。然后由优化子系统31修正此初始规划。图10中以流程图表明这种处理。此处理包括有要求生成随机数的4个步骤1001、1002、1005、1016。任务和技术人员各自被分配一个号。

该处理通过估算原始规划的成本开始(步骤1000)。接着利用一随机数发生器来选择一个任务。除已讨论过的预分配的任务外，各任务均具有被选择的同等概率，而不管它当前是否存在于一规划中。一旦选择了一任务，如何继续进行此处理取决于此被选择任务是否已在一环游中。

一可行的技术人员(即一个如预处理器33所确定的能执行此任务的人选)也作随机选择(应用与用来选择一任务相似的处理)。由1至N+1的范围选择数(步骤1002)，其中N是可行技术人员数，但是对应于被当前规划的所选择的任务的技术人员被排除选择之列。数N+1代表“伪”技术人员。分配任务到伪技术人员作用是为了目标函数而取消分配该任务。应指出，规划一任务到伪技术人员的机会为1/N，因此在系统中技术人员数增加时减少。如果任务未被规划，则它为排除出选择的伪技术人员。

如果此任务不针对伪技术人员(步骤1003)和不针对一指定时间(步骤1004)，就选择所选技术人员的环游中的一随机位置(仍采用随机数处理，步骤1005)和检测此位置此任务能否适应于它(1006)。为使它能将此任务配合进环游，间隙必须足够大来包括此任务，否则为了生成一间隙足够大以插入此任务它就必须能延迟所有的随后任务(1007)。

如果任务具有一约定时间(步骤1004)则检验环游中的所有可能的位置(步骤1008至1010)直至找到一有效位置(步骤1009)。各个位置的有效性由对照任务的约定时隙来确定(步骤1009)，例如，一被指定到一下午时隙的任务对环游中一在9.30am结束的位置就是无效的。如果所有位置均经过测试而没有一个有效(步骤1010)，即丢弃此任务(步骤1018)而选择一个新的(步骤1001)。如找到一有效位置就如上述针对非约定任务对之加以检验以确定此任务能否被配置到它(步骤1006和1007)。应指出，一具有约定时间的任务将不被规划到在由此约定时隙开始时间(减去一允许区间)和此约定结束时间所定义的时间窗之外的技术人员将到达的位置。如果前面任务的估算完成允许技术人员在此窗之前到达，则就认为此技术人员具有闲置时间。在确定是否能进行插入时允许行进到和离开一被插入到规划的任务。

如果插入可能(步骤1006)，就将此任务插进此技术人员的规划(步骤1012)和被估算成本的修正规划(步骤1013)。然后将此修正规划的成本与最佳的现有值进行比较(步骤1014)。任何降低目标函数或维持其不变的移动均被自动地承认(步骤1015)。这类似于先前被称作为“Hill Climbing”的处理，因为仅在一特定方向(向着优化)的移动才被认可。但在Simulated Annealing处理中，增加目标函数的值的移动也被认可，具有要作简短说明的由“冷却规范”所定义的概率P。生成0至1范围内的一随机数R(步骤1016)，而如果它小于或等于概率P(步骤1017)即认可此移动(步骤1015)。

如果移动被认可，即将所得的目标函数的值与前面得到的最佳值相比较(步骤1019)。如果它优于前面最好的，就将此方案保留作为新的“最佳值”(步骤1020)供以后的比较用。在此最后阶段，或因为任务不能被插入规划(步骤1007或1009)可能拒绝任何改变(步骤1018)。

然后利用修正规划(如果改变认可的话，步骤1015)或者早先的规划(如果拒绝改变的话，步骤1018)对其他任务重复此处理(步骤1001)。应指出，被认可的移动(步骤1015)被用作为下一循环的基础而不管它是否对“最佳值”有所改善(步骤1019/1020)。

取消分配一任务(亦即将其规划到伪技术人员)总会增加目标函数，但这样的取消分配是以概率P被接受的，由此使得可能在处理的下一循环中能重新规划一替换任务给从他那取走任务的技术人员。应指出，对分配任务到伪技术人员没有任何技能、时间、或其它的结束，即这样的分配总是可行的，但总要增加目标函数。

接收使得目标函数值增加的移动的概率P由式P＝exp(-δ/温度)给定。

此“温度”是一控制增加目标函数值所做的移动的数量的概念。温度值越高将会接收越多的增加目标函数的值的移动。在搜索期间此温度值逐渐减小，从而在越后面的搜索点将接收越少的这样的移动。δ是改变后的目标函数值与变化前的值之间的差。在一给定温度时给定数量的移动之后此值降低。此降低是用一预定值乘温度产生的。所有的移动、不管其为有效还是无效、被拒绝还是被接收，均包括在此数内。

δ、温度与接收使得目标函数值变差的移动的概率之间的关系如图11中所示。此图表明冷却规范的二关键特征，首先，接收使得目标函数值恶化的移动的概率随着δ的辐值增加时减小，和其次，在温度降低时概率也降低。

模拟熟练器可被设置为在一预定时间之后或已被应用预定数量的温度之后停止。要被传送到规划管理器的规划(一组环游)是在处理停止时产生目标函数的最低值的一个(亦即作为迄至当前发现的最佳而被存储的一个，步骤1020)。

优化子系统31应用作为在由个别超过时极限的可用性所确定的极限之内适宜的超时，这些极限通过预处理器33传送到子系统31。如果一任务可在一个别的所允许的超时之内完成则它就可由优化子系统加以规划。但如果一任务越过个别的超时极限，则它只有在如果它能被分割成二个或更多子任务、和如果此任务的可在被规划的工作日结束之前完成的部分大于一预定最小值时才被加以规划。在这些环境中，任务被分割来使得此任务的第一部分被规划成在经规划的工作日的结束时完成。未分割的任务被布置以便预计它要求非规划的超时。

在一工作日过程中优化子系统31以有规律的间隔运行。在每次其运行时，处理过程可由起点开始启动来试图规划所有还未被预规划器30规划的任务。另一方面，子系统31也可通过重复应用作为一起点的在其前面运行中所生成的环游来运行。在这一模式中，优化子系统31构成其起始位置如下，对于先前的环游组中的各技术人员进行检查，看他们是否仍然可用(亦即，是否仍在由预处理器33所提供的技术人员清单上)，对那些仍然可用的技术人员，任何由预规划器30布置的任务均被写入环游中。然后检验前面的环游，按照任务被进行的顺序，和将所有能被加到当前环游的任务加到此新环游的末尾(亦即在任何被预规划器布置的任务之后)。将任何不再有效的(例如已在别处分配的)任务从环游中去除。在这样生成一初始环游后优化子系统即以已说明的方式搜寻更好的方案。

周期地暂停此处理和标识直至由一后优化器39分析的点的最佳规划。这利用一基于规则的方法来标识呈现为接近优化的个别规划，例如仅具有小量闲置时间或行程时间和不涉及要求折返的路线的规划。这样的规划被识别为固定的，和优化处理重新开始的。这保证优化处理通过限制其搜索到那些“方案空间”的区域来集中到整个规划的最可能得到改善的那些部分。

在适当的运行时间之后，产生最后一组技术人员规划。然后这被传送到实时规划调整器40。在此实时调整器利用这一规划运行中，规划生成器30、31可重新运行以便利用更新数据生成新的规划。

图12、13和13中以流程图表明实时调整器40(图4)的运行。图4以方框图形式表示实时调整器40的基本特点。规划状态寄存器42存放规划的当前状态，它们是由优化子系统31(图3)通过规划存储器32最初提供的。技术人员状态寄存器43和工作寄存器池44类似地分别存放最初由各自的预处理器33、34得到的关于技术人员和任务的数据。这三个寄存器如下面将说明的全都可以加以更新。参数输入41使得操作人员能设置各种加权和其他系统所应用的值。

技术人员状态寄存器43可由技术人员T1等本身的输入来更新，特别是以联机或脱机地记录技术人员的状态。工作寄存器池也可借助人工接口(一计算机终端)45来更新，它使操作员能在实时分配器运行期间，例如响应客户报告故障将新的任务加到工作寄存器池。也可设置连接到网络46内的故障监视器的自动输入。

寄存器42、43、44全部提供到-分配处理器47的输入，它利用这些寄存器中的当前状态信息以参照图12、13和14说明的方式在其联机请求指令时给该技术人员T产生一种分配。所得的分配被传送到指令生成单元48，它将有关此新分配任务及任何有关活动的指令传送给技术人员T。分配处理器47还传送关于技术人员的当前位置，下一预期的呼叫时间等的更新信息到技术人员状态寄存器43。分配处理器47还传送更新信息到工作寄存器池44，特别是为删除刚被分配的任务。分配处理器还传送更新信息到规划状态寄存器，特别为修正受刚才所作分配影响的任一其他技术人员的临时性规划。

对调整器40作这样的管理，即要能最早地或在最恰当的时候考虑自从规划被生成以来所发生的变化。这些变化的产生有可能是由于技术人员针对比预期早或迟的新任务提出报告，以短的通知请求缺席，对被规划任务的改变(如修改的约定)，进入系统新任务，或对规划和分配规则的改变，例如因恶劣天气或交通状况所引起的行进时间的变化。目标是要保证在当一技术人员要求一任务时，实际分配的工作是在处理此工作请求时的最适用于该技术人员的最合适的任务，而不管它是否是-原先被规划的。为有助于理解将说明的分配和优化规则，采用图12～14的一系列流程图。在图12中，参考号13指图13中的表述的流程图，它作为一在图12的流程图中所表明的处理期间被调用的子程序运行。同样，图14的处理作为图12和13的各个步骤中的子程序而进行。

下列术语在数个规则中出现，为方便起见在此给予定义。

“Inaccurate(不准确的)”：活动的规划状态(如任务、缺席、休息)，针对技术人员进行了规划但还未分配给他，和对此规划作为基础的信息已成为无效的。如果一技术人员被分配一不在此技术人员的原始规划中的任务时，或如果-原先在此技术人员的规划中的任务被分配到另一技术人员时这就可能发生。

“Pending(未定的)”：-活动的规划状态(如任务，缺席、休息)，针对-技术人员进行了规划但还未分配给他，和对此规划作为基础的信息被假定为仍然正确(亦即没有被标以“不准确的”)。

现在说明图12～14中表明的处理。这些被概括如下：

图12表示用于确定要给予-刚登记的技术人员什么指令的处理(步骤1200)。指令(1211至1215)将通常执行-任务(1213)，但也可能发出其他指令例如缺席(如参加一会议或培训会，1211)；

图13为选择-合适任务的处理；

在图12和13的处理双方，均采用确定此技术人员执行一给定任务的可行性的子程序。这一处理在图14中说明。

图12说明用于对一联机技术人员确定-任务的分配的处理。当一技术人员登记时(步骤1200)系统查阅规划来标识对此技术人员的下一个活动(1201)。如果此下一被规划的活动为“工作日的结束(EOD)”(亦即此技术人员在其他时间已没有被规划的任何另外的活动)，系统进到处理13试图找到对此技术人员的合适任务。如果在“工作日结束”活动之前存在有被规划的活动(负输出到步骤1201)，则执行—“预选缺席检查”处理(步骤1202至1207)。首先系统检查此技术人员的规划以确定是否对此技术人员规划过任何缺席(步骤1202)。如果没有这样的缺席则利用下面疳说明的处理13寻找此技术人员的下一任务。

如果存在至少一个缺席，则系统查看此下一个缺席是否是由于在当前时间之后一预定时间之内起动(步骤1203)。如果是这样则进行检查以确定所规划的此缺席的结束是否落在-必须进行休息的期间内(步骤1204)。如果不会，则指示此技术人员作缺席，例如参加一会议(步骤1211)，并向回报告要求进一步的指令。通过记录此缺席期间的开始来更新数据库(步骤1216)，将此技术人员的下一预期的接触时间更新为被规划的缺席的结束，和将此技术人员的地点更新为缺席的地点。

如果此技术人员还未进行休息并被规划为在此休息必须开始的最后时间之后结束他的缺席，则指示此技术人员继续此缺席，并在下一次接触系统之前进行休息(步骤1212)。此技术人员的规划被更新包括此休息和缺席的持续时间，和估算的行进到缺席地点的时间，并记录现已进入休息(步骤1216)。

返回步骤1203，如果下一缺席尚未预期地开始，系统即在此缺席预期开始之前分配能被进行的最好的任务(步骤1205～1210)。其规则如下：

步骤1205确定下一规划的活动是否是缺席(亦即，在被规划的缺席之前未规划任务)。如果是这样，利用后面参照图13的处理来搜寻-任务。但如果在缺席之前规划-任务，则进行一将在下面图14说明的可行性测试(步骤1206)。如果在必须进入休息之前剩余的时间中被规划的任务维持为可行的，如由步骤1206测试的，则对在此任务之后是否仍能进行被规划的缺席作出评估(步骤1207)。如果此任务通过个二测试(步骤1206、1207)，则它被分配到此技术人员，他接收指令来执行它(步骤1213)。但如果被规划任务未能通过二测试，即它不能在此缺席或-规划的休息的预定时间之间被执行，则利用图13的处理标识替代任务。

现在说明如图13中表明的分配技术人员到任务的处理。这一处理是背离先前系统的基本点之一。在这样的先前系统中，如果一技术人员具有预定的规划，如果可能它将总被分配到该规划中的下一任务，或者一已在系统中但还未规划给另外的技术人员的任务。在这样的配置中，对自从此规划系统最后的有规律更新以来该系统新的任务在下一次有规律更新之前将不会被分配。这里所说明的处理按照它能影响任何指定的技术人员允许在每次它接收一新任务时进行规划优化，而不管他是否报告如所规划的，和不管一可执行的任务是否已为他的执行而进行规划，并在这样的优化中甚至考虑到自从最后的规划修正以来被加到系统的任务。这使得在整个规划的重建之间能有更多时间，并因而能有更多时间用于各重建过程。

分配一任务给不是一被规划来做它的技术人员将仅在有关该技术人员方面修正规划，而如果此任务原先是对另一技术人员规划的，即其他技术人员。在工作日期间，周期地建立新的规划。这样作的频率将按照发生变化的速率来选择，这样使得先前的规划在新的一个成为可用之前不致因在线变化而完全破坏。但是能用于生成各新的规划的时间越多。所能生成方案越优化。

如果可能，用于优化阶段31的第一循环中的初始规划可以是依据由决定性级30所加入的任何新的固定点的、由实时优化器40在前面的周期中生成的当前规划。

尚不没分配的任务的细节(不管是否作规划分配)被存放在“工作池”数据库44。在考虑分配任务给技术人员时确定下列因素，以便用于发生的各种修改和优化检查：

a、注定此技术人员要参与考虑中的任务从该处行进的位置，它被认为是此技术人员的当前任务所在的地点，或者如果尚未被分配任何任务时则为他的工作日开始地点；

b、分配起始时间(即，技术人员的当前时间或工作时间的开始，并且哪一个都是较晚的)；

c、此技术人员的工作时间的剩余时间，包括任何被规划的超时；

d、此技术人员必须结束其工作周期的地点，它可以是他家所在地或被规划缺席的地点；

e、优选的工作地点，和围绕它的行进半径。位于此半径之外的任务将不分配到此技术人员；和

f、可移动限制，这被设置来防止由一任务到另一任务的过长的行进时间。

如图13中表明的，在第一步(1301)，检查确定是否对此技术人员规划有任何任务。如果有这样的任务，如果现在分配给此技术人员的话，处理接着利用-测试1302(图14的子程序)检查此任务是否仍可进行。此被规划的任务有可能因为未规划的变化结果，特别是如果此技术人员在比所规划的早或迟报告的话，此技术人员不可能执行。如果以下所有条件均满足此任务可进行：

a、此技术人员在他的规划工作时间内具有足够时间执行此任务，或者如果此任务已被分割越过工作日结束(在不同的日期上通过被规划的开始和结束时间标识)，此技术人员将能在所规划的工作时间结束之前完成的任务的预期持续时间的部分大于一预定最小值；

b、此任务满足休息管理的要求(见图14)；

c、如果任务要在一定的时间之间执行，技术人员的预期到达现场的时间在此期间之内；和

d、此信息没有被分配到一不同技术人员。

如果在技术人员的规划中的下一任务不能通过所有上述检查，则认为此任务不可行，否则即为可行。

不管此技术人员的临时性规划中是否有可行的任务，系统现在均试图通过运行多个测试来改善此临时性规划。这些在图13中被标识为测试1303、1304、1306(如果有可行的任务，亦即如果二测试1301和1302的输出均为正)，或者测试1304A、1306A和1309(如果当前不存在有可行的被规划的任务，亦即如果测试1301或测试1302的输出为负)。这一处理这样被设计是使得如果存在有可行的被规划任务，只有在有机会在服务质量上作重大改善时才将规划打乱。

首先，如果标识到-可行的任务，即进行测试以确定(步骤1303)此被规划任务是否被标记为很高的重要性或难以分配。如果是，即不再作进一步优化将其分配给技术人员(输出1308)。

在所有其他情况中(亦即如果规划中没有带这样标记的可行的任务)，处理研究(步骤1304/1304A)工作池44中是否存在有尚未被规划的标记为非常重要和接近其承诺时间的任务。这可能因为多个原因发生，例如因为它是一新任务，或者是一个从别处的其他规划中丢失的。

为再分配一任务到当前联机的技术人员，必须满足参照步骤1302所述四个条件，以及如下的：

e、此任务没有被预规划器30“绝对规划”到被规划技术人员(如果有的话)；

f、考虑中的技术人员具有所需的技能并答应承担此任务；

g、任务的地点在此技术人员的地理限制之内；

h、此任务在其目标时间的一预定周期内；和

i、此任务能在技术人员的下一固定任务之前执行。

所有被这样选择的任务然后被排列成如下序列：

1.任一专门预规划给联机技术人员的任务；

2.到任务的行程时间(按增加次序)；

3.技能偏好；

4.优先级(按递减次序)；和

5.承诺时间。

可利用已知的路由导航系统考虑到例如道路类型、工作日的时间等因素来计算由一地点到另一地点的行程时间。在规划一任务而前面任务还未规划时，在普通地区采用用于任务的典型行程时间因素。如果任务标记为“不准确”，或在对规划正进行修改操作，行程时间必须重新计算，因为对被规划项的估算将不再正确。

符合以上条件和休息管理条件的所得清单中的第一个任务被选择来分配到联机技术人员(步骤1305)。如果没有发现这样的任务，即作进一步测试(步骤1306/1306A)，在测试中确定是否有满足下列条件的任务：

-它比联机技术人员的规划任务(如果有)的优先级高，

-它在步骤1304/1304A未被考虑，

-它已经规划给另一个技术人员，

-该联机技术人员能比所规划的其他技术人员更早到达。

现在对所有满足这些条件的任务加以评估。应用同样的测试，只是将任务要接近其目标时间(上述测试“i”)的要求替代为仅只需考虑优先权高于被规划任务(如果有的话)的任务的要求。如果找到合适的任务，就将其优先于被规划任务(如有的话)分配到技术人员(步骤1307)。

如果测试1304或1306都不能产生更合适的任务，此被规划任务即被分配(步骤1308)。但是如果有负输出到二测试1304A和1306A(亦即在规划已被分解时的相同测试)则无可加以分配的被规划任务。代之以，指示技术人员与他的上级联系取得指令(步骤1309)。

在步骤1304、1304A、1306、1306A选择任务中，要求测试来保证任务能在其约定时间(如有的话)进行。还必须考虑关于是否也应指示技术人员在其下次接触控制系统之前进行休息。也需要类似测试以评估被规划任务的可行性(步骤1302和1206)。图14说明此测试。此处理有三个目标。第一，保证在他的被分配的时间窗内进行休息。第二，如果一项任务不能被立即分配，可配置一休息以允许一任务在该休息之后被分配。例如，除非事先进行休息否则指定到达可能太早，这是由于对此技术人员允许其在那个时间进行休息。第三，在任务已被分配给技术人员时，如果约定所在的期间与技术人员将到达地点的时间不一致则拒绝任何约定任务。

在此处理中进行的第一个测试确定是否应考虑-休息。如果所有被规划的休息均已被采取，所考虑中的任务即是可行的，除非此技术人员不能在约定时隙(如有的话)到达任务地点。因此系统首先测试任务是否有约定时隙(步骤1402)和如果有此技术人员能否在该时隙到达(亦即既不太早引起空闲时间，也不太迟，步骤1403和1404)。如果他能在约定时隙之内到达，或如果没有约定时隙，任务就是可行的(1410)。如果他不能在约定时隙内到达。任务是不可行的(1413)。

如果此技术人员还有要作的休息，测试有四种可能输出(如图14中步骤1410到1413所示)。任何一个任务是不可行的(1413)或者它是可行的，后一种情况下有可能需要在任务之前(1412)或在其进行中(1411)规划休息，或者如果任务能在作出休息之前完成则根本不要(1410)。

如果此技术人员尚未作出休息，则步骤1401中的测试返回一正的结果。在此情况中，下一测次再次检查此任务是否有-约定时间(步骤1402A)。如果有，则对此技术人员是否会针对此约定太早进行测试(步骤1403A)。如果此技术人员不会太早，即进行测试以检查此技术人员是否将在约定隙结束之后到达(步骤1404A)。这三个测试基本上与上面讨论的步骤1402、1403和1404中的相同，但它们导致不同的结果。如果测试1404A的结果为正的(换句话说，技术人员只有在约定时隙结束之后才能到达)，则此任务对该技术人员是不可行的(输出1413)而必须分配-不同的任务给此技术人员。如果此技术人员可不太早也不太迟(测试1403A和1404A的结果均为负)则进行测试(步骤1405)来检查任务是否能在休息开始的最迟时间之前完成。如果此测试结果为正则任务可行，而无需作休息指示(输出1410)。但如果此任务不能在必须作休息的最迟时间之前完成(测试1405的结果为负)则进行下一测试(步骤1406)以确定此技术人员立即进入其休息是否仍太早。如果此测试的结果为正，则此任务为可行但必须在任务期间进行休息(输出1411)，因为测试1405的结果为负，所以此任务不能在必须作休息的时期结束之前完成。但如果可能进行休息的时隙已被打开(测试1406为否定)，进行另一测试(步骤1408)来确定如果此技术人员要立即进入他的休息他是否仍能在约定时隙结束之前开始此任务。如果输出为正(亦即如果在其前面进行休息则此任务是可行的)，指示此技术人员作休息然后执行任务(输出1412)。但是如果此测试1408的响应是正的，则任务是不可行的(输出1413)。这是因为此休息和任务均不能在另一个必须开始的最迟时间之前完成。

如果测试1403a(对此约定此技术人员将会太早？)是正的，则进行测试1406a(类似于测试1406)：虽然在此瞬间如果休息时隙和约定时隙没有被打开(1406a为正)则此任务为不可行(输出1413)。如休息时隙已被打开(1406a为负)则进行另一测试1407以确定在此技术人员的休息结束时用于约定的时隙是否将打开。如果不将这样，则此任务仍然在当前是不可行的(输出1413)。这并不是说此技术人员根本不能进行此任务，而仅只是它不能是他的下一个任务。下一测试1408与前面的情况相同。它决定如果作休息此任务是否能在约定时隙结束之前开始。这一测试的结果既可能是任务可行的和应在任务之前进行休息(输出1412)或者是任务是不可行并必须指定某一另外的任务(输出1413)。

最后，如果测试1402a的输出为负的(亦即此任务没有约定时间)则进行类似于测试1405的测试1405a，以确定任务能否在作休息的时隙结束之前完成。如果此结果为肯定的则此任务可行的，对休息不要求指示(输出1410)，否则进行另一测试(1409)以确定技术人员是否会在休息时隙开始之前到达任务。如果他不是(1409负)，则指示技术人员在任务起动前作休息(输出1412)。否则，他被指示在任务期间作休息(输出1411)。

现在回到图12，在步骤1208，如果由图13的处理找到适合的任务(输出1305、1307、1308)，这一任务连同在可行性测试中所产生的任何其他指示被分配到此技术人员(步骤1213)，(图14)，例如在任务之前(1412)或在任务期间(1411)作经规划的休息。但是，如果没有发现有效任务(输出1309)则进行测试确定是否能作休息(步骤1209)。如果未规划休息，技术人员无工作并被指示与其上级联系取得指令(步骤1214)，或被允许在工作日结束工作或等待进一步指示，例如可能进入新的任务或进入其约定窗内。

如果能作休息(步骤1209)则进行测试(1210)确定如果被规划有缺席但尚未到期开始时能否在休息之后立即缺席。这是一关于在休息期间结束时刻之前进行预期缺席的测试。(应指出，如果此缺席已到期开始，测试1203的结果将成为负，所以将以进行测试1204替代测试1210)。取决于这一测试的结果(步骤1210)技术人员被指示仅作休息(步骤1215)，稍后作在他的规划中余留的缺席，或者同时作缺席和休息(步骤1212)。如未规划有缺席(测试1202的结果为负)则对步骤1210中查询的回答自然总是负的，因而输出1212是无关的。

一旦一任务被分配，带有或不带有休息(输出1211、1212、1213或1215)，或决定没有任务或其他活动例如缺席或休息能分配，(步骤1214)技术人员即被作相应地指示。此指令由消息发生单元48产生。这可生成一分配显示供一个调度员用来传送此指令到技术人员T，或者通过通信链接C直接将数据消息传送到技术人员的手机(例如H1)。被修正规划细节被存放在数据库42、43、44中(步骤1216)。对于技术人员寄存器43这些列举技术人员的当前地址和预测完成时间(亦即，预期技术人员的下一个联机请示新指令的时间)。这通常为行进到此新任务的时间、此任务的预期持续时间、和已被规划的任何缺席和休息持续时间的总和。

规划42也可被更新。如果被分配的任务是被规划给联机的技术人员，则该项即简单地被作为现在已被分配的加以删除。如果此技术人员被规划另外的任务，则如果被分配的任务是来自另一技术人员的规划，则就必须从此另一技术人员的规划中删除该项。在此技术人员的规划中所有其余项被标以“不准确的”，因为这些规划是基于假设他将首先进行现在已被分配在别处的任务。同样的，在联机技术人员的剩余规划中的所有项也因同样原因被标作“不准确的”。任何被标作为“不准确的”任务均被认为是不再规划的，因为不存在有任何原先被规划技术人员将仍能执行它们的必然性。在选择分配给其他技术人员的任务中，“不准确的”项可被给予高于那些被标以“未决的”的项的优先级，因为它们有更大的不被分配失败的危险。

在进行图5～10的初始规划生成处理期间发生的对系统的输入，例如要加到规划的新任务或技术人员报告任务的完成，将使得初始规划在产生此规划时部分不正确。图15、16和17为是说明处理这样的输入的三种方法的时间路线。

在此三个图中，输入用参考号1，1a指明，而输出，例如响应这样的输入对技术人员的指令，以参考号2，2a指明。初始规划生成处理由参考号3，3a指明，和规划修正处理由参考号4，4 a指明。将会注意到，通常二处理3和4并行发生，初始规划生成处理3提供修正处理4a的下一循环的输入。

在各种情况中，在初始生成处理不运行时发生的输入1按照规划处理4和所生成的任何必须的输出2加以处理。这些输入也被提供给初始规划生成器3的下一次运行。

图15中，规划修正处理4在初始规划生成处理期间暂停。在初始生成处理3处在运行中发生的输入1a按照当前修正处理4不立即处理而在存储器5中加以缓存直至处理3完成，然后根据新的初始规划按修正处理4a加以处理，提供输出2a。

另一方面，在图16中，利用应用现有数据的修正处理4在接收到输入1a后立即生成输出2a，但在初始规划3完成时输入1a也被缓存以便对新的修正处理4a提供输入。这具有提供即时响应2的优点，而图15的配置则具有利用更新近的初始规划生成响应2a的优点。选择一种或其他配置取决于1a与输出2a之间的可接收的延迟。

如果提供了要求对初始规划作实质性的修正的数据1b，以致利用现有初始规划生成的方案3、4将成为无效，将规划修正处理4和初始规划生成处理3暂停(如果目前在运行)，然后再以新数据重新起动(3a)初始规划生成处理。在重新起动处理3a运行期间接收的数据2a被加以缓存(5)直至生成新的规划。

Claims

1.一种任务分配设备，包括：

输入装置，用于提供有关欲分配的任务和可用于执行该任务的资源的信息；

规划生成装置，分配资源到任务，由此各资源生成一初始规划；

存储装置，用于存储初始规划；

更新装置，用于从输入装置接收有关任务和资源的更新信息；

修正装置，用于响应这样的更新信息来修正至少一第一资源的初始规划，

由此即可独立于规划生成装置响应这样的更新信息来改变初始规划。

2.按照权利要求1的设备，其特征是规划生成装置被配置为按照以输入装置所接收的数据周期地生成初始规划，和修正装置被配置为响应在这样周期生成初始规划之间接收的数据来改变初始规划。

3.按照权利要求1的设备，其特征是规划生成装置包括：

一第一决定性级；

用于选择欲通过此第一级规划的任务的装置；和

一第二优化级，用于规划其余任务，其中，此第二级包括有将由第一级规划的任务作为固定的处理的装置。

4.按照权利要求3的设备，其特征是用于选择供第一级规划的任务的装置被配置为选择多组涉及多于一个资源或形成一任务序列的链接任务。

5.按照权利要求3或4的.设备，其特征是第二级按照一随机处理进行操作。

6.按照权利要求5的设备，其特征是此随机处理是SimulatedAnnealing处理。

7.按照权利要求3的设备，其特征是规划生成装置包括一第三后优化级，它包括：用于分析由第二级生成的规划的装置；用于标识要求进一步优化的规划的装置；和用于将这样的规划输入进第二级的又一循环以做进一步优化的装置，此第二级的又一循环具有将未被如此标识的规划作为固定的进行处理的装置。

8.按照权利要求3的设备，其特征是修正装置包括多个选择装置，各自用于依次对多个等待执行的任务加以评估以确定适宜于由第一资源执行的给定优先级的任务是否可行，并将这样任务分配到第一资源，此选择装置被配置为标识逐次递减优先级的任务，以便使得高优先级的任务在针对第一资源的初始优化规划中优先于较低优先级任务被分配。

9、按照权利要求8的设备，其特征是至少一个选择装置包括第一评估装置，该评估装置用于确定第一资源的初始优化规划是否包括有此给定优先级的任务，并在包括时选择所述任务，和第二评估装置，在如果此第一资源的初始优化规划不包含这样的任务时可运行来确定是否存在有未被规划的任务，并如存在时选择所述任务。

10、按照权利要求7的设备，其特征是修正装置包括用于标识具有与第一资源的这些的特征相关的资源的装置，和被配置为响应更新信息修正只有那些具有这样的特性的资源的规划。

11、按照权利要求7的设备，其特征是还包括用于在生成初始优化规划之后加入另外的任务和/或资源到多个欲规划的任务和/或资源的装置。

12、一种分配多个资源到多个任务的方法，此方法包括利用计算机执行下列功能：

提供关于欲加分配的任务和可用于执行此任务的资源的初始信息；

为各资源生成分配资源到任务的初始规划；

存储此初始规划；

提供关于任务和资源的更新信息；和

响应这些更新信息修正至少一第一资源的初始规划，

由此即能独立于生成此初始规划的处理响应这样的更新信息来改变初始规划。

13、按照权利要求12的方法，其特征是初始规划被周期地生成，和这样生成的初始规划响应在这样周期生成初始规划之间接收的数据被加以修正。

14、按照权利要求13的方法，其特征是在周期生成初始规划期间暂停修正处理，此更新信息被保留直到生成新的初始规划，然后在完成它们的生成时用来修正这些初始规划。

15、按照权利要求13的方法，其特征是在生成此初始规划期间此修正处理继续，经如此修正的规划在它们的生成完成时被作为对初始规划的修正输入。

16、按照权利要求12的方法，其特征是如果接收到一基本的更新数据项即启动规划生成处理。

17、按照权利要求12、13、14、15、16中任一个的方法，其特征是规划生成功能包括用于规划所选择任务的第一决定性级，和用于规划其余任务的第二优化级，其中，此第二级将经过第一级规划的任务作为固定的来处理。

18、按照权利要求17的方法，其特征是选择多组涉及多个资源或形成一任务序列的链接任务以便由第一决定性级进行规划。

19、按权利要求17的方法，其特征是此第二级按照一随机处理操作。

20、按照权利要求19的方法，其特征是此随机处理是一SimulatedAnnealing处理。

21、按照权利要求17的方法，其特征是此规划生成功能包括一第三后优化级，在此对由第二级生成的规划加以分析以标识要求进一步优化的规划，和将这样的规划输入到此第二级的又一循环作进一步优化，此第二级又一循环将未被如此标识的规划作为固定的来处理。

22、按照权利要求12～16中任一个的方法，其特征是，此修正处理包括多个选择步骤，在其中每一个中对多个等待执行的任务加以评估以确定适宜于由第一资源执行的一给定优先级的任务是否可行，如被标识即将这样的任务分配到第一资源，这些选择步骤被配置为标识优先级递减的任务，以使得高优先级的任务优先于一个较低优先级的任务加以分配，而不管高优先级任务是否在此第一资源的初始优化规划中。

23、按照权利要求22的方法，其特征是至少一个选择步骤首先确定此资源的初始优化规划是否包括一给定优先级的任务，如果包括即选择所述任务，或者如果此资源的初始优化规划不包含这样的任务，则确定是否存在一未被规划的任务，如存在即选择这样的任务。

24、按照权利要求12～16中任一个的方法，其特征是此修正功能标识具有与第一资源的那些相关的特性的资源，和修正只有那些具有这样的特性的资源的规划。

25、按照权利要求12～16中任一个的方法，其特征是在生成此初始优化规划之后可将另外的任务加到多个欲执行的任务。