板式家具高速自动分拣系统出库及打包调度策略

林 煊，陈庆新，毛 宁

(广东工业大学 广东省计算机集成制造重点实验室，广东 广州 510006)

0 引言

随着人们生活水平的逐步提高，个性化需求越来越旺盛，家具行业也开始朝着个性化和定制化的方向发展。与传统家具相比，定制家具板材的材料和规格多种多样，生产成本较高。因此，为节省原材料成本,定制家具生产商通常将多个客户的订单整合到一起统一下料，以最大限度地提高板材利用率。板材加工完成后，再将每位客户的家具板材从中分拣出来进行打包发货。上述过程虽然节省了原材料成本，但也造成后续分拣作业成本的上升。在此背景下，具有低错误率以及高效率的自动化分拣方式开始逐渐取代传统的手工分拣模式。

目前，分拣系统已广泛应用于医药、烟草、快递等行业的物流配送环节，而关于分拣系统问题的研究也越来越引起学者的重视。文献[1]以人工拣选系统为背景，考虑分拣货品重量对分拣顺序的影响，研究了一类具有出库优先顺序约束的订单排序问题，提出一种求解该问题的精确算法;文献[2]针对自动化立体仓库出入库调度问题，引入Petri网方法对问题进行建模，并以系统总体效益最优为目标，提出一种基于遗传算法的调度规则决策方法，解决自动化立体仓库的出入库调度规则优化的多约束性、多目标问题;文献[3]以双拣选区自动拣选系统为背景，提出一种虚拟视窗算法，通过提前订单开始分拣时间，以压缩货物之间的距离，从而节约分拣时长;文献[4-5]在文献[3]所提出的压缩合流分拣策略的基础上，研究了品项分配优化问题，提出一种启发式聚类算法进行求解。现有关于分拣系统调度策略的研究大多集中在人工拣选系统和自动仓储系统，在少部分关于自动分拣系统优化方法的研究中，主要围绕在品项分配问题，而鲜有关于自动分拣系统出入库调度策略的研究。因此，本文研究不仅填补了目前定制家具自动分拣系统出入库调度问题研究的空白，也丰富了现有自动分拣系统分拣调度策略的研究。

定制家具分拣作业可细分为条码识别、尺寸检测、入库暂存、出库4项作业。分拣出库的板件经由移载机合流以及线体运输，到达后方的打包机进行打包处理，出库作业的高效性和准确性将直接影响包装作业的开展。因此，本文研究对于提升板式家具自动分拣中出库及包装作业的整体效率具有重要的应用意义。

本文研究的自动分拣系统出库打包问题可抽象为一种带装配操作的三阶段混合流水车间问题。其中：第一阶段机械手出库和第二阶段移载机合流可表示为机器加工处理阶段；第三阶段打包机的打包作业类似装配作业将多块板件组装成一个包件。针对此类调度问题，已有部分学者进行了相关研究。文献[6]考虑每个阶段有多台同等并行机，将两机装配流水车间拓展为两阶段混流装配问题;文献[7]考虑工件的运输阶段，将两阶段的装配流水车间调度问题拓展为三阶段装配流水车间调度问题，在证明问题为NP难问题的同时，分析了问题的下界。多阶段装配车间调动问题是NP难题，在合理的时间内难以求得问题的最优解，因此能够快速求解问题近似解的启发式算法，目前正成为该领域研究的热点。对于两阶段问题，文献[8]以最小化最大完工时间和平均完工时间的加权和为优化目标，构造了模拟退火(Simulated Annealing, SA)算法、禁忌搜索(Taboo Search, TS)算法和蚁群优化(Ant Colony Optmization, ACO)算法3种有效求解该类问题的元启发式算法;文献[9]考虑与文献[8]相同的模型，提出一种融合变邻域搜索机制的离散粒子群优化(Discrete Particle Swarm Optimization, DPSO)算法，并实验证明了所提算法相较于SA算法和TS算法的优越性。对于三阶段问题，文献[10]以最小化最大完工时间和平均完工时间的加权和为目标，提出一种SA求解算法;此后，文献[11]在文献[10]所研究问题的基础上，又提出一种变邻域搜索(Variable Neighborhood Search, VNS)算法，实验表明，VNS算法的表现优于文献所提的SA算法，而SA算法在时间耗费上更有优势;文献[12]总结了目前有效求解三阶段装配车间调度问题的元启发式算法，通过融合变邻域搜索机制，提出了混合遗传算法(Hybrid Genetic Algorithm, HGA)、混合分布估计算法(Hybrid Estimation of Distribution Algorithms, HEDA)和混合差分进化算法(Hybrid Discrete Differential Evolution, HDDE)。现有关于启发式算法的研究主要集中在迭代寻优的元启发式算法，而本文针对出库打包调度问题的特殊性，将设计一种更为高效的构造类启发式算法。

