烟草在线摘自《烟草科技》　　激光导引运输车系统（Luser　Guided　Vehicle　System，LGVS）集机械、电子、光学、计算机、传感器、通信、信息处理等高新技术于一体，在柔性自动化物流系统中起着重要作用。LGVS任务调度（Dispatch by task）涉及运输车对象、任务队列、网络拓朴结构及道路交通状况，是一个复杂的系统工程。目前，实际运用的LGVS任务调度策略还停留在单个任务的执行效率，虽然策略简单易行，但缺乏整体性，没有充分利用任务队列中各实体之间的内在联系，其系统稳态平均能力和实体通过系统的稳态平均滞留时间均有损失，而仿真、人工智能等方法，由于模型复杂、求解耗时等原因还处于研究试验阶段。针对上述问题，论文提出了一种结合数学规划与预约思想，用预约调度（Dispatch　by　appointment）的方法，提高LGV$的搬运能力和任务实时性。

　　1　LGVS网络图及指派模型

　　LGVS任务调度在优化的系绕网络拓朴结构（Map）上，以网络最短路径（Shortest　Path）为基础，充分利用系统资源，优化调度指派关系，从而使系统总体效益最佳。

　　1.1　LGVS网络图模型

　　LGVS网络图（Network Map）是一张有向电子地图，它描述了系统网络构成元素的属性及其相互之间的网络拓朴结构关系，是求解系统最短路径问题的前提，也是LGVS进行运输车检测定位以及系统高级数据处理（如决策、评定等）的基础，该模型中，网络图主要构成元素有：LGV、点、站台、段、簇、区域及其拓扑结构关系。

　　以LGV运输车在卷烟生产车间的应用为例，研究LGVS的任务调度问题，所建立的LGVS网络图模型如图1所示。以SQL Server2000作为系统后台数据库，以Delphi6.0为开发平台，建立LGVS网络图模型并将各图元素及相互间的拓朴关系以数据库表的形式保存。

　　图1中，A1-A5：LGV运输车，往返于各站台间，执行物料托盘搬运任务；S1-S3：出库站台，仅为LGV运输车的取货站台，为搬运起始地址；S4；回收站台，仅为LGV运输车的卸货站台，为搬运目标地址；S5-S23；普通站台，既可以是起始地址，也可以是目标地址。

　　1.2　指派模型

　　在诸如有若干项搬运任务需要分配给若干辆LGV来完成的指派问题（Assignment Problem）模型中，首先需引入n2个0—1变量，并赋予χy以下含义：

　　（1）

　　这样，0-1指派问题的数学模型可写成：

　　公式（2）

　　图1　LGVS　网络图模型

　　该模型中，称矩阵C=（cy）n×n为指派问题的效益矩阵（Efficiency　Matrix）或系数矩阵。此类指派问题有n！个可行解，而研究目标是找出n！个可行解中最优或较优的—个解。

　　2　服务系统的顾客预约调度

　　如果把LGVS视为一个服务系统，那么LGV运输车就是该服务系统的服务员，而散布在车间的各物料站台间的搬运任务是服务对象（顾客），LGV运输车搬运托盘过程为服务活动。以下所提到的顾客就是指系统任务，站台提出物料请求（呼叫）称顾客到达，服务员指LGV运输车，LGV运输车完成搬运称服务结束。

　　目前，许多LGVS任务调度策略主要考虑单顾客的服务效率，采用先到先服务（First　Come，First　Served）或高优先级先服务（High　priority，First　Served）的原则。为了追求系统整体效益最佳，引入了顾客预约调度。在预约调度系统中，系统为每一位服务员预定两个顾客缓存区用于存放在服务顾客和预约顾客，服务员可以为一位顾客提供服务的同时预约另一位顾客。如图2所示，在服务员状态为空闲时，系统先指派的黑色顾客立刻接受服务，后指派的灰色顾客处于预约等待状态，当服务员对黑色顾客的服务结束时，灰色顾客立即占用黑色位置，由预约顾客变为在服务顾客，并马上接受服务员的服务活动。由于系统调度指派的顾客并不一定直接得到该服务员的服务活动，可能仅仅得到服务预约，因此，称之为预约调度。

　　该服务系统有3类实体：服务员LGV、顾客Task 和顾客队列Line。服务员是永久实体，其活动为搬运托盘，有预约、预约空闲和空闲，3种状态。顾客为临时实体，它接受服务员的服务，有等待预约、预约服务、接受服务及结束服务等状态。顾客队列是一类特殊实体，其状态主要以队列长度来标识，本文中的顾客队列专指未接受预约的顾客队列。3类实体的活动及状态之间存在逻辑上的联系。

　　（1）顾客到达服务系统，如果所有服务员处于忙且均被预约状态，则该顾客进人排队队列处于等待预约服务状态；如果所有服务员处于忙但有未被预约的服务员状态，则系统进行预约调度，该顾客进入预约队列处于等待服务状态；否则，直接进入接收服务状态；预约顾客在接受服务之前允许参与下一次预约调度；

　　图2　LGVS预约调度流程

