公共订单服务平台下制造联盟生产与运输两阶段协同调度成本最小化问题^*

刘捷先

(铜陵学院 会计学院，安徽 铜陵，244061)

(合肥工业大学 管理学院，安徽 合肥，230009)

【摘要】本文研究了公共订单服务平台下制造联盟生产与运输两阶段协同优化问题，优化的目标是最大化生产与最小化运输成本。本文证明了该问题为NP难问题，分析了该问题的结构性质，并基于这些性质，提出了MLS启发式算法，并通过大量实验与LS启发式算法进行比较，证明了MLS启发式算法的有效性。

关键字：制造联盟；生产与运输；协同优化；成本；调度；MLS启发式算法

中图分类号：F 27；C 931.1  文献标志码：A

Cost Minimization of Two-stage Cooperative Scheduling Problem of Production and Transportation in Manufacturing Alliance Based on Public Order Service Platform

Liu Jiexian

  (School of Accounting , Tongling University，Tongling city, Anhui province，244061,China)

(School of management, Hefei University of technology，Hefei city, Anhui province，230009,China)【Abstract】This paper studies the two-stage collaborative optimization problem of production and transportation in the manufacturing alliance under the public order service platform. The goal of the optimization problem is to minimize the maximum total production and transportation costs. It is proved that the problem is NP hard. Base on the studied structural properties, a heuristic algorithm MLS is proposed to solve the problem. Compared with LS algorithm, the efficiency of MLS is proved through many experiments.

Key words: manufacturing alliance；production and transportation；collaborative optimization； cost；scheduling；MLS heuristic algorithm

一、引言

基于云计算、大数据、物联网等新兴信息技术，云制造作为一种新型的制造模式在科学技术与制造业相结合的条件下应运而生。云制造为进一步降低制造资源的浪费和闲置提供了可能。基于云制造技术，公共订单服务平台可以实现社会资源的互联、制造资源与服务的开放协作，制造资源的利用率更高，避免了大量资源闲置的情况出现，因此研究基于公共订单服务平台的生产与运输协同优化具有很重要的意义。制造业的发展受到制造工厂的加工效率的影响，制造工厂需要考虑到机器的使用与运输成本。通过考虑供应链中生产与运输两个阶段，将制造需求与制造供应有机的结合，在满足各个客户的要求前提下，利用生产运作管理的相关方法，寻求某些目标的最优化。

大量文献对只考虑生产阶段调度的问题进行深入研究。Zhang等^[1]假设作业的处理时间是不确定的，利用动态规划与FPTAS方法分析了带有节省成本约束的最小化最大完工时间的问题。Lee等^[2]研究了在最小化完工时间的约束下最小化机器使用成本与在最小化最大完工时间的约束下最小化机器使用成本两种问题，并设计了相应的启发式算法，获得了最坏误差界。李凯等^[3]研究了释放时间具有减函数约束的单机调度问题，提出了一种模拟退火算法，实验证明该算法可以在能够有效时间内寻找到高质量的满意解。Gu等^[4]等研究了最小化最大完工时间的车间作业调度问题，提出了一种改进的IAPSO算法，实现了机器更有效的利用。在经典调度问题中，作业的处理时间一般是固定不变的。He等^[5]研究了最小化最大完工时间与总的完工时间和双目标批调度问题，通过一个动态规划算法有效解决了该问题。Meng等^[6]将生产调度问题延伸到家庭作业中，研究了最小化最大完工时间的平行批调度问题，并提出了一种在线模糊算法。