不同于一般的多阶段装配流水车间问题，本文研究的出库打包调度问题中，板件除了在第一阶段有确定的处理机器外，还具有确定的先后包装顺序以及一定的运输时间。为了避免板件经由线体输送以及移载机合流后，到达打包机的顺序出错，从而影响包装作业的开展，应当控制同一个包装任务内的板件在第一阶段机器上的处理顺序。因此，第一阶段可表示为工件加工具有优先顺序约束以及工件加工具有指定机器的并行机调度问题。目前，针对此类问题的研究成果并不多，文献[13]研究了工件在第一阶段加工具有指定机器且第二阶段只有一台机器的两阶段流水车间问题，并证明了该问题为NP难问题;文献[14]证明了工序之间具有任意加工优先顺序约束，且工序所指派加工机器确定的两台平行机调度问题是NP难问题;文献[15]在文献[14]的基础上，考虑实际加工环境，研究了一种以最小化最大完工时间为目标，工件具有单位加工时间且工件加工具有链状优先顺序约束以及指定机器约束的两台并行机调度问题(U2-Chain问题)，并给出求解该问题的近似算法。

本文研究的定制家具出库打包调度问题是上述相关文献研究问题的结合和推广，创新点主要体现在以下3个方面：①在现有关于带装配操作的流水车间问题的研究中，对于加工阶段和装配阶段均有多台并行机组成的复杂系统的研究相对较少，本文研究的三阶段调度问题中每个阶段均有多台并行机；②本文不仅考虑了板件在工序间转移的运输时间，还考虑了板件运输时间对控制板件到达打包机先后顺序的影响；③大多数研究均是以最小化最大完工时间为优化目标，但是在实际加工环境中，考虑单个目标并不能保证系统整体性能的优化。本文在考虑尽可能短的时间内完成所有包装任务的同时，为减少板件在第一阶段货架的存储时长以及板件在包装工位等待的平均时长，以最大包装完工时间、最大出库完工时间以及板件在包装工位的总等待时间三者的和最小化作为问题的优化目标。

1 数学模型

1.1 问题描述

定制家具自动分拣系统的出库打包调度问题可抽象为一类三阶段流水作业排序问题，其中每阶段均由多台同等并行机构成。其与传统的混合装配流水车间调度问题之间主要存在以下3点差异：①在现有的装配流水车间问题研究中，很少考虑装配任务内工件的优先顺序约束，而在定制家具的包装环节中，根据已知的包内板件堆叠次序要求，包内板件的包装处理次序存在确定的优先约束关系，板件在出库后经由线体输送和合流移载机合流后的顺序需要满足此优先约束；②在实际的自动分拣系统布局中，处于不同分拣单元的分拣机与第二阶段合流移载机之间的运输距离可能存在差异，相较于少数考虑运输时间影响的装配车间问题，本文还考虑了距离的差异对合流顺序的影响；③传统的装配车间问题中每个装配任务的工件数相同，每个工件有指定的唯一加工机器，加工机器数量等于每个装配任务的工件数，而在出库打包问题中，每个包装任务的板件数量不尽相同，包内板件可暂存在任意分拣单元内，一台分拣机可能兼顾一个包装任务内多块板件的出库作业。

