基于全局空闲工位优先的机动车检测调度算法

刘晓鑫，赵祥模，张立成，周 洲

(长安大学 信息工程学院，陕西 西安 710064)

0 引 言

近几年，我国机动车保有量爆发式增长[1]，但机动车检测行业的检测效率没有明显提升，导致检测行业提供的服务不能满足车主的检测需求。优化机动车检测调度流程是解决上述矛盾的有效途径之一。根据P. Brucker等研究可知：机动车检测调度属于柔性车间调度问题(flexible job-shop scheduling problem，FJSP)，Garey M R等研究结果表明该问题是NP-hard问题。

目前求解FJSP问题的方法主要可归纳为两类：精确求解和近似求解。精确求解可通过排列组合、分支界定、动态规划[2]等方法解决，但是只适应于规模较小的情况。在问题规模较大时，多采用近似求解法。S. Zhang等[3]通过改进蚁群算法，提出了增强型蚁群优化元启发式算法，用来解决作业车间环境下的调度问题。Piroozfard H等[4]通过考虑碳足迹在环境中的排放，提出了一种改进的多目标遗传算法，优化了工作车间调度问题。Nouiri M等[5]应用粒子群优化算法求解FJSP问题。Lu C等[6]从实际制造企业出发，提出了既考虑产品最大寿命，又考虑能源消耗的混合多目标回溯搜索算法，用于解决置换流车间调度问题。Gao L等[7]为了更好解决焊接行业中的动态调度问题，提出一种混合多目标灰狼优化器。Liu Y等[8]为了释放系统节能潜力，提升系统效率，提出了一种总电耗和总加权时滞最小化的双目标调度模型。上述学者针对不同实际环境对相应的FJFP问题进行了解答，但是在机动车检测领域，针对检测车间作业调度问题的研究较少。

本文以最小调度完成时间和最大工位资源利用率为目标，结合实际生产环境，采用全局工位优先的原则，对机动车检测调度流程进行了优化和改进。

1 机动车检测调度问题分析

1.1 问题描述

机动车检测调度问题可概括的描述为：将机动车检测任务安排在不冲突的时间和检测工位中，同时满足各种约束。具体地讲，有Vn辆机动车要在m个检测车间进行检测，每个检测车间有k个检测工位。已知每辆机动车在每个检测工位上的检测任务及检测耗时，对Vn辆机动车在m个检测车间上的检测顺序进行安排，使得Vn辆机动车在完成m个检测车间的检测任务后,一些性能指标达到最优化。本文中的最优化指标是：最小化完成时间和最大化资源利用率。

最小化完成时间指：完成最后一辆机动车的最后一项检测项目的时刻应该尽可能早，即完成所有机动车的检测任务，检测车间耗时最短。当Vn辆机动车完成检测项目申请后，各检测车间和检测工位分别要检测的机动车就已经确定。要使得检测完成时间最小化，需要通过调度算法，降低检测工位空转时间，使得各检测车间能够尽快的完成机动车的检测任务。

最大化资源利用率指在完成Vn辆机动车的检测任务期间，通过调度算法，尽可能使得各车间各检测工位能够时刻保持运转。换而言之，尽可能降低检测设备的空转时间。

1.2 约束条件

为了确保本算法在实际工程中的可操作性，保证检测车间能够有序正常运行，需要满足以下约束：①同一车间内机动车按工位排列顺序进行检测；②不同车间之间机动车可随意跳转检测；③各检测车间各检测工位检测任务各不相同；④同辆机动车同一时刻只能在一个工位接受检测；⑤设定原子时间，将每个项目的检测耗时设定为原子时间的整数倍；⑥检测任务一旦开始不得中断；⑦如果多个检测车间，同时竞争同一辆机动车时，当前检测车间正在检测的车辆数量少的车间优先；⑧如果多个检测车间，同时竞争同一辆机动车，并且当前各车间的检测车辆数量相等时，机动车能够最先检测的车间优先，否则随机选择一个车间检测。

1.3 解决方案

由1.1节可知，最小化检测完成时间和最大化工位资源利用率，均与检测车间中各检测工位的运行状态有关。因此，从检测工位角度分析和解决问题。

