作业车间环境下的采购生产配送联合调度模型

张维存 高蕊 张曼

摘 要：针对生产配送联合调度（IPDS）模型较少考虑复杂生产环境以及采购环节的问题，建立了在作业车间环境下，以最小化订单完成时间为目标的采购生产配送联合调度（IPPDS）模型，并采用改进的动态人工蜂群（DABC）算法进行求解。根据IPPDS问题的特征，首先，采用二维实数矩阵的编码方式，实现任务（加工与运输）與资源（设备与车辆）的匹配关系;其次，采用基于工艺过程的解码方式，并在解码过程中针对不同任务设计了满足约束条件的方法，来保证解码方案的可行性;最后，在算法过程中设计了引领蜂与跟随蜂的动态协调机制和局部启发式信息。通过实验给出DABC适当的参数区间，对比实验结果表明， IPPDS策略相较于分段调度和IPDS策略，调度时间分别缩短了35.59%和30.95%;DABC相较于人工蜂群（ABC）算法求解效果平均提升了2.54%，相对于改进的遗传算法（AGA）求解效果平均提升了6.99%。因此，IPPDS策略能更快速地满足客户需求，而DABC算法既减少需设置的参数，又具有良好的探索和开发能力。

关键词：作业车间调度;车辆调度;联合调度;车辆共用;人工蜂群算法

中图分类号：TP301.6

文献标志码：A

Procurementproductiondistribution joint scheduling model in job shop environment

ZHANG Weicun*， GAO Rui， ZHANG Man

School of Economics and Management， Hebei University of Technology， Tianjin 300401， China

Abstract：

Aiming at the issue that the Integrated Production and Distribution Scheduling （IPDS） model rarely considers the complex production environment and procurement， the model of Integrated Purchase Production and Distribution Scheduling （IPPDS） with minimizing the order completion time in the job shop environment as target was established and the improved Dynamic Artificial Bee Colony （DABC） algorithm was used to solve the model. Based on characteristics of IPPDS， firstly， to realize the matching relationship between task （processing and transportation） and resource （equipment and vehicle）， a coding method of twodimensional real number matrix was adopted. Secondly， the decoding method based on the process was adopted， and the method to satisfy the constraints for different tasks were designed in the decoding process to ensure the feasibility of the decoding method. Finally， the dynamic coordination mechanism and local heuristic information of leading and following bees were designed in the process of the algorithm. Appropriate parameter intervals of DABC were obtained by experiments， and the experimental results show that： compared with piecewise scheduling and IPDS， IPPDS strategy has the scheduling time reduced by 35.59% and 30.95% respectively. DABC algorithm has the solution effect averagely improved by 2.54% compared with Artificial Bee Colony （ABC） algorithm， and averagely improved by 6.99% compared to the Adapted Genetic Algorithm （AGA）. Therefore， IPPDS strategy can meet customer requirements more quickly， and DABC algorithm not only reduces the parameters to be set， but also has good exploration and development ability.

Key words：

job shop scheduling; vehicle scheduling; joint scheduling; vehicle sharing; Artificial Bee Colony （ABC） algorithm

0 引言

随着经济的快速发展和物质产品的多样化，如何高效满足客户个性化需求，提高企业在市场竞争中的信誉度和竞争力成为学术界和企业界关注的问题。从运作层面，将生产和配送进行联合调度（Integrated Production and Distribution Scheduling， IPDS）为解决上述问题提供了一种有效的探索[1]。

目前，对IPDS问题的研究主要针对较为简单的配送方式和生产环境： 李凯等[2]研究了直接配送的IPDS问题，时间窗等约束条件只有在简单生产环境下才会考虑[3];刘玲等[4]、Li等[5]研究了单机情形的生产与配送联合调度问题; Joo等[6]、Jiang等[7]研究了并行机情形的生产与配送联合调度问题。也有学者将IPDS问题范围进行拓展，从计划层面对由供应商、生产商、配送中心组成的多级供应链进行建模和分析。Taxakis等[8]以供应商的选择、设施（工厂、配送中心、零售商等）数量和位置，分销策略为变量，建立了一个多产品多阶段的单周期供应链网络问题模型，并用遗传算法进行求解;Jamili等[9]以配送时间及成本为目标，建立了采购生产配送三阶段物流调度模型。在IPDS的实践中应用方面，吴瑶等[10]为提高按订单生产模式下易腐品的生产配送效率，构建了以总配送成本最小和交付产品新鲜度最大为目标的模型，设计了基于双子串编码的非支配排序遗传算法进行求解; Kergosien等[11]以交付延迟时间最小为目标，研究了化疗制剂袋的IPDS问题; Ensafian等[12]构建了血小板供应链的采购生产配送鲁棒优化模型; Fu等[13]以金属包装行业为背景建立了具有时间窗约束的IPDS模型。

