基于五维调度算法的并行设备车间调度方法

刘 琴， 陈 进

(江南大学 机械工程学院，江苏 无锡214122)

一般柔性数控加工车间，对提高设备利用率和及时完成给定的任务有很高的需求。在此需求下，应该将任务的每道工序都分配到合适的设备上加工。每个任务中的每道工序都可以在多台不同的设备上加工完成。设备可分为3 种［1］:有相同功能完全相同的平行设备，功能不同但加工时间相同的同类设备，以及功能和加工时间都不相同的不相关设备。

在有n 个任务、m 台设备的调度问题中，每个任务都有规定的工艺路线，每道工序都可以由一组具有相同或不同特点的设备来完成。其中最关键的问题就是为每道工序选择合适的设备，使加工成本最低。

目前，国内外就此研究方法主要有图论法、动态规划法、线性规划法以及遗传算法等。Gupta 等［2］将同类并行设备的车间调度问题纳入考虑范畴，并为最小最大延迟设计了2 种启发式算法，但并没有考虑到设备利用率问题。Kang 等［3］提出了一种用于处理包括返工概率、交货日期以及根据工艺路线设置时间的并行设备调度方法，但此方法是以假定每台设备上每个任务的返工概率是可以通过设备上的历史数据采集为基础的。Ozlen 等［4］则考虑到重新规划的问题，当一组任务已经分配给不相关的并行设备时，他们提出可以指数次算法来生成所需的有效解决方案，并使特定功能运算达到最优化，但其运算过程较为复杂，运算周期较长。

文中研究的主要问题是，在满足作业车间相关约束和规范的前提下，找到加工一组任务的最优序列。作业车间调度［5］主要需要解决的便是如何提高设备利用率问题，而车间作业调度应有实时性，如调度时间过长，会影响其运作效率。因此，文中所提算法着重于提高设备的利用率，减少调度时间，使车间作业成本达到最低化。

1 五维调度算法

1.1 五维调度算法介绍

问题为:在有同类并行设备的车间加工中，在保证订单按时完成的前提下，找出使设备利用率最高的一组加工序列，并加快运算速度。为此，提出五维调度算法(FDA)。FDA 中包含5 个独立的参数，分别代表工件的交货期与当前时间的差值、本工序之后本工件的剩余加工时间、本工序之后当前设备的剩余加工时间、本工件已排最晚时间与当前设备已排最晚时间之差的绝对值、当前工序的加工时间。

问题的条件为:某加工车间有m 台设备、n 个需要加工的任务，每个任务都有已定的工艺路线，且每道工序的预计工时都是确定的，并有z 台可用设备［6］。

问题的变量为:i 是任务编号，i = 1，2，…，n。j是设备编号，j = 1，2，…，m。g 是任务i 当前调度到工序的工序序号。则五维调度算法的5 个独立参数可描述为

式中，di指任务i 的计划交货期与当前时间的差值，差值越小，说明任务越紧急，则应优先排产;是任务i 根据其工艺路线，在第g 道工序后的所有工序加工所需的时间之和，即是指任务i的剩余需加工工时，任务的剩余工时越少，则越应优先安排加工，可减少车间任务堆积，并保证任务按时完成;Aj是所有需在设备j 上加工的工序工时总和是指在设备j 上已排工序的加工时间总和，其中Θ 是指在设备j 上已排的所有任务的集合，q 是指任务u 在设备j 加工的工序序号;(Aj－)指设备j 的剩余可加工时间，因为车间有同类并行设备，同一道工序有多台设备可供选择，所以设备剩余加工时间越短，越可在此设备上优先安排加工，可有效地提高设备利用率;yj*(－1)，i，g－1指任务i 在其g －1 道工序上已排的计划结束时间指设备j 已排的最晚计划结束时间;指两者之差的绝对值，该差值越小，任务加工越紧凑，可保证订单按时完成［7］;tj，i，g指任务i 在第g 道工序加工工时，加工工时越大，则越先排产，可提高设备利用率。

综上所述，最小化的前4 项及最大化的后1 项，构成了最小的评价指标，即V 值，其所属任务在所属设备上优先排产。

1.2 五维调度算法运算步骤

首先介绍五维调度算法运算步骤中用到的5 个矩阵(m 为设备总数，n 为任务总数):