步骤1 将Vn辆机动车在各检测工位上申请的检测项目按照检测工位进行分组。每个检测工位维护一个检测车辆队列，队列中的机动车按照在该工位申请检测项目的先后顺序依次排列；

步骤2 在满足1.2节约束条件的前提下，当检测车间首个检测工位空闲时，从该工位的检测车辆队列中，顺序调度机动车进行检测；

步骤3 当所有机动车完成所申请的检测任务之前，循环执行步骤2。

2 基于FIFO策略的机动车检测调度算法

基于FIFO策略的机动车检测调度算法(简称为：FIFO)广泛应用在当今工业环境中，例如：榆林、咸阳、商洛等多地区的10余个机动车检验机构的机动车检测调度算法均是基于FIFO策略的调度方式[9]。FIFO具有理解简单、易于实现的优点，其算法调度流程可总结如下：

步骤1 将检测机构所有检测工位按照某个顺序进行排列，得到检测工位队列stationArray。检测工位在stationArray中的顺序一旦确定，不可更改；

步骤2 将申请检测的机动车按照申请时间先后顺序排列，得到机动车队列vehicleArray；

步骤3 从vehicleArray按顺序调度机动车，按照检测工位在stationArray中的顺序，依次完成机动车的检测任务。当前工位的下一个检测工位繁忙时，机动车必须在当前工位等待，直到下一个检测工位空闲时才可以进入检测；

步骤4 当stationArray中第一个检测工位没有机动车检测时，从vehicleArray中调度下一辆机动车进入检测流程。步骤4在算法调度过程中独立执行，时刻监控stationArray中第一个检测工位的状态；

步骤5 循环执行步骤3，直到完成vehicleArray中所有机动车的检测任务。

由上述调度流程可知：当采用FIFO调度机动车时，机动车必须顺序完成stationArray中的检测任务，不能出现跳过某个检测工位，检测下一个项目的情况。这样可能导致一个显著的问题：由于下一个检测工位处于繁忙状态，机动车完成当前检测项目后，继续在当前检测工位等待，即使该机动车在下一个检测工位没有检测任务也必须等待。这样必然导致：需要进入当前工位检测的机动车，也必须等待已经完成检测任务的机动车进入下一个检测工位之后，才能进入当前工位进行检测。最终导致：机动车等待时间加长、检测工位空转时间延长、机动车检测完成时刻延后、检测工位资源利用率降低。

因此，有必要引进新的机动车检测调度策略，克服和优化FIFO带来的缺陷和不足，缩短检测完成时间、提升检测工位资源利用率。

3 基于全局工位优先的机动车检测调度算法

3.1 符号定义

定义1 空闲工位:当前，如果检测工位没有对任何机动车执行检测任务，则称该检测工位为空闲工位。此时该检测工位处于空闲状态。如果机动车在空闲工位，说明该机动车在等待下一个检测工位完成检测任务。

定义2 繁忙工位:如果检测工位不是空闲工位，则该工位是繁忙工位。此时该检测工位处于繁忙状态。

定义3 空转时间:检测工位处于空闲状态的一段时间，称为该检测工位的空转时间。

定义4 繁忙时间:检测工位处于繁忙状态的一段时间，称为该检测工位的繁忙时间。

定义5 运行时间:检测工位空转时间与繁忙时间之和，称为该检测工位的运行时间。

定义6 未完成检测任务机动车队列:每个检测工位都维护一个未完成检测任务机动车队列(简记为：stationReVehicles队列)。将在检测工位申请检测的机动车，按照申请时间先后顺序排列，得到该检测工位的stationReVehicles队列。

定义7 机动车等待状态:如果机动车正在等待某个检测工位，则该机动车处于等待状态。

3.2 全局空闲工位优先

结合1.1节和第2章节的描述分析可知：为空闲工位选择机动车调度策略，关乎该调度算法的性能优良。结合空闲工位在实际车间的分布情况与当前机动车的检测情况，提出全局空闲工位优先策略：

当检测车间第一个检测工位处于空闲状态时，将该检测工位的stationReVehicles队列中，处于等待状态的第一辆机动车，调度到该工位进行检测。因为在全局范围内为空闲工位调度机动车，所以称为全局空闲工位优先。