由于IPDS问题的复杂性，很多学者研究了其求解策略和求解方法。首先，其求解策略可归纳为分解和集成两种。分解策略就是先分别求解生产排程和车辆调度问题各自的可行方案，再将两者方案进行整合以满足求解要求和约束条件。而集成策略就是针对生产排程和车辆调度建立统一的求解方案或模型，同时求出满足各自问题特征的可行解。Viergutz等[3]指出：集成化策略的求解效果，特别是对于规模更大的测例，好于分解策略。其次，由于精确算法，如分支定界算法，只在少数的单机生产环境下的小规范测例情形表现良好[14]，因此IPDS求解方法更多采用启发式或元启发式算法。如改进的蚁群算法[15]、改进的遗传算法[16]、文化基因算法[17]、迭代局部搜索[3]等。人工蜂群（Artificial Bee Colony， ABC）算法由于算法結构简单，对解空间的搜索和开发能力强，收敛速度快，其改进算法已成功应用于生产调度问题[18]，但未见其应用于IPDS的求解。

本文将IPDS拓展为采购生产配送联合调度（Integrated Purchase Production and Distribution Scheduling， IPPDS）问题，并从运作层面在作业车间生产环境下对该问题进行建模。根据IPPDS问题特点，采用集成的求解策略利用改进的动态人工蜂群（Dynamic Artificial Bee Colony， DABC）算法寻求该问题可行、高效的求解方法，为该问题在更复杂生产环境下的应用提供方法支持。

1 问题描述以及数学模型

1.1 问题描述

本文研究一类由J个供应商、单个生产商和I个客户构成的IPPDS问题（如图1所示），并设供应商提供的原料及客户订购的产品各不相同。生产商期初接收到客户下达的订单Di（i=1，2，…，I），订单Di需要成品i的数量为qi。生产商接收订单后需从供应商j（j=1，2，…，J）进行原料采购，每种原料又可以生产多种产品。生产商采用作业车间的生产方式，即I种产品在G台设备上加工，每种产品有其自身的加工路径，且各工序加工时间已知。成品产出后，若有可用车辆，则将成品配送给客户，若无可用车辆，则暂放入成品库等待配送。生产商有K辆容量Vk（k=1，2，…，K）的车辆，所有车辆既可运输原料，又可运输成品。求解目标是选择物料的运输车辆，安排运输顺序，并确定产品投产及在各设备上的加工顺序，使所有客户订单执行时间（生产和运输时间）最小。

假设条件：1）原料和成品库存量期初为0，且产能和库存量无限;2）车辆型号、数量是确定的;3）生产准备时间、成品装卸时间忽略不计;4）从0时刻开始运输物料;5）忽略运输时的交通状态及设备故障等;6）同类型成品采用整批方式生成。

1.2 数学模型

参数说明 i（i=1，2，…，I）为成品编号; j（j=1，2，…，J）为原料编号;c（c=1，2，…，Ii）为工序编号;m（m=1，2，…，G）为设备编号;z（z=1，2，…，I，I+1，…，I+J）为物料统一编号;qi为客户对成品i的需求量;uij为成品i对原料j的单位消耗量;k（k=1，2，…，K）为车辆编号;tkz为车辆k运输物料z的往返时间;ticm为产品i第c道工序在设备m上的加工时间;Vk为车辆k的容量。

变量说明 a为运输次序编号，a=1，2，…，A（A为任意大的自然数）;tSicm为产品i第c道工序在设备m上的开工时间;tEicm为产品i第c道工序在设备m上的完工时间;tSkaz为第a次由车辆k运输物料z的开始时间;tEkaz为第a次由车辆k运输物料z的结束时间;Qkaz为第a次车辆k运输物料z的运输量。

决策变量 αi为若安排产品i投产，其值为1，否则为0。βi′im为若设备m上产品i′紧前于产品i生产，则其值为1，否则为0。δz′zk为若车辆k运输物料z′紧前于物料z，则其值为1，否则为0。ηkaz为若安排车辆k在第a次运输物料z，其值为1，否则为0。

目标函数

min（max{tEkaz}）（1）

约束条件：

qi=∑Aa=1∑Kk=1ηkai·Qkai（2）

