同类平行机生产运输协同调度问题研究

薛 梅

淮北师范大学1.经济与管理学院;2.信息学院，安徽淮北，235000

1 问题的提出

资源最优配置问题一直是企业关注的重点，合理的资源配置不仅可以大大提高生产效率，还可以提高企业的顾客服务水平。如何高效地配置供应链资源，现已成为供应链调度理论亟待解决的问题。2003年,Hall等[1]首次介绍了供应链调度的概念，以优化供应链成本和配送时间为目标，构建动态规划算法，解决由一个供应商和多个顾客组成的供应链协同调度问题。Li等[2]研究了单机环境下半成品、成品的运输与生产协同调度问题。张维存等[3]研究了原材料采购、生产和配送的调度模型，以最小化完工时间为优化目标，设计改进人工蜂群算法，证实了算法的有效性。蒋大奎等[4]探讨了平行机环境下的订单指派问题，通过设计的混合优化算法优化了最小化提前期和成本加权和的目标。轩华[5]考虑了运输能力有限的动态混合流水车间调度问题，采用改进拉格朗日松弛算法对问题求解，结果证明其有效。黄小曼[6]研究了差异分批调度问题，设计生产、库存和配送的调度优化方案，提出近似算法以实现最小化企业成本和制造时间跨度的目标。Naso等[7]从混凝土调度案例中归纳模型，研究了混凝土计划、生产与运输调度问题，提出启发式算法有效解决JIT问题。刘春来[8]考虑了由一个制造商、多个中间商和多个顾客组成的供应链问题，其中中间商位于不同地理位置。以最小化总成本为目标，设计了基于遗传算法的启发式方法，验证了算法的合理性。陈荣军等[9]考虑了由一个制造商和一个顾客组成的两级供应链，研究了按照工件最大送货时间和平均送货时间为排序规则的同类平行机调度问题，基于动态规划构造了多项式时间近似算法，分析了算法的性能比。Borumand等[10]同样考虑由一个供应商和一个客户组成的两级供应链，以最小化总延迟工件数和生产成本为目标，设计改进遗传算法(GA-VIKOR)，通过与其他算法的比较证实了算法的有效性。Hamid等[11]研究了多目标供应链优化问题，分别以最小化成本和库存为目标，提出了IENS算法，并证实其有效。Sajede等[12]研究了由一个制造商和两类不同需求的客户组成的供应链，一类客户在支付延迟交付费用前提下同意接受延迟交付，而另一类不同意，以最小化成本为目标，设计了改进遗传算法和蚁群算法，说明算法的可行性和满意性。薛梅等[13]研究了单机调度问题，设计改进离散粒子群算法优化制造时间。

综上所述，传统调度模型大多只考虑单机，忽略了半成品工件生产与运输对企业生产效率和成本的影响。本文以同类平行机为背景，研究半成品工件的运输与生产以及成品工件的运输问题，通过对工件进行排序、分批，设计批次分配和运输调度方案，以最小化制造跨度时间为优化目标，提出改进离散粒子群算法，一定程度上提高生产效率，减少企业交付时间。

2 问题描述和数学模型

2.1 问题描述

图1展现了一个供应商和一个客户组成的二层供应链。供应商有w个分布在不同地理位置的仓库，每个仓库都有充足的半成品工件，工件是由各自的尺寸Sj和加工时间pj共同决定的。仓库只有一辆运载工具，假定往返时间是固定的，记为T={T1,T2,…,Tk}。供应商拥有多台同类平行机，即可以同时加工多个工件的机器。机器容量与供应商运载车辆容量一样，均为B，假设所有工件的尺寸均不大于B。客户向供应商订购n个工件，工件集合记为J={J1,J2,…,Jn}。客户一旦下订单，供应商便开始处理订单。首先需要从仓库里选择n个半成品工件运输到工厂，然后经过加工运输给客户。

图1 两级供应链生产与运输协同调度模型

2.2 数学模型

模型存在如下假设：

①所有机器和车辆在零时刻有效；

②仓库的运载车辆有容量限制，每次只能运输一个工件；供应商仅有一辆运载工具

③工件加工过程不存在强占操作，即一旦批次开始加工，除非加工结束，否则不允许将工件从该批次中剥离；

④有一个充分大的缓存区，即加工完成的批次可以暂时放在缓存区；

模型的符号和含义说明：