3.3 算法流程与步骤

基于全局空闲工位优先策略，实现机动车检测的调度算法称为基于全局空闲工位优先的机动车检测调度算法(vehicle scheduling algorithm for testing based on global idle station priority，VSABOSP)。由1.2小节(2)、(3)，将检测车间的状态与该车间首个检测工位的状态保持一致。结合上述设定，将VSABOSP各车间具体流程阐述如下：

步骤1 根据Vn辆机动车的申请时间，为每一个检测工位构建stationReVehicles队列；

步骤2 在满足1.2节约束条件的前提下，基于全局空闲工位优先策略，为各检测车间调度机动车。各检测车间各检测工位并行执行检测任务；

步骤3 当检测车间首个检测工位完成检测任务后，将该检测工位设置为空闲状态。然后，同时执行步骤2和步骤4；

步骤4 基于FIFO算法完成机动车在该检测车间剩余工位的检测任务；

步骤5 从检测工位的stationReVehicles队列中删除已完成该工位检测任务的机动车；

步骤6 如果机动车已经完成所有检测任务，则驶离检测车间，等候打印报告单；否则，将该机动车设置为等待状态。

VSABOSP中每个检测车间并行执行，并且执行流程类似，如图1所示。

图1 VSABOS检测车间流程

3.4 算法复杂性分析

机动车数量作为算法的输入规模，采用基本操作计数法对算法的复杂度进行分析。由3.3节可知，从空闲工位的stationReVehicles队列中为其选取首辆处于等待状态的机动车，是本算法的基本操作。对于空间复杂度，以机动车信息作为基本计数单元。

3.4.1 时间复杂度

通过分析VSABOSP调度过程，空闲工位选取机动车的次数与在该检测工位申请检测的机动车数量成正比关系。因此，当算法输入的规模为n时，算法的时间复杂度为

T(n)=O(f(n))=O(n)

(1)

3.4.2 空间复杂度

在VSABOSP调度过程中，每个检测工位的stationReVehicles队列中均维护在该工位有检测任务的机动车信息。因此，对于n辆机动车在m个检测工位进行检测的情况，算法的空间复杂度为

S(n)=O(f(n,m))=O(n*m)

(2)

3.5 算法高效性证明

采用数学归纳法对VSABOSP的高效性进行证明。由1.2小节和3.3小节可知，检测车间状态与该车间首个检测工位状态一致；车间完成检测的时刻与该车间最后一个检测工位完成检测的时刻一致。

在下面证明之前，结合工业实际，作如下假设：

假设1：算法在3个检测车间内调度，检测车间分别为车间a、车间b、车间c。车间a、b、c仅表示车间代号，无实际意义。

假设2：申请检测的机动车数量为Vn。其中Vn为整数，取值范围：Vn∈[1,+∞]。

假设3：FIFO按照车间a、车间b、车间c的顺序调度。

(1)当Vn=1时:此时，只有一辆机动车，由假设1可得:任何检测顺序都是等价的。因此，以车间a、b、c的顺序进行检测。检测调度Gantt图，如图2所示。

图2 Vn等于1

此时，VSABOSP和FIFO的调度耗时，均为任务1、任务2、任务3三者检测耗时之和。即VSABOSP调度时间不会大于FIFO。

(2)假设当Vn=n-1时，VSABOSP比基于FIFO的检测调度算法高效。

用集合 {0,1,2} 中的元素组合表示车间a、b、c在完成自身车间最后一辆机动车检测任务的时刻先后顺序。每个车间可以取集合 {0,1,2} 中的任意值。例如：组合为 (2,0,1)， 则表明车间b首先完成检测任务，然后车间c完成检测任务，最后车间a完成检测任务。

无论采用VSABOSP，还是FIFO，当完成n-1辆机动车的检测调度任务后，各检测车间的完成时刻组合，见表1。

表1 车间完成检测时刻组合