现有考虑生产运输成本的调度问题的研究比较少。Rustogi等^[7]研究了可增加额外机器的平行机调度问题中的影响，通过比较增加机器造成的减小值和成本增加值，从而确定最优的使用机器数。Li等^[8]针对计算机网格调度任务的优化问题，综合考虑成本和最大完工时间双目标，提出了MMCTB算法，实验表明MMCTB算法更加高效。Qi等^[9]研究了带有完工时间约束的最小化资源可用成本的调度问题（RACP），提出了一个新颖的启发式算法，实现了有效地寻找最优解决方案。李凯等^[10]研究了带有单个制造商与多个零售商的生产-库存-配送协同调度问题。本文考虑了供应链中生产与运输两个阶段，每个订单在两阶段中需要备料、等待加工、加工、缓存、运输五个环节，每个环节都要消耗一定的成本费用，我们假设各个环节的单位成本相同且与时间成正比。

本文针对供应链中制造联盟生产与运输两阶段协同优化问题进行了研究，生产阶段考虑了多制造商、生产恶化函数的、订单加工等多个因素，调度目标为最小化最大生产运输成本。该研究问题的整体框架如图1所示。下一节对问题进行了表述，并给出了参数表示；第三节分析了该问题的结构性质；第四节为解决该问题提出了MLS启发式算法；第五节通过大量仿真实验验证了MLS算法的有效性；最后，第六节对本文进行了总结与展望。

图1 供应链中生产与运输协同优化问题框架图

二、问题描述与参数表示

表1 参数表

所研究的问题描述如下：由个制造商组成的制造联盟在时刻接到来自同一个客户区域的个订单。每个订单包含一定数量的工件，这些工件都能被每一个制造商加工，同一个订单内的所有工件必须全部加工完成后才能加工下一个订单内的工件。每个制造商处只有一台加工机器。受到机器老化的作用，工件的加工时间会随着其开始加工的时间的增大而增加。我们将Wang等[11]人在单机调度问题中的对于加工时间的定义拓展到多制造商组成的制造联盟的任务调度系统中，具体数学定义如下：

其中，和表示工件加工时间的恶化效应，为工件加工的开始时间。

制造阶段的订单完成后，将由运输车辆运输到客户区域处。由于从同一制造商处到同一客户区域内的客户处的运输时间差异较小，为了简便起见，在本文中我们不作区分。每个制造商处各有一个运输车辆，每个运输车辆一次可以运输一个订单，制造商处与客户处的单程运输时间为。订单的生产运输成本，最大生产与运输成本，具体目标函数是最小化。采用常用的调度问题三参数表示法，所研究的问题可表示为。

三、问题结构性质

在本节中，我们首先证明了所提问题为NP难问题。考虑问题的复杂性，我们给出了每个制造商处加工订单集合已知情形下最优排序的结构性质，基于结构化性质提出了用于求解此特殊情形下问题的启发式算法。最后证明了该启发式算法能够在多项式时间内求得特殊问题的最优解。

引理1：所研究的问题是NP难问题。

证明：假设不考虑恶化效应（, ）；每个订单内只有一个工件；那么所研究的问题可简化为问题。已知问题为NP难问题，因此，所研究的问题亦为NP难问题。

引理2：对于问题来说，假设订单在制造商处加工且加工的起始时间为，那么订单的在制造商处的完工时间为

证明：该定理可用数学归纳法证明如下：

    假设订单只有1个工件，即，则完工时间为

    可以看出，公式（1）在时成立。

    当时，假设公式（1）成立，可以得出

    那么，情形下订单的完工时间计算如下：

可以看出，当公式（1）在情形下成立时，公式（1）在情形下同样成立，因此该定理得证。

推论1：对于问题来说，每个订单内的工件的加工序列可以是任意序。

证明：由公式（1）可知，每个订单内工件的排序并不影响该订单的完工时间，因此在最优解中订单内工件的排序可以是任意序。

引理3：对于问题来说，假设在制造商处的订单加工序列为 ，那么制造商处最后一个订单的完工时间为

证明：该定理可用数学归纳法证明如下：

对于制造商的第1个订单来说，其完工时间为

可以看出，公式（2）在计算的完工时间时是成立的。

假设公式（2）对于，成立，那么的完工时间为

那么的完工时间为

因此，公式（2）对于计算订单的完工时间同样成立。我们同样可验证该公式对于计算订单的完工时间同样成立。综上，该定理得证。