∑Ii=1αi·uij·qi=∑Aa=1∑Kk=1ηkaj·Qkaj; j=1，2，…，J（3）

∑Ii=1αi=I（4）

tSicm=max{tEi（c-1）m′， βi′im·tEi′cm}（5）

tEicm=tSicm+ticm（6）

tEkaz=tSkaz+ηkaz·tkaz（7）

Qkaz≤Vk（8）

∑Kk=1ηkaj·Qkaj-∑Ii=1αi·qi·uij≥0; tEkaj≤tSi1m（9）

tSkai≥tEiIim（10）

tSkaz≥δz′zk·tEkaz′（11）

式（1）为目标函数，表示所有订单配送完成时间最大值的最小化;式（2）表示对成品i的配送量等于其订单需求量;式（3）表示原料j的运输总量等于产品投产对该原料的需求量之和;式（4）表示所有的成品需求均进行的投产;式（5）表示工序开工时间取其上序完工时间和本工序设备上紧前工序完工时间中两者的最大值;式（6）、（7）表示加工和运输任务的结束时间等于其开始时间加上任务执行时间，也表示任务执行过程不能中断;式（8）表示第a次运输量不大于该车容量;式（9）表示在产品i投产时，原料j的累计运输量大于投產i对其需求量，即原料不能缺货或断流;式（10）表示成品i配送开始时间不早于其产出时间：式（11）表示车辆k的第a次运输开始时间不能早于其紧前运输任务的结束时间。

2 问题及求解算法分析

IPPDS问题的复杂性体现在：1）不同于作业车间调度问题（Job shop Scheduling Problem，JSP）和车辆调度问题（Vehicle Routing Problem，VRP）均假定需完成任务在期初是可执行，IPPDS中生产环节和配送环节需完成任务因采购和生产环节的调度结果不同而异，可执行时刻未知;2）不同于VRP问题中的车辆资源是已知和确定的，IPPDS问题中采购和配送环节的车辆可用性均受对方调度结果影响，因而车辆的可用性是未知和变化的。所以，IPPDS问题的复杂性高于JSP和VRP，也强于将采购、生产、配送问题进行两两联合调度的问题。

进一步分析，IPPDS问题的实质仍是将车辆和设备资源在运输和加工任务间分配的资源配置问题，且在配置过程中，需要满足工艺约束、资源独占约束、数量约束和时间约束。但相较于JSP和VRP问题，IPPDS不仅对资源和任务方面进行了拓展，更提高约束条件复杂性。如工艺约束不仅体现在生产环节加工任务在设备间的物流关系（式（5）），也体现为采购生产配送的整体物流关系（式（9）、（10））;资源独占约束既体现在产品加工对设备资源的独占性（式（5）），也体现为运输任务对车辆资源的独占性（式（11））;数量约束体现在订单需求量对配送量（式（2））、配送量对生产量（式（4））、生产原料需求量对采购量（式（3））及资源量（式（8））的约束;时间约束既体现在加工环节（式（5），（6）），也体现在运输环节（式（7）、（10）、（11））。

根据IPPDS问题特点，设计其求解思路是：1）基于资源任务匹配的权值矩阵（见3.1节）实现资源在任务间的配置，是求解问题的基础;2）基于工艺过程，依据权值矩阵，解码出满足约束条件的可行调度方案是求解问题的关键;3）利用改进的动态人工蜂群算法（DABC）实现高效、更优的求解是求解方法可行的重要保证。

具体而言（如图2所示），在求解IPPDS问题时，基于工艺过程，采用二维矩阵编码方式实现资源与任务的匹配;通过解码过程在满足约束下选择运输任务的车辆，确定运输次序，确定产品投产次序及各设备上加工次序，计算任务开始和结束时间;通过对人工蜂群算法中引领蜂与跟随蜂协调机制和解码过程的启发式信息设计实现算法的高效、更优求解。

3 改进的人工蜂群算法

为适应IPPDS问题的求解特征，本文从算法编码、解码、初始权值的取值方式、启发式信息和算法过程几个方面对基本人工蜂群算法进行改进。下面分别对改进具体情况进行介绍。

3.1 编码设计

为实现资源（车辆和设备）与任务（采购、加工和配送）的匹配关系，采用二维实数矩阵编码方式。首先，将加工任务与运输任务统一编码（如式（12）所示），其中j表示原料编号，c表示工序编号，i表示成品编号; 再将资源统一编码，其中k表示车辆编号，m表示设备编号;其次，矩阵中的实数元素值表示任务与资源对应的优先权值，权值元素所在的行对应任务号，列对应执行任务的资源号;最后，通过比较权值的大小，并选择权值最大者对应的资源执行相应的任务，可以实现资源与任务的匹配顺序。