(3)当Vn=n时:将当完成n-1辆机动车的检测任务时，FIFO在车间a、b、c的完成时刻分别记为：TFa(n-1)、TFb(n-1)、TFc(n-1)； VSABOSP在车间a、b、c的完成时刻分别记为：TSa(n-1)、TSb(n-1)、TSc(n-1)。 第n辆机动车在车间a、b、c的检测耗时为Ta、Tb、Tc。

由假设3可知，对于FIFO，车间a的首个检测工位是整个算法的起始工位。根据3.3节步骤3可知，存在“车间a的首个检测工位已经完成某辆机动车的检测任务，但是该检测工位空转，等待下一个工位空闲”的情况。这样必然导致车间a完成n-1辆机动车的检测时刻延后，即车间a的完成时间加长。所以，当完成n-1辆机动车的检测任务时，TFa(n-1)与TSa(n-1)之间满足如下不等式

TFa(n-1)≥TSa(n-1)

(3)

同理

TFb(n-1)≥TSb(n-1)

(4)

TFc(n-1)≥TSc(n-1)

(5)

结合表1和式(3)～式(5)可得到：当完成n-1辆机动车的检测任务时，如果VSABOSP各车间的完成时刻为表1中的 (x,y,z)， 则FIFO各车间的完成时刻为在表1中的可能取值为 (x,y,z) 及其同一行右侧和同一列下方包围区域的所有组合。例如：VSABOSP各车间的完成时刻组合为 (0,0,0)， 则FIFO可以取表1中的任意情况。

VSABOSP完成第n辆机动车的结束时刻为

TS(n)=min{TSa(n-1),TSb(n-1),TSc(n-1)}+Ta+Tb+Tc

(6)

FIFO完成第n辆机动车的结束时刻为

TF(n)=TFa(n-1)+Ta+Tb+Tc

(7)

分情况讨论式(6)、式(7)的大小关系：

情况1：TSa(n-1)≥TSb(n-1)或者TSa(n-1)≥TSc(n-1)。

结合式(3)可得TS(n)与TF(n)的关系

TS(n)≤TSa(n-1)+Ta+Tb+Tc≤TFa(n-1)+Ta+Tb+Tc=TF(n)

(8)

情况2：TSa(n-1)

结合式(3)可得TS(n)与TF(n)的关系

TS(n)=TSa(n-1)+Ta+Tb+Tc≤TFa(n-1)+Ta+Tb+Tc=TF(n)

(9)

对比式(8)和式(9)可得：最坏情况下，VSABOSP与FIFO调度效率一样，其它情况下VSABOSP会表现的更高效。

4 仿真实验

对Vn辆机动车的检测任务，分别采用FIFO和VSABOSP进行模拟实验仿真，其中Vn的取值范围为：Vn={5,10,20,30,40,50,60,70,80,90,100}。 实验环境为Windows 10 专业版64 位操作系统，Intel®CoreTMi7-6800K CPU @ 3.40 GHz 处理器，16 GB RAM。使用JDK1.8.0_171编码实现。

4.1 VSABOSP伪代码

VSABOSP调度伪代码由VSABOSP主算法、testing子算法、findVehicleForWorkshop子算法3部分组成。其中，VSABOSP主算法用于协调各子算法之间的调度关系，控制程序起止；testing子算法模拟检测车间检测机动车；findVehicleForWorkshop子算法用于在满足1.2节约束条件的前提下，为各检测车间调度机动车。为了更好阐述算法流程，将调度过程中涉及到的对象进行定义。

4.1.1 对象定义

检测项目对象，定义如下：