引理4：对于问题来说，假设在制造商处加工的订单加工序列为 ，如果，那么订单的处理时间不大于订单的处理时间，即。

证明：假设订单的开始加工时间为，由引理2可知该订单的处理时间计算如下：

同样地，订单的处理时间计算如下：

因此，订单与订单的处理时间之差为

由假设可知，，因此

该定理得证。

引理5：对于问题来说，假设在制造商处加工的订单加工序列为 ，那么存在一个最优排序满足。

证明：假设存在一个最优排序，其中。交换订单和订单的位置得到新的排序记作。其中，和分别是位于这两个订单前后的部分订单子排序，和可以为空。假设订单的开始加工时间为，那么最优排序中订单和订单的完工时间分别为

同理，中订单和订单的完工时间分别为

可以看出，中的结束时间与中的结束时间相同，中的开始时间与中的开始时间相同。和中两订单处理时间之间数值关系可用下图来表示。

图2 和中两订单处理时间示意图

依据图2，和中两订单处理时间之间数值关系以及运输车辆到达制造商处准备运送中的或者中的的时间，我们分为以下三种情况来分析交换订单位置后给最优排序的目标值带来的影响。为了简便起见，我们将运输车辆到达制造商处准备运送中的或者中的的时间记作。

情形一：  并且

在此情形下，运输车辆到达制造商处时中的或者中的都还未加工完成（或者恰好完工），因此，运输车辆在制造商处等待直至订单处理完成后直接将该订单运送到客户处。情形一可用图3表示。由图可知，中相较于中的而言，会提前被运送到客户手中。而且中的完工时间不变，该订单离开制造商处的时间点不会延迟，中的所有订单离开制造商处的时间点也不会延迟。综上，相对于最优排序而言，中最后一个订单到达客户手中的时间不会延迟，因此，在此情形下也是最优排序。

图3 情形一示意图

情形二：  并且

在此情形下，运输车辆到达制造商处时中的未加工完成（或者恰好完工），并且中的已经加工完成，因此，在中，运输车辆在制造商处等待直至订单处理完成后直接将该订单运送到客户处；在中，运输车辆到达制造商处直接将完工的订单运送到客户处。情形二可用图4表示。由图可知，中相较于中的而言，会提前被运送到客户手中。而且中的完工时间不变，该订单离开制造商处的时间点不会延迟，中的所有订单离开制造商处的时间点也不会延迟。综上，相对于最优排序而言，中最后一个订单到达客户手中的时间不会延迟，因此，在此情形下也是最优排序。

图4 情形二示意图

情形三：  并且

在此情形下，运输车辆到达制造商处时中的或者中的都已加工完成，因此，运输车辆抵达制造商处直接将完工的订单运送到客户处。情形三可用图5表示。由图可知，中离开制造商处的时间和中的离开制造商处的时间相同。而且中的完工时间不变，该订单离开制造商处的时间点不会延迟，中的所有订单离开制造商处的时间点也不会延迟。综上，相对于最优排序而言，中最后一个订单到达客户手中的时间不变，因此，在此情形下也是最优排序。

图5 情形三示意图

综合以上讨论可知，最优排序中存在订单和订单并且满足，那么交换订单和订单位置后产生的排序仍是最优的。重复交换最优排序中满足上述关系的订单可得到引理所述的性质。

引理6：对于问题来说，假设在制造商处加工的订单加工序列为 且满足引理5的性质，那么订单的生产运输成本为

其中，, ,

证明：当时，那么在前个订单中必有一个订单在运输工具到达制造商处还未完工。假设该订单为，那么该订单的处理时间要比运输时间长，即。由引理4和5可知所有在后面加工的订单的处理时间都不小于的处理时间，因此都大于运输时长，即。综上可知，完工后可直接被运送到客户处，故最后一个订单送达客户的时间为其完工时间与制造商到客户处的运输时间之和，因此订单的生产运输成本为。相反地，当时，可