问题可简述为：假设有n个包装任务，每个任务Ji有Qi块板件，每块板件均需要先后经过出库A、移载B、包装C三道工序的处理，其中工序A只可以由板件所在分拣单元E内的唯一一台机械手处理，工序B可以在第二阶段任意一台机器进行处理，同一个包装任务的工序C需要在第三阶段任意相同的打包机上处理。板件在每道工序间处理需要经过线体转运，板件从工序A不同机器出发到达工序B机器所耗费的运输时间TA不同，而从工序B出发到达工序C机器的运输时间TB均相同。在第一阶段，因为板件存储的分拣单元确定已知，所以有确定的处理机器。在第三阶段，同一个任务内的板件处理具有一定的先后顺序约束，板件在经由线体运输到达包装工位的顺序必须满足此顺序约束，且只有当一个任务处理完毕才能处理下一个任务；一台机器在同一时间只能处理一块板件；工序在处理过程中遵循不可抢占原则。目标是最小化板件最大包装完工时间、最大出库完工时间以及总等待时间三者的总和。

1.2 数学模型

首先针对问题进行数学模型构建，模型决策变量描述如下：

Sik为板件i在第k阶段机器上的开工时间；

目标函数：

minf=α1×max(Ci3)+α2×max(Ci1)+

(1)

s.t.

∀i=1,2,…,n，∀k=1,2,3；

(2)

(3)

(4)

∀j=1,2,…,n，∀k=1,2,3；

(5)

∀j=1,2,…,n，∀k=1,2,3，∀m=1,2,…,mk;

(6)

∀k=1,2,3，∀m=1,2,…,mk；

(7)

(8)

Ximk=Xjmk，∀k=3，∀m=1,2,…,mk，

∀Oij=1；

(9)

∀i=1,2,…,n，∀j=1,2,…,n，∀k=3；

(10)

∀i=1,2,…,n，∀j=1,2,…,n，∀k=1,2,3；

(11)

Rik=Cik-1+Tk-1,k，∀i=1,2,…,n，∀k=2,3;

(12)

Sik≥Rik，∀i=1,2,…,n，∀k=1,2,3；

(13)

Cik=Sik+Pik，∀i=1,2,…,n，∀k=1,2,3。

(14)

其中：

i,j为板件编号；

n为板件总数；

k为处理阶段数；

α1，α2，1-α1-α2分别表示出库完工时间、包装完工时间和板件在包装工位等待时间在目标函数中所占权重；

Cik为k阶段板件i的完工时间；

Sik为k阶段板件i的开工时间；

Pik为k阶段板件i的处理时间；

Ximk表示k阶段板件i是否被指派到机器m上加工，如果是，则Ximk=1，否则Ximk=0；

mk为k阶段机器数量；

Uijmk表示k阶段的机器m上，板件j是否紧跟在板件i之后处理，如果是，则Uijmk=1，否则Uijmk=0；

Tkk′为k阶段到k′阶段的线体运输时间；

Rik为k阶段板件i的到达时间；

Oij表示板件i、j是否在同一个包件，且板件j紧跟在板件i之后处理，如果是，则Oij=1，否则Oij=0；

L为一个非常大的正数。

其中：式(2)表示在各阶段板件与自身不存在紧前紧后关系；式(3)和式(4)表示在各阶段板件最多先于或紧跟在另一块板件之后处理；式(5)表示在各阶段板件i与板件j之间仅存在唯一的紧前紧后关系；式(6)表示在各阶段如果板件被指派到某台机器上处理，则在这台机器上一定存在关于该块板件的紧前紧后关系；式(7)表示各阶段各台机器一次只能处理一块板件；式(8)表示各阶段板件只可以被指派到一台机器上处理；式(9)表示在第三阶段同一个包装任务的板件必须在同一台机器上处理；式(10)表示在第三阶段同一个包装任务的板件需要按照指定顺序处理；式(11)表示各阶段机器只有处理完一块板件后才能处理下一块；式(12)表示板件到达各阶段机器的时间等于其在上一阶段机器的完工时间加上运输时间，需要注意的是第一阶段到第二阶段的运输时间因第一阶段板件处理的机器不同而异；式(13)表示各阶段板件的开工时间不能早于其到达时间；式(14)表示各阶段板件的完工时间等于其开工时间加上处理时间。

