张 栋, 胡祥培, 黄敏芳

(1.大连理工大学 系统工程研究所,辽宁 大连 116024; 2.华北电力大学 经济与管理学院,北京 102206)

0 引言

2010年以来农产品网上直销模式相继在北京、上海等地的出现，使蔬果类商品的流通模式由“农超对接”跃入“农宅对接”，为都市居民带来极大便利。对于通过网上直销销售蔬果类商品的企业来说，加工配送是蔬果类商品网上直销模式的关键作业环节，为了让客户当天吃到当日采摘的新鲜蔬果，企业在每天订单截止后于蔬菜基地进行采摘，经包装分拣作业后送至客户手中。这一过程要求加工配送中心在十分短暂的时间内处理大量个性化订单，且每一个订单的处理都需要经过采摘、标准销售单元包装、订单分拣多道工序，大量的个性化订单导致这一过程如何组织和调度变得十分复杂。且由于蔬菜种类繁多，形态各异，企业短期内无法实现全自动机器化包装，需要人工手动完成标准销售单元包装作业。人工作业效率的不稳定性、作业时间的随机性也使得这一问题的复杂性增加。综上分析，传统的手工作坊式生产模式已不能解决蔬果类商品的加工配送问题，要引入大规模流水作业的生产模式，而在这一模式下，如何高效地组织蔬果标准销售单元包装作业，有效协调标准销售单元包装、订单分拣、装车配送三个关键环节的生产节拍，使得作业人员能够按时无误地完成订单的分拣和装车配送的工作，提高效率，降低成本，确保前后作业工序的合理衔接，是蔬果类商品网上直销企业亟待解决的关键问题。

关于蔬果类商品包装作业的研究，可以归结为易腐品生产调度问题(perishable products scheduling)。近年来随着易腐品生产企业竞争加剧，企业不断提高自身服务质量，易腐品生产调度相关研究越来越受到国内外学者的重视，下面从模型和算法两个方面进行综述：

对于易腐品生产调度问题模型的研究，从研究思路上主要可以分为两类：第一种是以易腐品生产作业总成本或完成时间为目标，加上时间窗等约束条件，建立生产调度排序模型，设计求解算法的思路；另一种思路从库存控制的角度切入，考虑易腐品库存方面的特殊要求，研究易腐品订货策略和库存控制策略等[1,2]。鉴于本文所依托的企业采用直销模式，企业当日订单截止后直接从蔬菜基地采摘，经加工配送中心包装分拣后直接送达客户，不涉及多级供应商，所以本文采用第一种思路研究，故下文主要针对第一类文献进行综述。Claassen等[3]首先从战略和操作两个层面研究了食品等易腐品加工工业的包装作业计划和调度问题，并针对这一NP-hard问题提出启发式算法求解。Sabah等[4]在此基础上，将易腐品的生产线抽象为多阶段的流水作业系统，研究其作业调度问题，以按时完成为约束，以最小化系统流时间为目标，并考虑了多机工作负荷分配的平衡。Soman等[5,6]以一家荷兰的食品加工企业为例，考虑食品从加工到包装的过程，在调度生产的同时，针对食品工业的特殊性，加入了对库存成本进行控制的思想。Bilge等[7]以酸奶的生产加工线为例，以最小化总成本为目标，对生产和配送联合优化，考虑了酸奶的寿命期，转换时间和库存容量等一系列限制条件，建立混合整数规划模型并求解。Chen等[8]以最大化期望收益为目标，考虑商品的易腐性，对最优生产数量，生产时间和生产结束之后的配送路径进行决策。Nargess等[9]分析了快速消费品的周期需求特性，考虑了任务的最早开始时间、交付时间和最迟交付时间，建立周期调度问题(cyclic scheduling problem，以下简称CSP)数学模型，并应用WSPT优先规则和启发式算法进行求解。以上研究丰富了易腐品调度的理论研究，并为实际应用提供了一定的借鉴，但上述研究中的需求来自于超市对零售商，其需求波动较小，配送点少且集中，与网上直销模式的特点截然不同。在网上直销模式下，客户订单存在较大的个性化差异，客户配送点多且分散，这些特点导致已有研究结论与方法不再适用于本文考虑的包装作业调度问题。另外，为了按时处理大量个性化订单，加工配送作业具有多机并行作业、周期轮番作业、多车配送等特点。这些特点使得包装作业计划更加复杂。因此，网上直销模式下蔬果商品包装作业计划问题有待进一步的研究。