　　（2）系统指派服务员为顾客提供预约服务或直接服务，服务结束时，如果有预约顾客，则该预约顾客直接进入服务队列接受服务，此时，如果顾客队列队长为非零状态，则系统立即进行预约调度运算并将结果下达给服务员形成服务预约，否则，该服务员处于预约空闲状态；如果预约队列和顾客队列队长均为零，则服务员进入空闲状态。

　　顾客到达或预约顾客结束排队活动可以导致服务活动开始，而顾客离去可以导致服务活动的结束，因此顾客到达或离去可以作为事件看待。但由于预约顾客结束排队是以服务员状态为预约空闲为条件的，因此它是条件事件，所以预约顾客结束排队事件可以并入顾客离去事件。顾客到达使某一服务员状态由闲变为忙或从预约空闲到预约，使队列长度加1；顾客离去使某一服务员状态由忙变为闲或从预约变成预约空闲，使队列长度减1。

　　LGVS顾客预约调度具有以下优点：①有利于构造指派模型的效益矩阵；②预约顾客的再调度，动态响应了系统由于交通阻塞等原因造成的效益矩阵系数的变化，从而保证了系统调度的动态较优；③有利于LGV单机作业复合循环，减少了服务员的空载时间，提高了服务员的有效作业率；④调度服务的提前预约，有利于充分利用系统计算机的“闲期”资源，避免了系统因调度运算繁忙，造成LGV运输车完成任务后等待调度的现象。

　　3　LGVS预约调度算法的实现

　　基于网络图最短路径，将预约调度思想与标准指派模型相结合，实现LGVS的预约调度。

　　3.1　构造预约调度效益矩阵

　　一般情况下，LGVS任务指派模型并不符合指派问题的标准模型，因为在系统运行过程中难以直接确定满足调度条件的n辆运输车与n条任务，且效益系数难以直接获取，顾客数与服务员数也不相等，为此有必要引入一些约定。

　　3.1.1　确定效益矩阵的维数n

　　确定调度车辆n。因为系统允许预约顾客参与再调度，所以调度车辆数为所有“在线且正常”的LGV运输车。“在线”确保了服务员正在上班，“正常”确保了服务员无故障、交通阻塞、蓄电池电量低等异常状况。

　　确定调度任务m。首先假设排队顾客队列长为l系统某一次调度运算时有m1位顾客从顾客队列进入调度机（见图2），参与预约调度的顾客数（包括再调度顾客）为m，已知系统完全空闲的服务员数为n1，正在进行服务但未预约顾客的服务员数为n2，有预约顾客的服务员数为n3，则有：

　　（1）n1+n2+n3=n，m1+n3=m；
　　（2）当l≤n1+n2时，m1=l；
　　（3）当l>n1+n2时，m1=n1+n2；
　　（4）m≤n。

　　可见，当n1=n时，系统完全空闲；当0<n1<n时，表示系统没有满负荷运行；当n1=0且0<n2≤n时，表示系统满负荷运行，但仍可继续预约新顾客；当n3=n时，表示系统满负荷运行且所有服务员都在进行服务活动且都被预约，此时，系统只能进行n位服务员与n位预约顾客间的再优化调度。

　　当m>n时，系统仅取优先权较大的m1位顾客进行预约调度；当m<n时.约定：系统进行预约调度时添加一些虚拟顾客使m=n，这些虚拟顾客被各服务员服务的效益系数为0。这样，系统m位顾客与n位服务员之间的所有对应就可以构成n×n阶效益矩阵C=cy（i，j=1，2，…，n）。

　　3.1.2确定效益系数cy

　　由于LGV运输车装卸载时间远小于其行走时间，不同运输车的装卸载时间也近似相等，且每条任务的起点到终点的最短路径一定，因此，约定：效益矩阵C的每一系数cy为若干段最短路径之和，cy表示从调度时刻开始，第i位服务员到达第j位顾客的起点并开始服务时刻的时间。

　　系统通过调用网络图最短路径算法模块确定第i位服务员服务第j位顾客的效应系数（或预约效益系数）。当服务员i空闲时，cy表示运输车i从当前位置移动到任务j起始点的最短路径值；当服务员i繁忙时，由于在LGV运输车执行预约任务前必须完成当前的执行任务，所以cy表示当前任务的完成时间加上当前任务终点到预约任务起点的最短路径值。如图3所示，已知LGV运输车当前位置处于p1点，正在执行的任务起点为p2，终点为p3，预约任务的起点为p4，终点为p5，图3中L1、L2、L3、L4均为相应两点间的最短路径，则运输车执行预约任务的效益系数Cy=L1+L2+L3。

　　3.2 LGVS任务指派模型的求解与程序实现

　　LGVS可以根据任务和运输车状态迅速构造出任务预约调度效益矩阵。此类指派问题有n！个可行解，目标是找出n！个可行解中最优或较优的一个解。

　　3.2.1 LGVS服务系统实体表

　　设计两张基本表：任务表TBL_TaskDoing和运输车状态表TBL_Lgv，实时跟踪记录系统状态变化，为系统进行预约调度提供实时数据。而派生的或临时的如预约顾客队列、预约服务员队列等，仅以临时效组记录。