2 启发式算法

对于NP难的排序调度问题，随着问题规模的增大，精确算法的计算负担呈指数级增长，不适用于求解工程问题。因此，可在合理时间内得到高质量解的启发式算法是目前研究的重点，主要集中在优先规则、分解算法以及元启发式方法。其中优先规则由于计算效率高且易于使用，在实际问题中应用最为广泛，但也具有短视的缺点，长期表现不佳；元启发式算法是独立于问题的技术，可以应用在非常广泛的问题上，但不能保证效率，求解效率相较于优先规则耗费明显；分解算法兼具上述两类算法的特点，在求解效率及求解效果上均有不错的保证。由于定制家具自动分拣系统对调度算法的实时性要求较高，基于出库打包调度问题，构造一种兼顾性能和效率的高效启发式算法是本文算法设计的重点和难点。

针对出库打包调度问题，本文构造一种启发式算法。关于多阶段流水车间调度问题的研究，文献[16-17]提出一种分阶段求解具有多阶段流水车间调度问题的思路;文献[18]针对带装配操作的三阶段混合流水车间调度问题，提出将问题分解为两个子问题求解，先确定装配阶段成品的装配顺序，再确定成品内各工件在加工阶段的加工顺序。本文基于上述思想，构建求解出库打包调度问题的近似算法。首先将复杂的出库打包调度问题按阶段分解为3个子问题：①确定板件在第三阶段机器的加工顺序(问题Ⅰ);②确定板件在第一阶段机器的开工时间(问题Ⅱ);③确定板件在第二阶段机器的开工时间(问题Ⅲ)。针对问题Ⅰ，采用最长加工时间优先规则(Longest Process Time，LPT)确定第一阶段各台机器Mi的加工序列Si；针对问题Ⅱ，将Si作为初始序列，通过改进的转移瓶颈算法(Modified Shifting Bottleneck Heuristic, MSBH)确定板件在第一阶段机器的开工时间Si；针对问题Ⅲ，根据问题Ⅱ确定的板件开工时间Si，计算得到板件序列Q1，通过算法FAM(first available machine)将Q1的板件安排到第二阶段的平行机上。由此得到求解出库打包调度问题的近似算法H*，下面详细介绍所分解的3个子问题以及相应的求解算法。

2.1 确定第三阶段各打包机板件处理顺序

此阶段问题可抽象为以最小化最大完工时间为优化目标的并行机调度问题，以三元组法表示为Pm||Cmax。对于求解Pm||Cmax问题的启发式算法很多，其中最常用的是启发式规则列表调度(List Scheduling，LS)算法以及LPT，本文拟采用LPT规则求解问题Ⅰ，算法步骤如下：

步骤1计算每个包装任务的板件总处理时间ti，将任务按处理时间ti递减排序，得包装任务序列bq。

步骤2在每个任务内按照规定的板件处理顺序对板件进行排列，得到更新后序列bq′。

步骤3每次从序列bq′中取第一个任务bq1，安排到当前总加工时长Sm最小的打包机m上，更新m的总加工时长Sm=Sm+Pbq1，更新m的包装序列Sm=Sm+bq1，更新序列bq′=bq′-bq1。如果bq′为空，得到各打包机板件包装序列Sm；否则，继续步骤3。

2.2 确定第一阶段板件出库开始时间

问题Ⅱ求解的关键在于考虑板件在各阶段机器的处理时间和机器间的运输时间，进而确定第一阶段各分拣单元内板件的出库开始时间，使得板件到达打包机的顺序符合问题Ⅰ确定的各打包机板件处理序列Sm。