本文在现有研究的基础上，首先分析蔬果类商品标准销售单元包装作业的特点，然后建立个性化差异订单需求下的易腐品周期调度模型，以确定每个时间段、每个包装作业工作地所包装的蔬果种类、数量和顺序；针对前述问题的复杂性，改进现有启发式算法对模型进行求解。本研究有助于丰富易腐品生产调度理论，同时为解决网上直销模式下蔬果类商品的包装作业问题提供科学有效的模型和算法，具有重要的理论意义和实际意义。

1 问题描述

网上商城以最小销售单元(一般为某种蔬菜的500g或1000g左右)的形式进行销售，客户对最小销售单元随意组合并下单，蔬菜加工配送中心根据当日客户订单汇总，到蔬菜基地进行采摘，运至加工配送中心将新鲜蔬菜包装成为最小销售单元，然后按单分拣，装车配送。作业流程如图1所示。

图1 蔬果类商品网上直销模式基本流程

由于订单数量巨大，蔬菜种类繁多，所以本文研究引入流水作业思想，将包装——分拣——配送作为上中下游三道工序。本问题中采用统一规格的车辆按照客户订单所属的小区分区进行配送，以配送车辆作为流水作业节拍，将整个包装作业计划期按照每一配送车辆的作业任务划分为若干个作业周期，所以就包装作业而言，其作业任务呈现周期性需求的特点，作业方式具有成批作业轮番生产的特性。

本文将每一种蔬菜在每一个作业周期内的需求定义为一个作业任务(job)，决策具体包括分派job的作业机器与调度job之间的作业顺序。由于蔬菜商品具有易腐性和快速消费的特性，早于交货期(due date)完成会造成较高的库存管理成本，而晚于交货期完成会造成下游分拣需求无法供应，所以在建模时对每种蔬菜设置相应的提早和延迟完成的惩罚系数，并对每个job设定最早开始时间(release date)，和最迟完成时间(deadline)，任务早于其最早开始时间进行作业和晚于其最迟完成时间进行作业是不允许的，为简化计算，将库存惩罚系数和延迟惩罚系数设置为常数，即作业成本随着提前时间和延迟时间呈线性变化，具体时间窗约束如图2所示。

图2 标准销售单元包装作业任务时间窗

由于易腐品调度的关键在于有效地控制中间在制品库存，而且蔬果包装中人工作业容易出错，而周期调度方法在控制中间环节在制品库存以及减少人工作业出错率等方面具有优势[9]，所以本文采用周期调度的思想对蔬菜标准销售单元包装作业问题进行建模。但由于在直销模式下，客户订单需求存在个性化差异，导致每个生产周期总体包装作业任务量存在较大变动，加上网上商城订单规模大、客户需求分散，需采用多机并行流水作业方式才能完成既定任务，如果采用原有建模思路，会造成包装环节和分拣环节无法精准对接，甚至可能由于某一订单的某一品类缺少，导致后续订单分拣工作无法进行。所以如何基于周期调度思想，结合本问题的特点，构建科学的模型对这一问题进行描述，是本问题建模的难点。针对这一难点，本文根据每个作业周期的实际蔬果需求量来计算每个作业任务的时间和作业过程中带来的各项成本。以有效缓解由于包装和分拣环节需求不对称带来的分拣工序拥堵和可能存在的在制品库存过大等问题。

2 模型构建

2.1 基本假设