　　图3　LGV当前预约效益系数

　　任务表TBL_TaskDoing。用于记录LGVS实时接收的搬运任务信息的二维表，每条记录包括任务号、搬运类型、任务状态、起始点、目标点、申请时间、结束时间、优先权、紧急度、服务运输车等信息。

　　运输车表TBL_Lgv。用于记录LGV运输车信息的二维表，实时记录LGV运输车的在线模式、当前位置、状态、装载情况、在执行任务、预约任务等状态。

　　3.2.2　设计预约调度触发条件

　　引起LGVS顾客预约调度的系统事件，称为调度触发条件。该事件的发生必将引起系统状态的改变，为此设计了3个预约调度触发条件：

　　（1）服务员空闲或预约空闲条件。即系统中至少有一辆LGV运输车完成任务处于预约空闲状态；

　　（2）顾客队列非零条件。即待预约调度任务队列长不为0（预约或未预约任务和非0）；

　　（3）预约+定时条件。即争抢预约条件，只要系统存在预约任务，则定时触发预约调度，动态寻求新系统状态下的最佳调度方案。

　　当（1）、（2）两个条件均满足时，系统触发任务调度。由于网络图最短路径计算占用大量的系统资源，在两次预约调度间隔之间，可能出现多位服务员完成服务状态。此时，服务员在调度系统做出反应之前，自动将其预约顾客（如果存在）变为服务顾客，从而减少调度系统的响应时间对系统效率的影响。

　　条件（3）为争抢预约条件，系统在调度计时器触发下，即使条件（1）、（2）均不满足，只要存在预约顾客，系统也会对预约顾客进行再调度。因此在系统出现诸如服务员故障、交通阻塞等故障时，系统能够对调度方案进行动态调节，寻求最佳调度方案。

　　3.2.3　LCVS预约指派问题的程序实现

　　构造效益矩阵和调度触发条件后，利用匈牙利法，对效益矩阵进行求解。将系统优先权与系统整体效益最佳有机地结合在一起，并以SQL　Server2000作为后台数据库，应用Delphi应用程序开发任务预约调度算法程序。

　　任务按优先权排序，根据任务调度机的状态依次单个或成批进入任务调度机，从而保证优先权高的任务优先调度指派。对于在任务调度机中的预约任务，由于运用了预约调度的指派模型算法，保证了系统整体效益最佳。

　　4　LGVS调度仿真

　　为了检验预约效益矩阵调度算法，并与传统LGVS任务调度算法进行定量分析和比较，从模型系统中随机抽取某一时刻的运输车状态，并构造一组任务，分别运用逐条任务逐辆LGV扫描法、逐条任务最短路径法和预约调度效益矩阵法进行系统调度仿真，并对仿真结果进行分析与比较。

　　4.1　仿真评价指标

　　4.1.1　系统稳态平均能力a（能力指标）

　　公式　（3）

　　式中：n1——系统LGY_运输车数量，l——第i个任务的延误时间，n——接收的任务数。

　　系统稳态平均能力就是LGVS在单位时间内能够平均完成的物料托盘搬运个数，以反映LGVS的整体搬运能力。

　　4.1，2　实体通过系统的稳态平均滞留时间w（延误指标）

　　公式　（4）

　　式中：w——第i个实体通过系统时的滞留时间，它等于实体在队列中的等待时间D，与该实体接受服务的时间S1之和。

　　在LGVS中，系统的稳态平均滞留时间就是站台实体物料搬运呼叫到LGV运输车完成物料搬运工作的平均时间，以反映系统的服务响应实时性。

　　4.2　仿真比较

　　基于所建立的LGVS网络图模型，并综合两种顾客到达方式（成批到达勺单个间隔性到达），生成某一时间段（如某天17：00：00-18：00：00）内的一组搬运任务。其中，假设[17：00：00~17：30：00）区间有10条成批到达任务，[17：30：00-18：00：00）区间有10条间隔时间为3min的到达任务，见表1。模型系统拥有5辆LGV运输车，系统随机生成的运输车状态见表2。为了便于比较，假设系统车辆初始状态中均无预约任务（Task2）。

　　然后，分别应用3种调度算法对模型系统进行仿真调度，检验3种算法的性能指标。3种算法的仿真结果性能指标对比见图4。

　　表1　系统在[17：00：00-18：00：00）时间段内的一组搬运任务


　　表2　模型系统某一时刻的车辆状态

　　调度算法

　　a、系统平均能力仿真结果比较

　　调度算法

　　b.实体通过系统的稳态平均滞留时间仿真结果比较

　　图4　3种调度算法仿真评价指标对比

　　5　结语

　　通过仿真比较可以看出，对于类似于卷烟生产车间模型的自动化物流LGVS系统，采用预约调度效益矩阵法无论在系统稳态平均能力a，还是实体通过系统的稳态平均滞留时间w指标上，均优于传统调度方法。而且该算法结构简单，易于编程实现，并具有调度灵活、高效、实时、抗干扰的特点。

作者：（红塔集团玉溪卷烟厂）张贵、袁国旺、陈勇、罗兵、刘松