通过前文分析，该类问题可抽象为工件加工具有链状优先约束且工件加工具有指定机器的并行机调度问题。参考文献[15]的求解思路，将子问题Ⅰ求得的板件序列Sm视为作业车间调度问题的加工任务Tm，板件序列的每一个板件Jk(Jk∈Sm)等同于加工任务Tm的每一道工序Ok(Ok∈Tm),加工工序Ok的机器即为板件Jk在第一阶段所指派的机器，因此问题Ⅱ可进一步抽象为一种工序具有重入特征的作业车间问题。对于作业车间问题，拟采用文献[19]所提的转移瓶颈法(Shifting Bottleneck Heuristic, SBH)作为问题Ⅱ的求解算法，算法步骤如下：

步骤1将调度问题以析取图表示。

步骤2将机器集合表示为M，将已完成调度的机器集合M0置空。

步骤3选择瓶颈机器，mp∈M-M0。

步骤4针对瓶颈机器mp，调用单机问题求解算法确定此台瓶颈机器上工序的加工顺序，在析取图上将方向错误的虚弧删除，将此台机器加入已调度的机器集合M0中。

步骤5当集合M0=M表示所有机器完成调度，算法停止，否则，转步骤3。

MSBH算法求解作业车间调度问题主要考虑3个关键点：①确定问题的析取图表示方式，即上述过程的步骤1；②确定单机问题的求解顺序，即上述过程的步骤3，文献[20]通过实验验证了TML(total machine load)规则用于确定瓶颈机器的优越性，因此本文选择总处理时间最大的机器作为瓶颈机器；③确定单机问题的求解算法，即步骤4确定瓶颈机器上工序的加工顺序。下面分别对步骤1的表示方法和步骤4的求解方法进行说明。

2.2.1 确定析取图表示方式

假设经过LPT规则算法确定了第三阶段3台打包机的板件包装序列，分别为：{1，2，3}、{4，5，6}、{7，8，9}，其中{1，5，7}、{2，4，6，8}、{3，9}分别存储在同一分拣单元，每个包装序列可抽象表示成车间调度问题中的一个工件，每块板件为工件中的一道工序。析取图如图1所示，每一点表示一道工序，图中最长路径表示调度问题的最大完工时间。图1中实线弧的方向表示同一个工件上工序间加工的先后顺序，虚线弧的方向表示同一机器上的工序在此机器上加工的先后顺序。问题的求解就是删减工序间多余的虚线弧，使得工序间仅存在确定方向的单向虚弧，即确定机器上工序加工的先后顺序，使得析取图的最长路径的距离最小。

为尽可能减少板件在打包机的等待时间，根据相邻两道工序所指派的机器相同与否，确定实线弧相邻两点间的距离为

dij=

(15)

式中：Ti,k,p表示板件i由阶段k机器到阶段p的运输时间;M表示一个接近0的实数。

对于同一个工件在同一机器处理的不相邻且间隔最短的两道工序也存在一个开工时间的约束关系，如图1中点4和点6间的距离和虚线弧相邻两点间的距离均可由式(16)确定。

dij=Pi1。

(16)

式中：dij表示点i指向点j的距离,即出库开始时间间隔；Pik表示板件i在k阶段机器的处理时间。

2.2.2 单机问题求解算法

SBH算法将复杂的作业车间调度问题分解为若干个以最小化最大拖期时间为目标、工序具有到达时间和交货期时间的单机调度问题进行求解，三元组法表示为1||r||Lmax。工序的到达时间rn和交货期时间dn分别为：

rik=L(0,ik)，

(17)

dik=L(0,n)-L(ik,n)+Pik。

(18)

其中：ik表示工序;L(p,q)表示p、q两点在析取图DG上的最长距离；0、n分别为析取图初始顶点和终点；Pik为加工时间。

针对1||r||Lmax问题，文献[21]已验证最早交货期(Earliest Due Date，EDD)优先规则是求解问题的有效算法。本文拟采用基于EDD规则的最早交货期松弛(Earliest Due Date Slack, EDDS)算法作为单机问题的求解算法，算法步骤如下(其中的工序指代本文问题中的板件)：

步骤2计算各工序的到达时间ri，交货期时间di。