模型建立之前对本问题作如下界定：

(1)所有标准销售单元包装作业的包装台为一致平行机，即包装同种数量的同种蔬果所需时间一致；

(2)作业人员包装不同种类蔬果之间的转换成本与任务的作业序列有关(sequence-dependent setup cost)；

(3)在每个周期内，包装作业一旦开始，则不允许有空闲，即机器只在每个周期的开始阶段可有闲置；

(4)每个任务只允许在一台机器上作业，且任务作业过程中不允许间断；

(5)作业计划期已经根据分拣需求被划分为明确的C个长度为T的阶段(周期)；

(6)对于每一台包装机器而言，在整个作业计划期内轮番包装固定的几种蔬果，其作业顺序相同，但作业数量会根据每个周期的需求有所不同。

2.2 参数及变量表示

决策变量:Btij/Btij′:Btij为t周期内机器i上jobj的作业开始时间，Btij′为计算Btij的中间变量，Bti0为周期内首个任务的开始时间;Ctij/Ctij′：Ctij为t周期内机器i上jobj的作业完成时间，Ctij′为计算Ctij的中间变量，Ctif为周期内最后一个任务的完成时间;Etj：t周期内jobj的提前完成时间;Ttj：t周期内jobj的延迟完成时间;Dtj：t周期内jobj的需求量;Q：一个足够大的正数。

二进制变量：

2.3 数学模型

(1)

(1)式为目标函数，第一项为提前完成的库存成本和滞后完成的惩罚成本总和，第二项为各周期任务之间的转换总成本，因需求存在较大波动，模型对作业总成本进行优化，体现了与一般周期调度只对单周期成本进行优化的不同之处；(2)式表示每个任务只能在一台机器上进行加工；(3)式表示任何一个任务都有一个紧前任务和一个紧后任务；(4)式为周期调度假设约束，对每台机器，在每个周期内所包装的蔬菜种类及顺序一致；(5)表示每两个连续作业的任务之间一定有一大于等于0的间隔时间t；(6)式为初始任务开始时间约束；(7)～(9)式表示基于本问题特殊性的任务相关时间(包括开始时间和完成时间)的计算约束；(10)式表示相邻周期间的任务作业时间约束；(11)～(12)式表示任务的提前完成时间和延迟完成时间约束；(14)式表示任务的起始时间不早于规定的提前时间；(15)式表示任务的完工延迟时间不晚于任务的截止时间。

3 算法设计与求解

本文所研究的标准销售单元包装作业计划问题属于组合优化领域中的排序问题，已有研究文献[16]表明这一问题即使在包装机器为2时仍为NP-hard问题，当蔬果种类多，作业机器多时，解空间巨大，且本问题的多机并行作业和任务时间窗等约束条件也增加了模型求解的复杂性。上述特点导致本问题求解困难。模拟增压-退火算法[8]具有较少受初始条件约束、操作简单、以一定概率接受时间窗以外不可行解等主要特点，为有效求解这一复杂的含时间窗约束的组合优化问题提供思路。但由于该算法具有最终得到解的质量对初始解和邻域解生成策略有较强依赖性的缺陷，为克服上述缺陷，本文对模拟增压-退火算法进行改进，提出改进的模拟增压-退火算法对模型进行求解，具体算法设计如图3所示。

图3 模拟增压——退火算法求解流程图

3.1 解的表示

对N种蔬菜按照种类进行编号为1,2…N，对M台平行机也进行编号为1,2…M。由于每台机器所要作业的任务数不一定一致，所以，为便于作业计划解的表示，根据实际情况，设定每台机器所负责任务的蔬果种类数上限为W，则此问题的解可以表示为一个M×W的矩阵，如图4所示，其中M1,M2,M3,M4表示编号为1号到4号的机器，0表示虚拟任务。

图4 解的结构表示

3.2 初始解的生成