tj，i，g:任务i 在第g 道工序上的加工时间，i = 1，2，…，n。t 为时间矩阵，g 是任务i 的工序序号。另外，tj，i，g= tc，i，g，即工序g 可在不同的设备上加工，且加工时间相同，j 和c 是设备编号，j ≠c。则T 矩阵为:Ts=(tj，i，s)m×n。

rj，i，s:根据工艺路线任务i 在设备j 上加工的工序序号，i = 1，2，…，n;j = 1，2，…，m。s 是任务i 可以在设备j 上加工的工序数。如果任务i 的第g 道工序以及第f 道工序都可以在设备j 上加工完成，设备j 在任务i 上就有2 个角色，则s = 1，2，rj，i，1= g，rj，i，2=f。假设每台设备在同一个任务中都可扮演z个不同的角色，也就是说，每台设备都可加工同一任务中的z 道工序，而且加工每道工序都有z 台设备可供选择。则R 矩阵为:Rs= (rj，i，s)m×n。

eg，i，s:任务i 在加工其第g 道工序可供选择的第s 台设备。很明显，R 和E 是一一对应，可以交换的。则E 矩阵为:Es= (eg，i，s)m×n。

xjig:任务i 的第g 道工序在设备j 上加工的计划开始时间，i = 1，2…，n;j = 1，2，…m。X 是一个三维的状态矩阵。g 是任务i 的工序序号。则状态矩阵，即X 矩阵为:Xs= (xg，i，s)m×n。

yjig:任务i 的第g 道工序在设备j 上加工的计划结束时间，i = 1，2，…，n;j = 1，2，…，m。Y 是一个三维的输出矩阵。则输出矩阵，即Y 矩阵为

五维调度算法的优化调度步骤:

1)准备T 矩阵、R 矩阵和E 矩阵。

2)搜索最低评价指标，其范围是任务i 从1 到n取值，工序序号g 从1 到m 取值，p(i)= g 记录当前任务排产到的位置。以上5 因素评价指标V 值越小，则代表越可优先加工。搜索最低评价指标有两个步骤:(1)从当前计算的工序所有可用设备中选择V值最小的设备，假设设备编号是j;(2)将Vj，i，g代入，与其它所有任务的V 值进行比较，选择V 值最小的任务，将其固定在当前加工位置上。在此道工序排完之后，p(i)= g +1。

3)计算在设备j 上任务的状态矩阵和输出矩阵:

4)继续从2)开始，直到所有的任务都完成排产。

2 计算实验

为了验证五维调度算法的有效性，设计并实施了一系列的计算实验。实验的目的是揭示不同的算法在相同条件基础上的相对表现和不同的结构公式。

实验平台是一个带有2 GHzCPU 和2 GB RAM的个人电脑，程序是用C ++ builder 来编程。工时t和工序顺序矩阵是从均匀离散时间中随机画出的［8］。

遗传算法(GA)是建立在生物进化模型上强大的搜索技术，已被许多用户应用于作业车间调度领域［9］，文中也使用这个方法来解决类似例子。其中，遗传算法的相关参数设置［10］如下:

群体大小= 50;终止进化代数= 100;交叉概率= 0.85;变异概率= 0.01。

文中做了3 组实验:第1 组设定任务数为10，设备数为10，平均每个任务的总工序数为10;第2 组设定任务数为50，设备数为25，平均每个任务的总工序数为25;第3 组任务数为100，设备数为50，平均每个任务的总工序数为50(见表1)。每组实验中的每道工序都有1 ～5 台设备可供选择，且每台设备每天的可利用时间都假设为24 h。每个实验结果都是5 次相同条件下实验得到结果的平均值，以保证结果的准备性。

表1 实验的级别及相关因素Tab.1 Level and related factors of Experiments

3 结果与讨论

通过比较计算时间及排产完成后的设备利用率来比较GA、FDA 两种算法的优化程度。

首先，比较两种算法计算时间的差异。如表2 所示，设备数为10、任务数为10 的条件下，GA 的计算时间为50 s，FDA 的计算时间为4 s;设备数为25、任务数为50 的条件下，GA 的计算时间为220 s，FDA的计算时间为35 s;设备数为50，任务数为100 的条件下，GA 的计算时间为450 s，FDA 的计算时间为110 s。显而易见，在计算时间上FDA 是优于GA 的。