参数：W,仓库的数量；k,仓库的序号；n,工件总数；j,工件序号，j=1,2,…,n;m,机器序号；l,工件批次总数，[n/B]≤l≤n；i,批次序号，i=1,2,…,l;Pb,批次bi的加工时间，等于批次中加工时间最长的数值；Rj,工件j到达机器的时间；T′,运载车辆在供应商和客户之间的来回运输时间。为了方便描述，将装卸载时间统一计算到运输时间中。

决策变量：xjim,若工件j属于第i个批次并且被机器m加工，则xjim=1，否则xjim=0；S1im,批次bi在机器m上的开始加工时间；C1im,批次bi在机器m上的完工时间；S2im,机器m上的批次bi的出发时间；C2im,机器m上的批次bi的到达时间；Cmax,制造跨度时间，即最后一个工件到达客户的时间。

本文的模型描述如下：

MinimizeCmax

(1)

(2)

(3)

(4)

S1im≥max{Rj×xjim}

(5)

S1im≥C1(i-1)m,i=1,2,…,l

(6)

C1im=S1im+Pb,i=1,2,…,l

(7)

S2im≥C1im,i=1,2,…,l

(8)

S2im≥C2(i-1)m+T’/2,i=1,2,…,l

(9)

Cmax≥C2im,i=1,2,…,l

(10)

式(1)表示优化的目标是最小化总跨度时间；式(2)说明一个工件只属于一个批次；式(3)说明任意批次中所有工件的尺寸之和不能超过机器容量；式(4)表示分配时没有工件被落下；式(5)和式(6)表示批次只有在机器有效的时候才可以加工；式(7)表示任意批次加工结束时间等于批次开始加工时间加上该批次的加工时间；式(8)和式(9)表示批次加工完成且运输工具有效的时候才可以被运输；式(10)表示整个跨度时间的性质。

3 离散粒子群算法及其改进算法

3.1 离散粒子群算法

1997年Kennedy和Eberhart为解决离散问题，提出了离散粒子群算法(BinaryParticleSwarmOptimization，BPSO)，该算法中粒子的编码是由一个多维向量表示的，它的下一代位置是由个体历史最优位置和群体最优位置共同决定。算法的速度更新公式依然采用PSO速度公式，即

(11)

Sig(vij)=1/(1+exp(-vij))

(12)

粒子通过式(13)改变位置：

(13)

式(11)-(13)中，w为惯性系数，c1和c2分别为认知系数和社会系数，r1、r2和rand均表示[0,1]的随机小数。通过数值模拟发现，当Vij∈[-5,5]时，xij会有一定的变换概率，因此取Vmax=5是一个相对较为合理的值。

3.2 编码方案及初始化

由模型可知，所有仓库在零时刻开始无空闲地运输半成品工件，直到供应商处的工件数达到订单数，这样便可以得到每个仓库运送工件的数量。由于优化目标是最小化跨度时间，因此先到必然先安排生产(FCFS)，故可以获得工件排序和对应的仓库号。采用0-1编码，用Xn维向量表示工件组批方案。数值1和前面的0组成一批，第n维数值均取1。如表1给出了一个实例，假设n=10,W=5,T={10,16,24,6,30}。将工件随机分成4个批次(图2)。由于机器有容量限制，提出BU(Batch Update)规则对存在的不可行解进行修正，过程描述如下：

表1 10个工件排序例子

图2 工件随机组批示例

对于任意批次bi，如果bi容量大于B，则对该批次进行如下处理：

如果|bi|-B+|bi+1|≤B，那么选择第一运输阶段最晚到达机器的工件J*，将J*归入到批次bi+1中。否则在j+1位置重新插入新批次，将工件J*归入批次bi+1中。然后将J*从批次bi中移除。

3.3 粒子适应度值的计算

适应度值是制造跨度时间。如表2给出了一组初始解。假设B=10，根据BU规则得到修正解，分批结果见表3。

表2 解的修正情况

表3 工件组批结果示例

根据模型可知，还需要将批次分配到机器上进行处理。由于批次有不同的到达时间，为了优化制造跨度时间，将按照先到达先安排处理(firstcomefirstserved,FCFS)规则分配批次。根据表1和表4给出的实例，可以得到分批结果，见表5。再利用FCFS规则对批次进行分配，结果如图3。

任务绩效会受到乐观希望、奋发进取以及自信勇敢的事务型心理资本的积极影响，任务绩效会受到坚韧顽强的正向影响，但是这一影响并不显著；针对工作绩效来讲，事务性心理资本各个维度能够发挥明显的正向影响，其中在工作奉献方面，奋发进取的影响较大；而从人际促进方面，坚韧顽强、乐观希望、自信勇敢等具有积极影响。