由于模拟退火算法的求解效果对初始解的邻域解生成策略依赖较较强，所以需要根据问题本身的特性生成好的初始解。根据前述周期调度的假设，生成初始解时需要将N种蔬菜安排在M条包装机器上进行包装作业，并使得每台包装机器上的总工作量尽量均衡。这实质为一个具有M个作业者的指派问题。对于将N个任务分配在两台机器上的问题，从相关研究可知，该问题可转化为0-1背包问题进行求解，属于NP-hard问题，所以当包装机器数M较大时，此任务分派问题较难得到最优解。而任务分派并非包装作业的最终目标，所以本文采用如下启发式算法生成初始解：

由前面假设，本问题每个周期中，客户对每一种蔬菜的需求只存在小幅度的波动，所以在生成初始种群时，为简化计算，先假定每个周期的需求一致，以此为基准来进行包装作业方案的初始化。算出每种蔬菜当日的需求总量，再根据每种蔬菜单元加工时间算出其总加工时间。

Step1将N种蔬果的总加工时间按照从大到小的顺序进行排序，所得到的蔬果种类序号依次为(a1,a2,a3…an)，对应的加工时间依次为(A1,A2,A3…An)，把(A1,A2,A3…Am)分别分至第1,2,…,M条包装生产线上，并令i=1。

Step2计算第1,2,…,M条包装生产线的当前总工作时间，将AM+i分派在工作时间最小的包装生产线上。

Step3令i=i+1，如果i>N-M，则得到任务分派初始解，转Step4，否则转Step2。

Step4得到初始解，结束。

3.3 邻域解生成策略

策略1随机选择两组机器数M1,M2，任务数N1,N2，然后将二者进行交换，得到邻域解。

由于策略1中随机交换任务生成邻域解的方法固定了每台包装机器上作业任务数，限制了邻域解的搜索空间，为了扩大邻域解的搜索范围，增加获得最优解的可能性，在此提出如下策略2，以解除任务数固定的限制。

策略2随机选择一组机器数和任务数(M1,N1)，和一组机器数M2和位置P，任务N1插入到M2机器上的P位置，得到邻域解。

图5 邻域解生成策略

3.4 迭代过程及降温升压准则

本问题采用“模拟升压-退火算法”进行求解，在迭代过程中设置温度和压强双重参数，随着迭代次数的增加，温度随之下降，压强随之上升，对于当前最优解根据上述邻域解生成策略生成其邻域解。对于邻域解，主要考察其目标函数值f(s)和违反时间窗的惩罚成本函数值p(s)，若两个方面同时优于当前最优值，则接受邻域解，否则以概率exp(-(f(S′,λk)-f(Sbest,λk))/τk)接受邻域解。并通过如下二式更新温度和压强(其中τ代表温度，λ代表压强):

τk+1=βτk

(15)

(16)

上面二式中相关参数设置可参考文献[10]。

3.5 迭代终止条件

本文算法将最大迭代次数Imax设置为10000，初始温度τ0设置为30000，终止温度τ′设置为1，当迭代次数I达到Imax或迭代温度τk低于τ′时，即终止迭代，输出此时的解，作为调度方案的最优解。

4 应用实例

4.1 CSP方法和非周期调度方法结果对比

本问题以北京昊宇神鹰农业科技有限公司为例，该公司蔬菜加工配送中心坐落于廊坊境内的蔬菜生产基地，毗邻北京城郊。初期主要服务于北京部分小区，现有蔬菜种类40种，日处理订单约4000个，其中一个订单平均重量4公斤、包含8种蔬菜(日采摘蔬菜近16000公斤，标准销售单元32000个)。公司每日下午4点截止当日订单，由于北京早晚车辆行驶高峰拥堵，车辆每日配送时间为凌晨，将货物送至小区智能配送柜.在每日下午4点至次日凌晨需完成采摘、标准销售单元包装、订单分拣与装车配送等一系列工作。为提高配送效率，先对所面对的数十个小区进行地区上的聚类，每辆配送车负责配送地区上相近的几个小区，采用配送车载重量为4t。每日的任务分4车配送完成。每日从下午6时开始标准销售单元包装作业，每车任务需在两个小时内完成，即6时～8时作业第一车任务，依次类推。