在实际生产中，每天需要加工的任务数一般都大于100 个，因此计算时间会相对更长。而生产中，当然是不希望把过多时间花在做计划上，尤其是生产周期较短且容易有插单等状况的企业，如果用GA进行计算，时间冗长，会影响生产进度，显然是不切实际的。因此，在此方面FDA 有很大优势。

表2 实验计算时间对比Tab.2 Contrast of calculation time

然后，再从设备利用率角度来比较两种算法。由于数据较庞大，以10 × 10 为例计算设备利用率，其它两组实验的设备利用率通过甘特图［5］可以直观形象地显示出来。

图1 所示为10 ×10 实验下两种算法的甘特图对比。甘特图的横轴为时间轴，每一格代表1 h，竖轴为设备编号，图中深色部分代表有任务在加工，淡色部分代表无任务在加工。因此，通过观察图中深色部分占总图的比例，即可看出其设备利用率(设备利用率= 设备工作时间/设备可用时间)的大小(见表3)。

图1 10 ×10 甘特图对比Fig.1 Contrast of 10 ×10 gantt chart

表3 实验设备利用率对比Tab.3 Contrast of equipment utilization rate

图2，3 分别为50 ×25，100 ×50 的实验下两种算法的甘特图对比。

图2 50 ×25 甘特图对比Fig.2 Contrast of 50 ×25 gantt chart

图3 100 ×50 甘特图对比Fig.3 Contrast of 100 ×50 gantt chart

由表3 的计算结果以及3 幅甘特图的对比可以看出，FDA 所得到排程结果的设备利用率比GA 更优。在实际生产中，当然希望设备利用率更高一些，这样可以尽早完成所需加工的任务，并且插单情况发生时，可以及时应对。

4 结 语

文中描述了同类并行设备的一种新算法，举例证明了这种算法优于现有的GA。在设备数量从10到50、任务数量从10 到100 的调度问题上，通过评价两种算法的计算时间以及设备利用率，证明FDA的优化程度更高。实验结果表明，FDA 做生产调度可得出较优的排产结果，并且运算效率也有很大提高。

［1］CHENG T C E，CHEN Z L.Parallel-machine scheduling problems with earliness and tardiness penalties［J］.The Journal of the Operational Research Society，1994，45(6):685-695.

［2］Gupta J N D，Ruiz-Torres A J，Webster S.Minimizing maximum tardiness and number of tardy jobs on parallel machines subject to minimum flow-time［J］.The Journal of the Operational Research Society，2003，54(12):1263-1274.

［3］KANG Y H，KIM S S，SHIN H J. A dispatching algorithm for parallel machines with rework processes［J］. The Journal of the Operational Research Society，2009，61(1):144-155.

［4］Ozlen M，Azizoglu M. Rescheduling unrelated parallel machines with total flow time and total disruption cost criteria［J］. The Journal of the Operational Research Society，2011，62(1):152-164.

［5］Rojanasoonthon S，Bard J F，Reddy S D.Algorithms for parallel machine scheduling:a case study of the tracking and data relay satellite system［J］.The Journal of the Operational Research Society，2003，54(8):806-821.

［6］WANG C J，XI Y G. Performance analysis of active schedules in identical parallel machine［J］. Journal of Control Theory and Applications，2007，5(3):239-243.

［7］杨宏安，孙树栋，王荪馨，等.基于约束满足的Job Shop 调度算法研究［J］.计算机工程与应用，2003，39(31):36-371.

YANG Hongan，SUN Shudong，WANG Sunxin，et al. A Job Shop scheduling algorithm based on constraint satisfaction problem［J］.Computer Engineering and Applications，2003，39(31):36-37.(in Chinese)

［8］LIN B M T，JENG A A K. Parallel-machine batch scheduling to minimize the maximum lateness and the number of tardy jobs［J］.International Journal Production Economics，2004，91(2):121-134.

［9］王立平，曹立明.遗传算法—理论、应用与软件实现［M］.西安:西安交通大学出版社，2002.

［10］XONG H.Heuristic method for dynamic job shop scheduling problem with operation relativity［J］.Chinese Journal of Mechanical Engineering，2006，42(8):50-55.