Y=

Pe（1，1）Pe（1，2）…Pe（1，k）00…0

Pe（2，1）Pe（2，2）…Pe（2，k）00…0

Pe（j，1）Pe（j，2）…Pe（j，k）00…0

00…0Pe（i+1，k+1）Pe（i+1，k+2）…Pe（i+1，k+m）

00…0Pe（i+2，k+1）Pe（i+2，k+2）…Pe（i+2，k+m）

00…0Pe（i+c，k+1）Pe（i+c，k+2）…Pe（i+c，k+m）

Pe（j+c+1，1）Pe（j+c+1，2）…Pe（j+c+1，k）00…0

Pe（j+c+2，1）Pe（j+c+2，2）…Pe（j+c+2，k）00…0

Pe（j+c+i，1）Pe（j+c+i，2）…Pe（j+c+i，k）00…0

（12）

3.2 解码过程

解码过程依据资源与任务的优先权值，在满足约束的条件下，安排发车次序、产品投产次序和加工次序，并确定运输的开始时间tSkaz和结束时间tEkaz，确定各工序的开始加工时间tSicm及结束时间tEicm。输入产品需求量qi，运输时间tkz等相关参数，设当前时刻t及前时刻t′为0，即t=t′=0，初始原料和产品库存都为0，所有资源都为可用。进入如下解码过程：

步骤1 更新任务和资源的状态。

若车辆k被占用，且车辆的运输结束时间tEkaz小于当前时刻t，对车辆k进行卸载。若卸载的是原料j，记录此次原料j的运输量Qkaj，增加原料j被车辆k运输的次数vjk，以及此次原料入库的时间tvjkj为tEkaz，并根据式（13）增加相应原料库存量Sj，车辆k变为可用;若卸载的是成品i，增加成品i被车辆k运输的次数vik，并根据式（14）更新已完成的订单配送量hi，更新车辆k的状态变为可用。

Sj=Sj+Qkaj（13）

hi=hi+Qkai（14）

若设备m被占用且设备加工结束时间tEicm小于当前时刻t，记录设备m的工序Oic已经完工，释放加工设备m，更新其加工设备变为可用;若Oic是最后一道工序，由式（15）增加成品i的库存量为Ri，并增加成品i被设备m加工的次数vim。

Ri=Ri+qi（15）

步驟2 构建可调度任务集合Φ。

根据式（16）判断原料j是否运输完成：若没有运输完成，记录原料j的运输权值及运输车辆k，将原料j放入可调度任务集合Φ; 否则，此任务不放入调度任务集合Φ。

∑Ii=1qi·uij-Lj≥0（16）

若原料j的当前库存量Sj能满足尚未投产的产品i（即αi=0）首工序的投料需求，记录成品i首工序的加工的权值及对原料j的需求量，将产品i首工序放入可调度任务集合Φ，否则，此任务不放入可调度任务集合Φ。

若非首工序Oic（c≠1）的紧前工序加工完成，记录该工序Oic的加工权值，将其放入可调度任务集合Φ;否则，此任务不放入可调度任务集合Φ。

若成品i已入库且根据式（17）判断其未完成配送，记录成品i被配送的权值，将其放入可调度任务集合Φ;否则，此任务不放入调度任务集合Φ。

qi-Li>0（17）

其中Lj、Li分别为原料j、成品i已安排的运输量。

步骤3 若集合Φ为空，则执行步骤5;否则从可调度任务集合Φ中选择权值最大的调度任务执行。

选择的权值可分为以下几种情况：若运输原料的权值最大，选择车辆k运输原料j，根据式（11）和式（7）计算原料运输的开始时间、结束时间，根据式（18）确定原料j的运输量，根据式（19）更新原料j的已安排运输量Lj。

Qkaj=min{Vk，（∑Ii=1qi·uij-Lj）}（18）

Lj=Lj+Qkaj（19）

若成品i首工序的加工权值最大，安排此工序在设备m上加工（即αi=1），根据式（20）减少原料j的库存量，根据式（21）和式（6）计算此工序的开始时间tSi1m及结束时间tEi1m。

Sj=Sj-qi·uij（20）

tSi1m=max{max{tvijj}， βi′im·tEi′cm}（21）

若非首工序Oic（c≠1）的加工权值最大，安排此工序在设备m上加工，根据式（5）和式（6）计算此工序的开始时间tSicm及结束时间tEicm，当c=Ii时，记录成品的入库时间为tλi=tEiIim。