Class Item {

String name; // 检测项目名称

int time; // 检测耗时 }

检测工位对象，定义如下：

Class Station {

int currTime; // 最后一辆机动车完成检测的时刻

boolean idle; // true： 空闲状态 (默认)； false： 繁忙状态

List items; // 可检项目列表

Vehicle veh; // 在该工位正在检测的机动车 }

机动车对象，定义如下：

Class Vehicle {

int currTime; // 上一个项目检测完毕时刻

boolean wait; // true： 等待状态 (默认)； false： 检测状态

boolean finish; // true： 完成检测； false： 未完成检测 (默认)

Map> itemMap; // 检测项目与工位映射关系 }

检测车间对象，定义如下：

Class Workshop {

List stations; // 车间包含的检测工位列表

boolean idle; // true：空闲状态 (默认)； false： 繁忙状 }

4.1.2 VSABOSP主算法

在机动车检测调度过程中，建立3个用于辅助程序调度的缓存队列：

等待队列：保存完成项目申请之后，开始检测之前的机动车集合。队列中，机动车按照项目申请完成时刻的先后顺序排列。简记为：waitQueue。

一级缓存：保存正在检测工位检测的机动车集合。队列中，机动车按照进入当前正在检测工位时刻的先后顺序排列。简记为：cache1。

二级缓存：保存一级缓存中完成检测任务，处于等待状态的机动车集合。队列中，机动车按照完成上一个检测任务的先后顺序排列。简记为：cache2。

VSABOSP主算法伪代码，如下所示：

VSABOSP主算法：

输入：waitQueue 等待队列， wsList 检测车间列表

(1)functionmain (waitQueue, wsList)

(2)cache1和cache2初始化为空

(3)while存在未检测完毕的机动车do

(4) 清除cache1中状态为finish的所有机动车

(5)foreachworkshop ∈ wsListdo

(6) 调用findVehicleForWorkshop子算法

(7) 调用testing子算法

(8)endfor

(9)endwhile

(10)endfunction

4.1.3 testing子算法

testing子算法：

输入：workshop检测车间

(1)functiontesting (workshop)

(2) vehicle ← 在车间首个工位检测的机动车

(3)ifvehicle != nullthen

(4)foreachstation∈ workshop.stationsdo

(5) items ← 获取vehicle在station工位的检测项目

(6)foreachitem∈ itemsdo// 模拟检测机动车的每个检测项目

(7) 更新station和vehicle的当前时间.curr-Time

(8)endfor

(9)ifvehicle完成所有检测任务then

(10) vehicle.finish ← true

(11)else

(12) vehicle.wait ← true

(13) 将vehicle添加到cache2

(14)endif

(15) 更新车间状态

(16) 工位状态更新为空闲

(17)endfor

(18)endif

(19)endfunction

4.1.4 findVehicleForWorkshop子算法

为检测车间调度机动车时，除了满足1.2节的约束条件，机动车还需要满足两个点要求：①机动车在检测车间有检测项目；②机动车处于等待状态。将满足上述要求的机动车记为：满足要求的机动车。由3.5节可知，检测车间的状态与该车间首个检测工位的状态保持一致。

在满足1.2节的约束条件下，实现VSABOSP，将机动车被调度的优先级[10]由高到低设置为：

cache1>cache2>waitQueue

findVehicleForWorkshop子算法伪代码，如下所示：

findVehicleForWorkshop子算法：

输入：workshop车间,cache1一级缓存, cache2二级缓存, waitQ等待队列

(1)functionfindVehicleForWorkshop(workshop, cache1, cache2, waitQ)

(2)while车间空闲do

(3) vehicle ← 从cache1选取满足要求的机动车

(4)ifvehicle存在then

(5) 将机动车调度到车间第一工位准备检测

(6) 更新车间、工位、机动车的检测状态

(7)return

(8)else

(9)ifcache2中存在满足条件的机动车then

(10) 将cache2中满足要求的机动车，添加到cache1

(11)continue

(12)else

(13)ifwaitQ中存在满足条件的机动车then

(14) 将waitQ中满足要求的机动车，添加到cache1

(15)continue

(16)else

(17)return

(18)endif

(19)endif

(20)endif

(21)endwhile

(22)endfunction

4.2 实验数据

参考国家在机动车检测领域的政策法规[11-14]，机动车检测主要分为3种检测线：安全性能检测线(以下简称：安检)、综合性能检测线(以下简称：综检)、环保尾气检测线(以下简称：环检)。通过政策解读发现：综检与安检，综检与环检的项目之间发生重合，例如：尾气检测既要在综检进行检测，又要在环检进行检测。抽取安检、综检、环检的公共检测项目，对比政策规定的项目检测最短时间与项目在工业实践中的检测耗时，将检测项目与检测耗时进行总结，见表2。

表2 检测项目检测耗时/min

4.3 实例分析

为了提高算法实用性，结合榆林、商洛、咸阳机动车检测站的布局，采用3个车间模拟，即环检车间、安检车间、综检车间。其中环检车间负责：尾气检测；安检车间依次负责：外廓尺寸、制动、前照灯、转向轮横向侧滑量的检测；综检车间依次负责：燃料消耗量、车速表误差、动力性、声级的检测。

对5辆机动车，针对表2中的检测项目，分别使用VSABOSP和FIFO进行调度。分别得到5辆机动车在各车间的调度过程，如图3、图4所示。

图3 FIFO算法

图4 VSABOSP

在VSABOSP调度过程中，机动车在检测工位、waitQueue队列、cache1队列和cache2队列中的变化情况，见表3。

4.4 仿真分析

首先，为Vn辆机动车申请表2中的所有检测项目，得到Vn辆机动车的检测任务，其中Vn={5,10,20,30,40,50,60,70,80,90}。 然后，将Vn辆机动车分别采用VSABO-SP 和FIFO进行调度，得到检测调度信息。最后，对检测调度信息进行对比分析，得到算法性能优劣对比相关图表，如表4、图5～图8所示。

其中，理论耗时指：Vn辆机动车理论上的检测耗时之和，即每辆机动车的检测耗时通过表2中项目检测耗时求和得到。调度结束时间指：从开始检测到完成Vn辆机动车检测调度任务之间的时间。空转时间指：检测过程中所有工位空转时间之和。平均调度时间指：在完成Vn辆机动车的检测调度任务后，所有车间结束检测时间之和与Vn之间的比值。利用率指：在完成Vn辆机动车的检测调度任务后，Vn辆机动车的理论耗时与所有检测工位运行时间总和之间的比值。

由表4可知，检测调度结束时间比理论耗时短，结合图3和图4，分析可得：同一时刻，有多辆机动车在多个检测工位上并发进行检测。相比于FIFO，VSABOSP将串行化转化为并行化执行。根据文献[15-17]的研究，并行化方法的效率要优于线性化方法，因此 VSABOSP的性能要高于FIFO。

表3 实例调度时刻/min

表4 算法仿真性能对比/min

为了更直观的对比VSABOSP和FIFO的性能差异，将表4数据绘制成图。图5是调度完成时刻对比图，图6是平均调度时间对比图，图7是检测工位总空闲时间对比图，图8是资源利用率对比图。

如图5所示，在相同调度任务的前提下，VSABOSP比FIFO调度完成时间更短。从侧面说明，在相同条件下，采用VSABOSP，检测机构每天可以完成更多机动车的检测任务，能够提升检测机构的检测能力。

图5 调度完成时刻对比

图6 平均调度时间对比

如图6所示，在相同调度任务的前提下，VSABOSP的平均调度时间远低于FIFO。表明，在相同条件下，VSABO-SP的检测效率更高，相同时间内，可以完成更多机动车的检测调度任务。

如图7所示，在相同调度任务的前提下，VSABOSP的工位空转时间远低于FIFO。表明，在相同条件下，采用 VSABOSP 检测工位空转时间更短，检测设备的利用率更高。

图7 工位空闲时间对比

图8 资源利用率对比

如图8所示，在相同调度任务的前提下，VSABOSP的资源利用率远高于FIFO。表明，在相同条件下，采用 VSABOSP 检测设备的资源利用率更高，减少了资源浪费现象。

5 结束语

针对当前机动车检测机构检测效率不高，车主等待时间过长的问题，基于全局工位优先原则，提出了一种基于全局工位优先的机动车检测调度算法(VSABOSP)，并对算法的时间复杂和空间复杂性进行了分析。然后，采用数学归纳法验证VSABOSP算法在最差情况下性能与FIFO一致，其余情况下要优于FIFO。最后，分别采用实例分析和仿真实验的方式对算法性能做进一步分析对比。

研究结果表明，相比于FIFO，VSABOSP，调度效率至少提升45%、工位空闲时间降低50%，资源利用率提升一倍，为机动车检测行业提供了调度优化方案。

在下一阶段，将对多检测车间多检测线情况下的机动车检测调度进行优化探索。