由于篇幅限制，挑取其中N=20,M=5(N为蔬菜种类数，M为包装机器数)的例子进行详细分析。

表1第一行为蔬菜种类编号(如1代表白菜，2代表茄子……)，第二至五行表示A,B,C,D四个小区当日蔬菜的订单汇总需求总量，第六行UPT为完成一个标准销售单元所需的时间，第七行UHC为一个标准销售单元所消耗的单元库存成本，第八行UDC为一个标准销售单元所消耗的单元延误成本。

为反应蔬果商品的需求特点，将蔬果划分为“常用”和“非常用”两类，标号上方有*的为常用蔬菜，否则为非常用蔬菜，常用蔬菜需求量在140～180之间生成随机数，非常用蔬菜需求量在60～100之间生成随机数，单元作业时间在10～20s之间。单元库存成本为3～5，单元延迟成本为10～15，为计算方便，对库存成本、延迟成本以及下面提到的作业转换成本进行无量纲数据处理，得到表1初始数据：

表1 各类蔬果需求数据

在表1中，UPT为单元作业时间(unit processing time)，UHC为单元库存成本(unit holding cost)，UDC为单元延迟成本(unit delaying cost)。

为简化计算过程，将蔬菜包装作业按照包装类别分为4类，上表中编号1～7为A类；为挑拣捆扎式包装，8～11为B类，为装袋式包装；12～15为C类，为托盘保鲜膜包装；16～20为D类，为翻筐挑拣式包装。同一类蔬菜之间的作业转换成本设置为10，不同类之间的转换成本如下矩阵所示：

ABCDA5504015B5053530C4035530D1530305

本文模型和算法基于周期调度的思想(以下图表中简称CSP)，而企业一般所采用的非周期调度方法(以下图表中简称非CSP)在安排作业计划时对每个作业周期单独考虑，而通常不会考虑周期与周期之间的联系，即在每一周期单独制定每台机器的作业计划，表2是本文方法与非周期调度方法对于上述算例的求解比较。

对每一种调度方法的程序运行50次，剔除异常解，取其中总成本最低的解进行比较，从上述结果可以看出，周期调度方法对于每种蔬菜的需求趋于稳定的假设下，相比于经验调度，在成本上有很大的改进，具体来说，周期调度方法得到的方案相比非周期调度方法在库存成本方面有很大程度的节约，在延迟成本方面也有明显改进，作业转换成本相近，造成延迟的任务数也有所减少。

表2 CSP调度方法与非CSP调度方法结果比较

图6和图7分别是本文方法和非周期调度方法所得到的方案甘特图，同种颜色表示同一种类型的蔬果，可见，在本文方法得到的方案中，对每一个包装作业机器来说，其工作频率比较均衡，对于所有包装作业工作地之间的比较，略微存在工作均衡上的差异，这可以通过每日之间的作业差异来进行调整。而对于非周期调度方法得到的方案，包装作业机器之间的工作量差异性比较明显，单台机器上的作业人员存在有时很忙，有时很闲的“闲忙不均”现象。从所有的包装机器的工作量来说，总工作量参差不齐，这不但加大了成本，还严重影响了作业完成时间和资源利用效率，在生产调度过程中是不合理的。

从包装作业出错率角度来说，从非周期调度方案生成的甘特图来看，对于同一台机器上的包装作业人员来说，作业蔬果种类频繁转换会导致作业人员的精神疲劳，从而导致包装出错率的提高。而CSP方法得到的方案在每台机器上，每个作业周期固定轮番地包装几种蔬菜，可以增加作业人员的熟练程度，有效降低作业出错率。

图6 CSP调度方案甘特图

图7 非CSP调度方案甘特图

4.2 参数灵敏度分析