若配送成品i的权值最大，安排车辆k配送成品i，根据式（22）计算成品配送的开始时间，进一步根据式（8）计算成品配送的结束时间，根据式（23）确定成品i的运输量，根据式（24）更新成品i的库存量Ri。

tSkai=max{δz′zk·tEka′z′，tλi}（22）

Qkai=min{Vk， qi-Li}（23）

Ri=Ri-Qkai（24）

步骤4 令t′=t，将当前时刻移动到被执行任务中最早完成的时刻t，即t={tEka*z，tEic*m}，利用式（27）对权值进行更新，然后转入步骤2。其中，a*，c*为t时刻已经开始，但尚未完成的运输和加工任务序号。

步骤5 若Φ为空，表示所有加工及运输任务已经完成，计算出调度任务的总时间，输出调度方案。

上述基于工艺过程逐步生成可行调度方案过程中，重点针对1.2节中约束条件进行设计。其中除式（5）～（7）直接在解码过程直接应用外，其他公式为便于解码过程操作进行了相应的转换。具体公式间对应关系为：式（2）转换为式（16）、（23），式（3）转换为式（17）、（18），式（8）转换为式（18）、（23），式（11）转换为式（21）、（22），式（9）和（10）分别转换为式（21）和（22）。另外，式（4）、（9）也在步骤2的物料选择条件中进行实现。

3.3 初始权值的计算方式

为了使始初矩阵内的权值之间能够明显差异化，在编码时利用式（25）把（0，1）的随机数转化成一个（0，∞）的权值，以实现个体多样性。

Pe（z，s）=ln（1+xzs）1-xzs（25）

其中xzs∈（0，1）。

3.4 启发式信息的设计

为使求出的解空间更大，设计了对运输及加工权值更新的启发式信息，即任务被相应资源执行的次数。物料在被车辆k运输一次或被设备m加工一次后，利用式（26）增加物料z被运输或加工的次数vzs，同时根据式（27）更新一次优先权值。

vzs=vzs+1（26）

Pe（z，s）=Pe（z，s）vzs+1（27）

3.5 算法步骤

算法运行前只需要设定唯一的参数是种群规模N，并令引领蜂规模Ne和跟随蜂规模Nu均为N/2。将调度方案的目标函数值f作为引领蜂和跟随蜂的适应值，通过算法进化得出f最小化的调度方案。初始时令f为任意最大值。之后进行以下过程：

步骤1 初始化引领蜂群。利用式（25）随机生成Ne个权值Pe（z，s），作为引领蜂的初始位置，并解码调度方案，根据式（1）计算目标函数值作为引领蜂的适应值fe。

步骤2 依据引领蜂适应值，利用式（28）计算每只引领蜂分配的跟随蜂数量Nue，

Nue=「（fe·Nu）/∑Nee=1fe（28）

步骤3 通过对应的跟随蜂种群寻优，更新引领蜂。具体过程如下（e、u分别为引领蜂与跟随蜂计数器，初值为0）：

3.1） 选定一只待更新的引领蜂xue。

3.2） 以引领蜂xue位置为指引，利用式（29）生成跟随蜂xue位置，以使其在该引领蜂周围搜索。

Pue（z，s）=Pe（z，s）·rnd（29）

其中rnd∈（0，1）。

3.3） 对跟随蜂xue位置进行解码，得出适应值fu：若fu优于引领蜂xe的适应值fe，即fu

3.4） 若u=Nue，即引领蜂xe的跟随蜂群全部搜索完成，转入步骤3.5）;否则u=u+1，转入步骤3.2）。

3.5） 若e=Ne，即引领蜂群全部更新完成，转入步骤4;否则e=e+1，转入步骤3.1）。

步骤4 将Ne只引领蜂按适应值fe由小到大进行排序，得出最优适应值f′。

步骤5 比较最优适应值f′与全局最优适应值f。若f′≥f，将适应值最差的引领蜂转化为跟随蜂，即Ne=Ne-1，且Nu=Nu+1。此时若Ne=1，则算法结束，并输出最优适应值和最优方案;若f′

上述算法过程中：一方面减少了参数设置，更便于应用。另一方面，引领蜂与跟随蜂既实现了各自分工（引领蜂在保留优秀解的同时指引跟随蜂搜索，而跟随蜂以引领蜂为中心进行随机搜索），又根据寻优状态进行角色转换，更好进行全局和局部搜索。

4 应用实例

4.1 IPPDS策略有效性分析