步骤3判断集合Ou是否为空，如果是，则执行步骤7；否则执行步骤4。

步骤7调度结束。

2.3 确定板件在第二阶段移载机的开工时间

此阶段问题可表示为以最小化最大完工时间为优化目标，工件带到达时间的并行机调度问题，三元组法表示为Pm||Ri||Cmax。求解Pm||Ri||Cmax问题的启发式算法有很多种，Panwalker等[22]归纳了8个基本原则，其中研究最多的是列表算法(List Scheduling,LS)。关于列表算法，Graham[23]提出了FAM和LBM(last busy machine)两种特殊算法。FAM算法基本思路是：已知一个工件序列S，每次始终选择序列S的第一个未调度工件到使其能最早开工的机器上；LBM算法的基本思想则是：每次始终选择序列S的最后一个未调度工件到使其最晚开工的机器上。本文拟采用FAM算法求解该子问题，算法步骤如下：

步骤1根据算式Ri,2=Si,1+Pi,1+T1,i,2,计算板件到达第二阶段机器的时间，其中Si,1为子问题Ⅱ确定的板件开始时间，Pi,1为板件在第一阶段的处理时间，Ti,1,2为板件在两阶段机器间的运输时间。

步骤2板件按照Ri,2不减排序，得到序列Q1。

步骤3每次选择序列Q1的第一个未调度板件，安排到使其能最早开工的机器上，直到序Q1内的板件全部排完。

3 算例仿真及结果分析

3.1 算例设计

由于本文研究的问题并非一类经典调度问题，在现有文献中难以找到针对本类调度问题的测试数据集。因此，拟借鉴文献[24]给出的调度规则评估模拟算例的生成方法产生本文的测试数据集，该方法采用裂区试验的设计方法进行仿真实验。结合本文问题研究的特点，总结出问题的主要因素为板件规模大小S，其中包括包件个数g和包内板件个数n两个主要参数。包件个数g有10、30、50三种规模；包内板件数量n从区间[1,15]的离散分布均匀产生，即板件规模有小、中、大3个水平。此外，包内板件分散度D、各阶段机器数M、目标函数权值W以及求解问题的调度算法Al是影响问题求解的关键因素，作为本次裂区试验的二级因素。根据同一个包内板件在分拣单元的分布情况，包内板件分散度分为低分散度与高分散度两个水平，低分散度表示包内板件均位于同一个分拣单元，高分散度表示包内板件按照堆叠顺序间隔分布于互不相同的分拣单元。例如有3个分拣单元，板件1、2、3、4均同属于一个包件，按照高离散度分布，板件1、2、3、4将分别存储于单元1、2、3、1。此外，机器规模包含小，中，大3个规模，分别为(2,1,4)，(3,2,6)，(5,3,9)，其中数字分别表示第一、二、三阶段机器数量，板件在3个阶段机器的处理时间t分别从区间为[9,15]、[1,5]、[2,25]的均匀分布中产生。目标函数权值共有[0.2,0.7,0.1]、[0.7,0.2,0.1]、[0.4,0.5,0.1]三组，第一、二、三位数分别表示出库完工时间、包装完工时间、板件在包装工位等待时间在目标函数中的权重。板件在第一和第二阶段，第二和第三阶段间的运输时间分别从区间[5,15]、[5,10]的均匀分布中随机产生。