主要分析蔬菜种类数N，包装机器数M和单位库存成本与延迟成本之比α(即库存成本在整个作业成本中所占的比重)三个参数发生变化时，CSP调度方法和非周期调度方法的适用性。

蔬菜种类N变化结果比较及分析：N=10,20,30,40(固定M=5,α=0.33)

表3 蔬菜种类总数N灵敏度分析

由此看出随着蔬菜种类的增加，周期调度方案产生的库存成本比之非周期调度有较大幅度的减少，但是减少的幅度呈下降趋势，周期调度产生的延迟成本则略有上升，作业转换成本相对比较稳定，无明显变化。证明周期调度比之非周期调度，在蔬菜种类较少时，效果更为明显。

包装作业机器数M变化结果比较及分析：m=3,5,7(固定N=20，α=0.33)

表4 机器数M灵敏度分析

随着包装作业机器数的增加，周期调度比之非周期调度在库存成本和转换成本两个方面改善幅度有所下降，但对延迟成本的改善幅度有所上升，说明当包装作业机器数较少时，周期调度方法可以很好地控制作业库存成本和作业转换成本，而当包装作业机器是较多时，周期调度方法对延迟成本的控制效果更为明显。

库存成本与延迟成本之比(α)灵敏度分析：α=0.25,0.5,1,2(固定N=20，M=5)

表5 参数α灵敏度分析

随着库存成本和延迟成本比值的加大，周期调度方法相比之非周期调度方法，在库存成本，延迟成本和转换成本控制方面的优势下降比较明显，有些结果甚至不及非周期调度方法得到的结果，当以保持流水作业通畅进行，不致因任务延迟完成带来下游作业拥堵为首要目标，即任务延迟完成所带来的延迟成本相对于库存成本较大时，这时的调度方案首要考虑降低任务延迟成本，其次考虑库存成本，在此情况下，周期调度方法在降低成本方面明显好于非周期调度方法。当任务延迟完成所带来的成本相对于库存成本不大时，这时降低库存成本成为首要控制的任务，在此情况下，周期调度方法并不适用。

综上数值应用实例结果，当所采用的生产模式为流水作业时，首先需要考虑上下游工序的衔接，保证生产作业能够顺利进行，而不至于因中间某一环节拥堵导致整个流水系统停滞，也就是说在这一模式下中间某一环节作业任务的延迟完成会对整个系统带来很大的影响，此时采用周期调度方法可以有效地控制作业成本。而当生产作业模式为单阶段生产或手工作坊式生产而非流水作业生产时，控制在制品库存成本成为首要目标，周期调度方法得到的方案在作业总成本上的优势并不明显，此时为方便起见，可以用非周期调度来指导生产。

5 结论

本文采用周期调度方法对蔬果商品网上直销的标准销售单元包装作业问题进行建模，通过启发式算法求解，最后通过算例验证，将得到的调度方案与非周期调度方案进行比较分析，结果表明本文模型和算法比非周期调度方法在作业成本方面有了明显的改善。

本文模型和算法有助于在网上直销环境下采用大规模流水作业解决蔬果类商品进行标准销售单元包装作业的问题，用科学定量描述的方法取代了传统的非周期调度方法，合理衔接了蔬果采摘和按订单分拣的作业，并大大减少了作业过程中的成本，为企业扩大生产销售规模奠定基础，具有重要的实际意义；在理论方面，文章采用周期调度的思想，针对任务人工作业时间不确定，作业时间窗严格的特点，解决了多机并行流水作业、周期轮番作业、多车配送等一系列复杂作业条件下的易腐品调度的建模问题，并改进了现有启发式算法对这一问题进行求解，在短时间内得到了优化的调度方案，文章的模型和算法丰富了易腐品生产调度相关理论。

后续工作将围绕包装作业机器异质化，包装作业区至分拣作业区送货车容量限制，以及考虑包装作业区至分拣作业区供应成本的联合优化等方面进行。