相较于IPPDS问题，对JSP和VPR的研究相当于将采购、生产、配送环节分段调度，而在IPPDS策略中，将采购、生产、配送三者同时优化，这样可大幅缩短总调度时间。为说明IPPDS策略相较于分段调度策略的有效性，以运输5种物料、加工6道工序为例进行說明。

某水果加工厂加工各种类型的水果，在期初接收到了3个客户的订单，客户1需要20t的箱装苹果（z=1），客户2需要15t的袋装苹果（z=2），客户3需要20t的袋装梨（z=3）。企业在接收客户的这些订单后，需要去果园采购35t的苹果（z=6）以及20t的梨（z=7），每个订单都需要经过拣选和包装两道工序。物料的需求量及运输时间如表1所示，所需用的车辆K1、K2相关信息如表2所示，3种订单的加工信息如表3所示。

采用分段调度策略对问题进行求解，将调度结果以甘特图的形式展现，如图3所示。

在该分步调度的方案中，0到8.5时，是去果园采购水果的阶段。待8.5时，所有水果采购结束，开始进行订单的加工，加工形式采用作业车间调度的方式; 20.5时，所有订单加工结束，开始进行订单的配送; 29.5时，所有订单配送结束，总的调度时间为29.5h。

为保证将新鲜的水果送到客户手中，采用IPPDS策略对问题进行求解，为直观表示，将调度结果用甘特图表示，如图4所示。

在IPPDS策略下，原料未运输完成的情况下，就可以开始生产，加工未完成的情况下，就可以进行配送，实现了采购生产配送的同时调度。由图4可知，相比分段调度策略，加工时间比分段调度策略提前了6h，配送时间提前了11.5h，总的调度时间缩短了35.59%，可以使客户需求的订单尽早地得到配送。

为了进一步证明IPPDS策略相较于IPDS策略的有效性，在上述例子的基础上，增加2个客户的需求，客户4需要15t的箱装橙子（z=4），客户5需要15t的袋装橙子（z=5），企业在接收客户订单后，需要去果园采购30t的橙子（z=8），并且需要增加运输车辆K3，新增订单同样需要进行拣选和包装两道工序。新增物料的需求量及运输时间如表1所示，新增车辆K3信息如表2所示，新增2种产品的加工信息如表3所示。

采用IPDS策略对该问题进行求解，将调度结果以甘特图的形式展现，如图5所示。

在该IPDS策略下，0到8.5时为去果园采购水果的阶段;待8.5时，所有水果采购结束，开始进行产品加工，采用作业车间调度方式，在产品加工过程中，对已加工完成的部分产品进行配送，实现生产配送的联合调度，在14.5时开始进行配送，27.5时，所有订单配送完成，总的调度时间为27.5h。

为保证将新鲜的水果在更短时间内送到客户手中，采用IPPDS策略对问题进行求解，为直观表示，将调度结果用甘特图表示，如图6所示。

由图6可知，相比IPDS策略，在IPPDS策略下，加工时间比IPDS策略提前了6h，配送时间提前了6.5h，总调度时间为21h，比IPDS策略缩短了30.95%，即6.5h，可以使客户订单更早地得到配送。若在增大物料需求量的情况下，将采购、生产、配送三个环节同时进行调度效果更显著。

4.2 DABC算法主要参数的确定

在DABC中，唯一需要确定的参数是种群规模N。为确定合适种群规模N，以原料j（j=1，2）、成品i（i=1，2，3）为例，其中原料J1可加工成品I1、I2，

原料J2可加工成品I3（各物料需求量及运输时间详见表4，所用车辆详见表5，成品的加工信息详见表6）。在不同种群规模下，即N取20，40，60，…，500不同的值，对DABC运行效果进行测试。每组实验运行10次后，取实验结果的平均值，并绘制出伴随着种群规模变化的最优结果平均值的变化趋势、优值方差的变化趋势及算法运行时间图，如图7～9所示，图7中的纵坐标反映了算法的优化结果;图9中的纵坐标表示运行的时间。

由图7可见，N=250时，DABC求解的优值曲线下降速率出现拐点;由图8可见，N=240时，优值的方差变化曲线出现拐点;由图9可见，N=260时，算法的运行时间曲线出现拐点。因此建议N在240～260取值。

4.3 算法有效性验证