裂区试验选取的调度算法，除了本文所提出的H*调度算法，基于文献[25]所提的组合多种简单调度规则构成组合规则求解调度问题的思路，结合目前几种以最小化最大完工时间为优化目标的有效调度规则包括加工开始时间最早优先(Earliest Start Time，EST)、LPT、Palmer、Gupta、剩余加工时间最短优先(Most Work Remaining，MWKR)，提出EST-LPT、ECT-LPT、EST-Palmer、EST-Gupata、MWKR-LPT 5种组合启发式算法，其中EST规则解决机械手出库调度问题，LPT规则解决包装调度问题，Palmer、Gupta规则都是求解经典flow-shop问题的有效算法，为适应本问题的求解，需要将每个阶段的多台机器虚拟成一台机器。此外，为进一步验证所构造算法的有效性，重新实现文献[9-10，12]所提的有效求解装配流水车间问题的5种元启发式算法作为对比算法，加入包括变邻域搜索机制的HGA、HEDA、HDDE算法和混合离散粒子群算法(Hybrid discrete PSO, HPSO)以及SA算法。为公平比较5种元启发式算法的性能，基于文献[12]的思想，设置算法的最大CPU运行时间(ρ×nms，n为板件数，ρ取100、300、500),设置3种时长的终止条件，以比较元启发式算法在不同运行时间下的性能，而在与其余启发式算法的比较中只取ρ=500，即迭代次数最大的结果。至此，试验共包含5个影响因子，其中问题规模S为试验唯一的主因素，具有3个水平；二级因素共4个，分别为包内板件分散度D，具有2个水平；机器规模M，具有3个水平；目标函数权值W，具有3个水平；求解算法Al，具有13个水平。最后，为了进行更为全面的分析，实验将重复10次，即每种因素水平组合的问题将重复10次。因此，本次试验共需求解7 020个问题实例。

3.2 仿真结果及分析

所有问题的求解算法已在MATLAB 2016b仿真软件编程实现，并在中央处理器为Intel Corei32.42 GHZ，内存4 GB的计算机上进行仿真试验。为了比对H*算法与最优解间的偏差，采用IBM公司的数学规划优化软件CPLEX对数学模型进行求解。由于CPLEX内置的分支定界算法在大规模问题上求解耗时过长，只选择7 020个算例中机器规模为(2,1,4)，板件个数在20～30块的小规模算例进行对比。如表1所示为各板件数下启发式算法与精确算法求得结果的平均值比对，ARPD表示近似解与最优解的相对偏差百分比RPD的平均值。结果显示，H*算法的ARPD均在3%以下。

表1 小规模算例求解结果与最优解偏差

试验设计采用IBM公司的SPSS统计软件，首先对所有调度算法求得的7 020个问题实例的结果进行正态性检验，在验证数据满足正态分布后，采用变异系数分析方法(ANalysis of VAriance, ANOVA)对结果进行显著性分析。限于篇幅，省略ANOVA分析的详细结果。结果显示，主因素以及所有二级因素在显著水平5%上P值均小于0.000 1，达到极显著标准。为了分析不同算法的性能差异，选择包含算法因素Al在内的最高阶交互作用显著的因素进行进一步的简单效应分析。结果显示，算法、板件数、分散度的三因素交互效应(Al×S×D)以及算法、机器规模、分散度的三因素交互效应(Al×M×D)最为显著。

表2所示为不同板件规模以及分散度下算法的两两比较，表3所示为不同板件规模以及机器规模下算法的两两比较。限于篇幅，只列出其他算法与H*算法的比较，为方便表示，小于0.001的P值以0值取代，并将P值小于0.05的结果，即差异显著的结果标注为“*”。从表2中可以看出，在与简单组合规则的比较中，小规模高分散度下H*算法的表现与EST-LPT、EST-Palmer、MWKR-LPT三种调度规则的差异不显著，在其余板件规模以及分散度下，H*算法的表现要显著优于其余7种组合规则算法。在与元启发式算法的比较中，小规模任意分散度下H*算法的表现与5种元启发式算法差异不显著;中等规模低分散度下H*算法的表现显著劣于SA算法，与其余4种元启发式算法差异不显著;中等规模高分散度下H*算法的表现与SA算法差异不显著，而显著优于其余4种元启发式算法;大规模低分散度下H*算法的表现显著劣于SA算法，显著优于HGA和HDE算法，与HPSO和HEDA算法差异不显著;高分散度下H*算法的表现与SA算法差异不显著，而显著优于其余算法。由表3可以看出，在与简单组合规则的比较中，任意机器规模以及分散度下H*算法表现显著优于所有组合规则算法。在与元启发式算法的比较中，小、中等机器规模低分散度下H*算法表现显著差于SA算法，与其余元启发式算法差异不显著;大机器规模低分散度下与所有元启发式算法差异不显著;任意机器规模高分散度下H*算法表现与SA算法差异不显著，而显著优于其余元启发式算法。