图3 2个机器情况下批次分配示例

表4 10个工件调度例子

表5 工件组批和批次到达时间

3.4 改进算法

BPSO算法多次迭代后会导致粒子搜索能力下降。故本文提出改进离散粒子群算法(缩记为PMs-MBPSO)，引入交叉和变异因子，有效解决算法早熟问题。因优化目标是最小化制造时间，故交叉操作是将粒子按照适应度值从小到大排序，选择前20%的粒子随机两两进行交叉，产生相应的子代，然后用子代取代父代。每维随机产生0或1，如果数值等于1，则将该维数值互换，否则不互换，如图4。

图4 交叉操作实例

变异操作是在粒子改变位置的过程中，增加编码数值的不确定性。变异概率以适应度值为基准，公式如下：

(14)

(14)式中，fmin指全局极值，favg指平均值，f指当前粒子的适应度值，P1=0.1，P2=0.01。每个粒子生成[0,1]间的随机小数，并将其与Pm进行比较，如果小于Pm，则粒子变异，否则不变异，如图5。

图5 变异操作实例

面向问题的离散粒子群算法和改进离散粒子群算法的流程图如下图6和图7所示：

图6 PMs-BPSO算法流程图

图7 PMs-MBPSO算法流程图

4 数值模拟与结果分析

4.1 参数取值

本文用随机产生算例的方法，将PMs-MBPSO算法与PMs-BPSO算法、PMs-GA算法进行比较。为了测试算法的有效性和满意性，将从5个维度考虑算例规模：工件数量J，工件加工时间Pj，工件尺寸Sj，机器数M和仓库数W，具体取值情况见表6。

表6 参数取值情况

4.2 结果分析

参数设置：初始染色体数为100，交叉概率Pc=0.8，变异概率Pm=0.1。粒子种群数为100，Vmin=-5，Vmax=-5，初始化速度公式Vij=Vmin+rand*(Vmax-Vmin)，c1=c2=2，w=0.5+rand/2。仿真算例均在VisualC#2010平台下实现，以迭代300次作为算法终止条件。

根据表6取值可得24种不同规模的算例，用M(a)J(b)p(c)s(d)W(e)表示，其中a、c、d、e∈{1,2}，b∈{1,2,3}。用最好值、最差值和平均值进行比较，分别用best、worst和average标记。为描述算法改进程度，定义改进率IA来体现PMs-MBPSO算法相较于其他两个算法的改进情况，见式(15)。

(15)

其中A代表PMs-BPSO和PMs-GA算法，值越大表明改进效果越好，具体情况见表7和表8。

表7 2个机器情况下PMs-MBPSO算法改进结果

表8 4个机器情况下PMs-MBPSO算法改进结果

由表7和表8可知，PMs-MBPSO的最好值全部优于其他两种算法，最差值也几乎都优于PMs-GA算法的最好值。随着工件数量的增加导致解空间呈指数增长，使得三种算法的搜索能力均有所下降，但PMs-MBPSO相对于PMs-BPSO和PMs-GA算法而言具备明显的优势。这说明随着工件规模的增多，PMs-MBPSO具有较好的鲁棒性。对于J1类，PMs-MBPSO的改进程度较差，这是由于工件规模较小，解空间较小，三种算法都能在固定的迭代次数中找到近似的最好值。

半成品工件的运输-生产-运输多阶段调度问题常常存在于像钢铁企业这类生产过程非常复杂、生产工艺要求较高的企业。而本文提出的改进离散粒子群算法在一定程度上可以缩短产品制造时间，提高企业生产效率，降低生产成本。

5 结 语

本文考虑了同类平行机背景下，分布在不同地理位置的工件的生产与运输协同调度问题。在生产能力和运输能力均有限的情况下，构建调度模型，针对问题特点，提出改进离散粒子群算法。采用FCFS规则把批次分配到同类平行机上，并对迭代过程中产生的不可行解利用BU规则进行修正。通过仿真实验将PMs-MBPSO和PMs-BPSO、PMs-GA进行比较，结果表明PMs-MBPSO算法的满意性。这表明针对本文的调度模型，PMs-MBPSO算法能够大大提高资源配置效率，对于供应商而言不仅可以节约时间，还可以减少产品提前期，更快速地将产品运输给客户，从而获得顾客满意，这对于企业的运营管理有着极重要的意义。

在后续的研究中，可以从两个方面进行，一是改变优化的目标，如考虑优化供应商总成本，最大延误工件数，或者两者的加权和等；二是改变生产特点，如考虑机器的恶化效应和工人的学习效应等。