刘玲等[4]用遗传算法求解了单机器生产下多车辆运输协同调度问题，本文考虑了作业车间情形下多车辆运输协同调度问题。文献[4]中考虑多车辆情况与本文考虑的多车辆情况类似，都是用多车辆运输多种物料，只是文献[4]中一辆车可以运输多个客户的订单到客户处，而本文问题是多辆车既运输原料又运输成品。正是由于两者的相似性，利用文献[4]中改进的遗传算法（Adapted Genetic Algorithm， AGA）对

本文问题进行求解。

为进一步验证DABC的优越性，再次利用基本的人工蜂群（ABC）算法对本文问题进行求解，即将DABC与ABC、AGA两种算法对比，测试数据分为小、中、大三种规模并随机产生，物料种类由5种增加到12种，调度任务总数由11种增加到30种。设定三种算法的种群规模均为N=260， ABC的引领蜂的局部寻优次数为20，循环次数为100，AGA的交叉概率pc=0.8，变异概率pm=0.1，循环次数为100。每種算法运行10次，比较三种算法运行的结果（见表7）。Z1、Z2、Z3列分别表示ABC、AGA、DABC运行10次的平均值。GP1表示ABC与DABC之间的差值比，计算方式为GP1=（Z1-Z3）/Z1*100%。同理，GP2表示AGA与DABC之间的差值比，计算方式为GP2=（Z2-Z3）/Z2*100%。如果两个比值是正数，说明DABC优于ABC及AGA。

从表7可以看出，10个测例的平均差值比分别为2.54%、6.999%，说明DABC运行出的优值要优于ABC及AGA;DABC有较优的方差，且都小于ABC及AGA的方差，说明DABC运行结果比较稳定。总体来看，DABC要优于ABC及AGA。

通过比较可见DABC表现出更好的求解能力和求解稳定性。究其原因主要有：1）调度问题是一类解空间离散的组合优化问题，采用邻域搜索的方式也很难得到问题最优解，因为最优值相同或相近的两个个体，编码值差别会很大，因此DABC中一方面引领蜂对优秀个体进行保留，另一方法跟随蜂在引领蜂周围形成针对性的差异个体，提高了算法的探索-开发能力;2）采用的二维实数的编码方式，有利于个体的进化计算，降低了算法实现和计算的复杂度，提高了算法运行效率;3）启发式信息的设计也提高DABC搜索效果。下面就启发式信息对算法求解效果影响进行分析。

4.4 启发式信息有效性分析

为验证启发式信息的有效性，随机生成5组测例，每组测例运行10次，并取结果平均值，比较去掉启发式信息后的DABC（DABC0）与DABC的运行结果，种群规模均为N=260。运行结果详见表8，其中Z4，Z5分别表示DABC0与DABC运行10次结果的平均值;GP3表示DABC与DABC0之间的差值比，计算方式为GP3=（Z4-Z5）/Z4*100%，如果该比值为正数，说明DABC要优于DABC0。

从表8中可以看出，5个测例的平均差值比为15.008%，说明DABC的运行结果要优于DABC0，说明了启发式信息的有效性。其原因在于：物料每被运输或加工一次，物料与其运输车辆或加工设备组合的权值被更新一次，避免每次选择车辆或设备时，只选择某辆车或某台设备，增加了解的多样性。

表格（有表名）

5 结语

本文的IPPDS问题在考虑作业车间生产环境下，将采购生产配送进行联合调度，是对IPDS问题的拓展和完善。DABC既减少了参数设置更便于应用，又表现出良好的求解效果。具体而言，本文的研究表明：

1）相对于分阶段的调度策略和IPDS策略，IPPDS策略可以大幅缩短了采购、生产、配送三个环节的总调度时间。

2）通过测例分析，改进的人工蜂群算法在使参数设置更简单的同时，还使算法求解效果有更稳定的参数设置区间。

3）通过对比分析，针对引领蜂跟随蜂协调机制和启发式信息而改进的DABC，对IPPDS问题求解表现出较好的求解效果，具有良好的探索开发能力。

IPPDS问题的解决，首先，从客户角度，降低订单的交货期使客户的需求及时得到满足，可增强企业的信誉度。其次，对于企业角度，高效地对客户的个性化需求进行采购、加工及配送，可降低企业运营成本，提高企业的竞争力。

参考文献 （References）

[1]WANG D， GRUNDER O， EL MOUDNI A. Integrated scheduling of production and distribution operations： a review[J]. International Journal of Industrial & Systems Engineering， 2015， 19（1）： 94-122.

[2]李凯，周超，马英. 考虑释放时间的单机JIT调度问题[J]. 运筹与管理， 2016， 25（3）： 71-77. （LI K， ZHOU C， MA Y. Single machine JIT scheduling problem considering release time[J]. Operation Research and Management Science， 2016， 25（3）： 71-77.）