表2 Al×S×D简单效应分析结果

表3 Al×M×D简单效应分析结果

为直观比较算法间的偏差，以每个实例下不同算法所求得的最佳解作为实例的最优值，计算7 020个实例下的RPD值，根据Al×S×D、Al×M×D的维度汇总计算平均相对偏差百分比ARPD。结果如图2和图3所示。在任意板件规模和机器规模的低分散度下，组合规则的平均偏差ARPD远高于元启发式算法和H*算法。而在高分散度下，随着板件规模的增大和机器规模的减小，组合规则的偏差甚至低于除SA算法之外的元启发式算法。在所有参数组合下H*算法的ARPD均远小于组合规则算法，接近元启发式算法的平均偏差，甚至低于除SA算法之外的其余元启发式算法的平均偏差，在低分散度下与求解效果最好的SA算法偏差在7%左右。而在高分散度下，随着问题规模的增大，H*算法的ARPD趋近于0。

为进一步验证算法在求解不同规模问题上的有效性，从时间耗费上进行调度算法的比较。表4给出了每个调度规则在不同规模板件数量和机器数量下的中央处理器平均运行时间。结果显示，所有调度规则的CPU运行时间均随着板件数规模的增大而上升，其中H*调度算法比其他组合规则算法运行时间长，但都是在可接受的范围内。此外，从表4中还可以发现，随着机器规模的增大，所有算法的运行时间呈下降趋势。考虑不同元启发式算法的收敛速度存在差异，为公平对比不同元启发式算法的求解性能，统一对不同元启发式算法设置一个相同的最大CPU运行时间，作为元启发式算法的运行停止准则。图4所示为不同分散度的3种运行时长下，元启发式算法的平均偏差ARPD，虚线表示H*算法的ARPD值。可以看出，随着运行时间上升，SA算法偏差变化不大，基本收敛至局部最优解，而其余元启发式算法依然还有提升空间。另外，在低分散度下，当ρ≤300，即运行时间小于300nms时，H*算法的ARPD均小于HGA、HDE、HEDA、HPSO算法，随着运行时间上升为ρ=500，HEDA、HPSO的ARPD才低于H*算法。在高分散度下，当ρ=100时，H*算法的ARPD值与SA算法相近，即使在最大运行时长ρ=500，其ARPD依然小于HGA、HDE、HEDA、HPSO算法的ARPD。

表4 启发式算法的实例平均运行时间

综合以上分析，本文所提H*算法在求解的效果上明显好于其余调度规则，接近甚至优于元启发式算法求解效果，且相较于迭代寻优的元启发式算法，随着任务数量的增加,H*算法的运行时间均在可接受范围之内，即使面对大规模问题，也能在足够短的时间内得到高质量解，满足出库打包调度实时求解的要求，是所研究的出库打包调度问题的一种有效求解算法。

4 结束语

本文将定制家具自动分拣作业中的出库及包装作业抽象为一类考虑板件在相邻两阶段机器间具有一定运输时间，且板件处理具有优先顺序约束及机器约束的三阶段柔性装配流水车间调度问题，并建立了相应的数学模型。

针对本文研究的数学模型，构造了一种求解该类问题的启发式算法H*。基于裂区试验设计的思想设计了该类问题的仿真算例，并与另外构造的7种组合规则算法以及5种元启发式算法进行性能比较。算例的仿真及结果分析表明了H*算法对于求解所研究的出库打包调度问题的有效性和优越性。

本文研究的出库打包调度问题中，出库阶段的加工机器(即机械手)不考虑随机事件干扰，但在实际分拣作业中，可能存在单个机械手需要处理入库及出库两类任务的情况。因为机械手需要兼顾入库任务，分拣机械手的可出库时间具有不确定性，所以考虑第一阶段机械手状态不确定性的动态调度规则将是下一步研究工作的重点。