[3]VIERGUTZ C， KNUST S. Integrated production and distribution scheduling with lifespan constraints[J]. Annals of Operations Research， 2014， 213（1）：293-318.

[4]刘玲，李昆鹏，刘志学. 生产和运输协同调度问题的模型和算法[J]. 工业工程与管理， 2016， 21（2）： 86-91. （LIU L， LI K P， LIU Z X. Model and algorithm of production and transportation collaborative scheduling problem [J]. Industrial Engineering and Management， 2016， 21（2）： 86-91.）

[5]LI K， ZHOU C， LEUNG J Y T， et al. Integrated production and delivery with single machine and multiple vehicles[J]. Expert Systems with Applications， 2016， 57： 12-20.

[6]JOO C M， KIM B S. Rulebased metaheuristics for integrated scheduling of unrelated parallel machines， batches， and heterogeneous delivery trucks[J]. Applied Soft Computing， 2017， 53： 457-476.

[7]JIANG L， PEI J， LIU X， et al. Uniform parallel batch machines scheduling considering transportation using a hybrid DPSOGA algorithm[J]. The International Journal of Advanced Manufacturing Technology， 2017， 89（5/6/7/8）： 1887-1900.

[8]TAXAKIS K， PAPADOPOULOS C. A design model and a productiondistribution and inventory planning model in multiproduct supply chain networks[J]. International Journal of Production Research， 2016， 54（21）： 6436-6457.

[9]JAMILI N， RANJBAR M， SALARI M. A biobjective model for integrated scheduling of production and distribution in a supply chain with order release date restrictions[J]. Journal of Manufacturing Systems， 2016， 40： 105-118.

[10]吳瑶，马祖军，郑斌. 有新鲜度限制的易腐品生产配送协同调度[J]. 计算机应用， 2018， 38（4）： 1181-1188. （WU Y， MA Z J， ZHENG B. Integrated scheduling of production and distribution for perishable products with freshness limitations[J]. Journal of Computer Applications， 2018， 38（4）： 1181-1188.）

[11]KERGOSIEN Y， GENDREAU M， BILLAUT J C. A Benders decompositionbased heuristic for a production and outbound distribution scheduling problem with strict delivery constraints[J]. European Journal of Operational Research， 2017， 262（1）： 287-298.

[12]ENSAFIAN H， YAGHOUBI S. Robust optimization model for integrated procurement， production and distribution in platelet supply chain[J]. Transportation Research Part E： Logistics & Transportation Review， 2017， 103：32-55.

[13]FU L， ALOULOU M A， TRIKI C. Integrated production scheduling and vehicle routing problem with job splitting and delivery time windows[J]. International Journal of Production Research， 2017，55（20）：5942-5957.

[14]KARAOGLAN I， KESEN S E. The coordinated production and transportation scheduling problem with a timesensitive product： a branchandcut algorithm[J]. International Journal of Production Research， 2016， 55（2）：536-557.

[15]程八一，李明. 面向生產库存配送的联合调度问题及蚁群优化算法[J]. 机械工程学报， 2015， 51（12）： 202-212. （CHENG B Y， LI M. Ant colony optimization for joint scheduling of production， inventory and distribution[J]. Journal of Mechanical Engineering， 2015， 51（12）： 202-212.）

[16]马雪丽，王淑云，刘晓冰，等. 易腐食品二级供应链生产调度与配送路线的协同优化[J]. 工业工程与管理， 2017， 22（2）： 46-52. （MA X L， WANG S Y， LIU X B， et al. Integrated optimization of production scheduling and distribution for perishable food products in twoechelon supply chain[J]. Industrial Engineering and Management， 2017， 22（2）： 46-52.）

[17]DEVAPRIYA P， FERRELL W， GEISMAR N. Integrated production and distribution scheduling with a perishable product[J]. European Journal of Operational Research， 2017， 259（3）：906-916.

[18]PAN Q， WANG L， LI J， et al. A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimisation[J]. Omega， 2014， 45：42-56.

This work is partially supported by the National Social Science Foundation of China （17BGL087）， the Project of Natural Science Youth Foundation of Colleges and Universities in Hebei Province （2011125）.

ZHANG Weicun， born in 1975， Ph. D.， associate professor. His research interests include intelligent optimization， industrial engineering.

GAO Rui， born in 1994， M. S. candidate. Her research interests include logistics and supply chain management.

ZHANG Man， born in 1993， M. S. candidate. Her research interests include logistics and supply chain management.