0 引言

随着经济及人口的急剧增长，能源危机与环境污染问题日益突出，可持续发展与绿色经济理念逐渐引起各界的广泛关注。据预测，到2050年，全球能源使用量相较2020年将增加近50%，如此大的增幅也进一步加大了全球能源供给压力^[1]。特别地，工业作为能源消耗量最大的行业，在过去60年间，其能耗几乎翻倍，约占世界总能耗的一半^[2]，能源的高效利用已成为学术界及工业界亟待解决的问题。作为工业制造系统的重要环节之一，生产调度的好坏将会直接影响企业的效益和竞争力^[3]，高效的调度决策能够协同优化企业的经济指标和绿色指标，实现增效、节能、减排、降耗、降成本，减少对环境的影响^[4-5]。

然而由于经营环境的急剧变化，高效节能的调度方案制定却变得越来越难以实现：1) 就产品需求而言，客户订单的产生时间往往是动态随机的，且每次需求通常包含有数量随机的多种产品类型^[6]。不仅如此，出于经济性、便利性等考虑，实践中同一客户订单所包含的多种产品需求往往需要一次性交付，这无形中增加了同一订单中不同产品之间内部等待的可能性及整个订单的完成时间。订单需求的动态性、随机性、多样性及耦合关联性，大大增加了企业生产管理的难度。2) 就产品生产而言，企业往往需要同时协调加工效率具有显著差异的多台机器(即异质并行机)，如复合半导体晶片的生产、纺织品的生产等^[7]。异质机加工环境有利于满足个性化的产品需求，且多台机器并行有利于加工效率的提升和机器间的互补。但这样复杂的机加工环境也使得机器间的协调优化变得十分困难，易造成较多的在制品积压和较长的中间等待时间。因此，如何充分利用生产设备的灵活性来快速满足多元随机的客户需求，是企业缩短订单完成时间的关键。

对于以上需求及生产中所存在的随机性、动态性、关联性、异质性等特点，现有文献中鲜有关于随机订单调度优化方面的相关研究。在同质并行机环境下，李运霞等^[8]用遗传算法探讨了专用并行机下的调度优化问题。在异质并行机环境下，为了实现最小的订单完成时间，XU等^[9]提出了数个启发式算法，XU等^[10]和ZHAO等^[11]则分别采用了不同的仿真优化算法来进行求解并对该问题进行了相关拓展^[12-13]，进一步考虑了准备时间和材料库存的影响。对于产出率最大化问题，XU等^[14]和ZHAO等^[15]考虑了两种常见模式的异同问题，并在ZHAO等^[16]的研究中被进一步分析，探讨了客户优先权的影响。当进一步考虑能源的峰值约束时，现有的相关研究极少，ZHAO等^[17]研究了一个异质并行机环境下的随机客户订单调度和能源分配问题，以最小化订单生产周期。以上的少量研究所考虑的订单调度决策是静态的、从一而终的，即同一分配方案会对所有的订单使用。

就方法论而言，模型预测控制(MPC)在生产调度领域有着较为广泛的应用。TANG^[18]采用基于MPC策略的滚动时域方法来解决动态并行机调度问题。CATALDO等^[19]采用MPC递归计算最优控制行为，以限制总能耗和最大化总产量。肖磊等^[20]针对离散型多品种、小批量企业优化其并行生产线。虽然模型预测控制技术在生产调度领域有着一定的应用，但是目前大多数文献关注的是确定性工件生产调度问题，很少有关于随机异质并行机客户订单的节能调度问题。

基于以上的研究现状及业界实践，本文在峰值能耗约束下，通过对异质并行机环境下的能源配置及随机客户订单的动态调度，来更加快捷有效地满足客户的产品需求。就产品需求而言，对于客户订单所具有的不确定性、关联性等特点，动态调度的运作方式具有良好的环境适应性及决策容错性，有助于优化方案随实际情况的改变而灵活做出调整。就生产环境而言，鉴于机器间异质性所造成的协调困难及随之而来的效率低下问题，能源配置可以增加生产环境的灵活性与协作性，提高系统的生产效率，有效协调并充分利用设备的产能^[21]，同时由于能源的稀缺性，过高的能源消耗水平将会给企业在经济、环境等方面造成较大负担，因此有必要考虑峰值能耗(即最大能耗)的影响。综合以上两方面的相关因素，本文利用模型预测控制方法，对随机订单的调度及有限能源的配置进行动态优化，以实现增效节能的目标。

1 问题描述

本研究考虑了随机环境下的动态客户订单调度和峰值能耗约束下的能源分配问题。客户订单的间隔到达时间，是服从于到达率为λ的指数分布的随机变量。订单n中共包含T(T≥1)种产品类型，产品t的需求随机表示为(为便于描述，初始时所有机器处于闲置状态，即初始需求为0，q_t⁰=0，∀t)，每种产品的期望需求量已知，表示为E(q_t) < ∞。

对于客户的产品需求，存在一组异质并行机对其进行加工。当机器m上每单位时间消耗单位能源用来加工产品t的需求时，其加工速度为v_mt，v =[v_mt]_M×T。此外，可通过改变机器上的能源分配，来实现更高效的加工速度调节目的。基于边际递减规律^[22]，本研究假设机器的能源消耗函数是凸函数，并采用这一具体形式，其中，p _mtⁿ和p_mtⁿ分别是消耗单位能源及e_mt单位能源下的加工时间，k是正常数。决策变量e_mt，e =[e_mt]_M×T是机器m上每单位时间为加工产品t所消耗的能源量，并且满足0≤e_mt≤ e_mt，其中e_mt为机器耗能上界，e=[e_mt]_M×T，所有机器的峰值能源消耗不超过E，即。生产过程中所有机器的最大总功耗称为峰值能耗，若其超过既定阈值，则在阶梯电价等政策下电价将大大高于额定电价。峰值能耗的控制是企业节能降本的重要手段。该能耗函数已在众多研究中被广泛采用^[22-23]。

对于每个到达的客户订单，其产品需求将通过订单调度决策，被安排在相应的机器上进行并行加工，δ_mtⁿ表示订单n中的产品t分配在机器m上的比例，δ_mtⁿ∈[0, 1]，δ ⁿ=[δ_mtⁿ]_m×t。每台机器上的待加工产品按照先进先出规则(FIFO)进行非中断加工，机器繁忙时待加工产品产生等待时间，且机器不允许存在人为的空闲时间。

对于该研究问题，产品的加工时间由策略(δ ⁿ，e)决定，即订单n中的产品t在机器m上的加工时间。对于订单n，其在机器m上的总加工时间{p_mⁿ(δ ⁿ，e)}_n=1^∞，队列中的等待时间及在机器m上的生产周期存在关系：

(1)

(2)

此外，由于同一订单中的所有产品都具有相同的到达时间，而每个订单的完成时间由最后完成的机器所决定，因此订单n在策略(δ ⁿ，e)下的生产周期，可表示为

(3)

本研究的目标是通过策略(δ ⁿ，e)的优化，来最小化订单的期望生产周期，即：

(4)

以上问题描述可表示为图 1。

2 问题分析 2.1 最优策略分析

对于本研究问题，由于每个订单的完成时间由加工其产品需求的最后完工机器决定，因而一个直观的想法是应使得同一订单在不同机器上的加工任务同时完工。然而由于顾客需求的随机性、机器的异质性及决策的动态性等因素，这一直观想法并不成立。

性质1  最优策略不一定使得同一订单中的产品需求在各台机器上同时完工。

证明  用反证法证明，假设最优解使得同一订单中的产品需求在各台机器上同时完工。考虑所研究问题的实例：存在2台异质并行机及2种产品需求，2台机器在最优能源分配下的机器加工速度为。前2个订单之间的到达时间间隔非常短(几乎可以忽略不计)，且第3个订单的间隔到达时间足够长，这两个订单的产品需求分别为(10 000，0)和(0，10 000)。如果假设成立，两个订单在所有机器上分别同时完工，则它们的完工时间分别为10⁴/(10⁴+1)和2×10⁴/(10⁴+1)，其平均值为1.5×10⁴/(10⁴+1)。然而，若令δ₁₁¹=1且δ₂₂²=1，则其平均加工时间为1，小于前者，与假设矛盾。得证。

性质1表明，在对本研究问题进行优化时，每次只考虑单独一个订单的最优决策，不足以实现系统整体的高效运行，甚至会产生较差的系统表现。由于订单间及同一订单中不同产品之间的复杂耦合关系，个体的最优很可能是以整体的损失为代价的，这一现象加剧了本问题的研究难度。

2.2 生产周期分析

由于订单的多样性、随机性和同步性及机器的异质性、耦合性、可变性等因素的共同影响，本文所探讨的订单期望生产周期这一目标即使是解析表达式也是很难获取的^[24]，对其进行优化就更加不易。为了加速最优解的寻找及评估，以下性质首先给出了所研究目标函数的下界，其中var(·)为相应变量方差。

性质2  本研究问题的最优目标函数具有下界：

(5)

其中，

证明  机器的最终速度(e_mtv_mt)不会超过性质2中的速度，且在此情况下，所有机器是同质的，因而最优订单调度策略为δ_mtⁿ=δ_mt=1/M。这使得该系统等效为M|G|1排队模型，其期望生产周期如性质2中的下界F所示。

除下界以外，上界的获取有助于在不知道最优解情况下，对系统的最差表现进行预估。

性质3  本研究问题的最优目标函数具有上界：

(6)

其中，

证明  任意可行策略的目标函数值都可作为该优化问题的上界。性质3中采取了使得所有机器同时完工这一策略。在此策略下，该系统是一个M| G| 1排队模型，其期望生产周期的表达如性质3中的上界F所示。

当只有一台机器时，以上上界和最优值等价，即此时最短完工时间可由性质3直接获取。在实践中，如果一台机器的性能显著优于他人或机器的数量非常有限，那么以上上界将可以极大地促进最优政策的确定。

2.3 产品差异分析

客户订单的一个显著特征是每个客户一次需要的产品类型可能不止一种，这一特点可以很好地体现现实中的需求，然而这也为相应的分析及优化带来了巨大挑战。一方面，不同产品的特性不同，即使在同一台机器上也可能有不同的加工效率，另一方面，产品之间由于机器共享及同步离开等因素，其加工活动存在着紧密关系。为了便于理解产品差异对系统的影响，性质4给出了产品类型数非常有限时的最优策略的显式表达。

性质4  当只有一种产品时，即T=1，最优策略可表示为

证明  由于对于所有所选的机器而言，需求信息均相同，因此任何订单都应具有相同的加工时间，反之则存在更好的策略以减少最长完工时间。在此情况下，这些机器可以被看成一个机器，其速度是所有工作机器速度的总和。因此最优可行策略应最大限度地提高总速度，即。基于e ^*及约束，可以得出：

性质4表明，当T=1时，可以在多项式时间中找到最优策略。此外，该最优策略表明，机器之间的协调对于提高整个系统的处理效率非常重要。特别地，应优先为加工时间对能源变化敏感的机器分配更多能源。此外，最优订单调度δ ^*使所有机器同时完工，这表明了机器之间完工时间适当平衡的重要性，从而有利于减少内部等待时间，更有可能实现更短的完成时间和更高的系统效率。

此外，对于每种产品需求的相对比例保持不变的情况，以下性质给出了其最优策略。

性质5  如果每个订单中每种产品的相对比例是固定的，即q_tⁿ∶ q₁ⁿ=a_t，∀n，t，最优策略(δ ^n*，e ^*)= (δ ^*，e ^*)可以由数学规划模型MP-C_prop决定：min C_prop

(7)

证明  对于第1个订单，因为q₁¹对所有机器都相同，因此式(7)左侧是其加工时间的有效表达，该模型对于C_prop的优化确保了该订单的高效完成。对于第2个订单，如果这两个订单的整体最优策略使得在它到来之前不可能存在机器闲置，那么这两个订单可以组合并优化，因为它们的需求是成比例的，易见该规划模型给出了其最优策略。若总体最优策略在第2个订单到来之前部分机器处于闲置状态，则此策略根本不是最优策略，因为第1个订单的周期时间可以进一步缩短。若总体最优策略在第2台计算机到来之前使得所有机器都处于空闲状态，则可采用和第一个订单相同的分析。将此过程推广到其他订单，以上结论得证。

性质5在按订单组装等场景中特别有用。例如，不同的组件(即产品类型)组装在一起以形成最终产品(即客户订单)，在此情景下，客户要求的产品尺寸各不相同，并且每个产品购买或接收的组件数量必须符合BOM(bill of material)的要求。性质5提供了一种可靠的方法，来确定相应的最短长期平均生产周期，这在实际的生产计划中非常有用。

2.4 机器速度分析

用于加工订单需求的机器通常具有不同的性能，这虽然使得系统更加灵活高效，但也增加了其分析的难度。不同的机器可能对分配的能源有不同的敏感性，且这些机器间不是独立存在的，它们之间具有很大的耦合性。

对于机器速度的影响，首先研究相同或一致并行机器的情形，性质6给出了其相应的最优策略。

性质6  当能源分配决策e满足，最优策略(δ ^n*，e ^*)=(δ ^*，e ^*) 可由以下的数学规划模型决定：

(8)

证明  能源分配决策e所满足条件意味着机器的最终速度(即e_mt^*v_mt)是均匀的。对于第1个订单，可证最优订单调度δ^*应按比例分配每种产品，并使所有机器同时完成加工，即式(8)。对于第2个订单，若它在该规划模型的策略下第1个订单完工后到达，则同理可得最优订单调度策略同样也是δ^*，即同样遵循式(8)。否则，这两个订单可以被视为一个，可以看出该策略对它们也是最优的。将此分析推广到其他订单，可得上述结论。

由性质6可以看出，当每台机器处理不同产品的相对效率彼此之间没有显着差异时，良好的订单调度应使得机器之间的加工时间尽可能均衡，这是因为机器加工时间的不平衡产生了额外的内部等待时间，考虑到客户订单中的产品需求同步离开这一特点，这将导致较长的完工时间。

3 算法设计

模型预测控制(MPC)是一种基于预测过程模型的控制算法，它根据历史信息来判断将来的输入和输出，主要包含预测模型、滚动优化和反馈校正3个要素^[25]。该算法采用滚动优化的方式，对于存在不确定性的复杂系统而言，无需在全局范围内判断最优表现，因此非常适合解决供应链管理中的动态优化问题，这也正是本文采用该类算法的原因所在。MPC算法的应用领域已由最初的工业过程控制，迅速扩展到航空、航天、供应链管理等多个领域。

对于本研究问题，本文借助MPC思想框架，构建针对订单优化的名为MPC-C的算法进行求解，其主要步骤为：

1) 能源分配决策

通过以下数学规划模型MP-C_max来最小化单一订单的期望加工时间，获取能源分配决策e_mt：min C_max

(9)

2) 订单调度决策

步骤1  对于到达的当前订单n，基于历史订单信息及订单n的相关信息，采取移动平均法，对其后l个订单的随机到达时间及产品需求信息进行预测，得到这些订单的到达时间及产品需求，其中移动平均法的计算为。

步骤2  基于数学规划模型MP-C_max所获得的能源分配决策e_mt，通过以下的数学规划模型MP-Total，来对订单n及其之后的l个订单同时进行优化，以获取调度优化策略(δ ⁿ，δ ⁿ⁺¹，⋯，δ ^n+l)：min C_max

(10)

步骤3  按照以上数学规划模型所获得的产品分配策略δ ⁿ，对订单n所需的产品在相应机器上进行分配与加工。

步骤4  更新系统中诸如机器当前完工时间等状态信息，获取下一个订单n+1的到达时间及需求信息。

步骤5  通过滚动优化的方式，利用步骤2中的手段对订单n+1进行优化。

本算法的流程如图 2所示。

研究指出k=1适用于大部分的政府及工业场景，而k=0.5对大规模集成电路的设计有很好的刻画^[22]，对于此种情形，算法中的两个数学规划模型可通过转化成二次约束二次规划的方式进行相应的求解。对于更一般的情形，拉格朗日对偶法是求解模型的有益思路。此外，本研究中性质2和性质3所构建的问题上下界，有助于缩小搜索范围、加速寻优过程。

4 仿真实验 4.1 实验设计

本节的主要目的是对所提算法MPC-C的性能进行评估。对此，本文将该算法与两个算法进行对比：1) 算法Fix，不考虑问题的随机性，即假设订单的到达时间及需求量都等于其期望值，通过求解MP-C_max数学规划模型来得到相应的静态优化策略；2) 算法Myopia：仅优化当前订单的完工时间，即根据当前订单到达时的系统状态及订单信息，通过数学规划模型法来尽可能降低该订单的完工时间。

本实验中问题规模的相关参数设置为：机器数量M=2，4，6，8，产品数量T=2，4，6，8。产品需求量的期望E(q_t)由正态分布N(5，0.1)取绝对值得到，每个订单中每种产品的需求量由均值是E(q_t)的正态分布这一在研究及实践中广泛存在的随机分布函数^[26-28]独立产生。为了检验需求量变动性的影响，本实验在两种需求量变动性情况下进行对比实验，即相对一致需求量(relatively uniform workload，RUW)和高度变化需求量(highly variant workload，HVW)，前者标准差由均匀分布U(0.6，0.8) 产生，后者为前者的两倍。订单的到达速率λ=0.5M/T。机器速度v_mt由正态分布N(5，0.1)取绝对值得到，能源分配上限e_mt由均匀分布U(0.9，1.1)产生，总能源E=MT。不失一般性，令加工效能系数k=1。

通过仿真实验来对系统的长期性能表现进行估计，仿真实验使用Matlab语言编程，在一台主频为3.60 GHz、内存为16 G的台式机上运行。对于每次性能估计，运行30次独立重复的仿真实验以减小误差。每次仿真实验当第1 000个订单完成时实验停止，并采用Welch方法^[29]来减少实验前后的影响，即利用其中的600个订单(201~800)的数据来进行性能估计。对于本文研究的峰值能源约束下的随机客户订单调度问题，由于其最优解难以获取，因此在稳态分析中，将通过与3.2节中性质2所构建的下界进行对比，以便对算法进行相应的评估，即：

其中，F^Alg表示所考虑的3种算法在特定情况下的目标函数值，F由性质2中的下界表达式求得。

4.2 实验分析

表 1和表 2给出了两种需求量变动性下的32种情况的实验结果。具体而言，在每张表格中，3~5列给出了3种算法的期望生产周期估计值相较于下界的性能差距，6~8列给出了各算法的计算时间，最后一列给出了相应的下界值，最后一行给出了每一列实验结果的均值。图 3和图 4依据性能差距及下界，给出了每种需求量变动性下期望生产周期的95%置信区间结果，由实验结果可以看出，该置信区间很窄，即基于4.1节实验设计所得到的结果是可信的。

在本实验中，下界F用来作为基准对相关算法进行评估，因此其质量的好坏对于评估的准确性至关重要。由于难以知道目标函数的最优值，所以本实验通过将F与所考虑的3种算法中的最好算法进行对比的方式，对下界的质量进行评估。这是因为3种算法中的最好算法可以视为最优目标函数值的上界，因此下界与最优值之间的差距一定不大于最小值的相关结果。表 1和表 2中的实验数据表明，所有情况下的平均性能差距约为6.48%，鉴于本问题的随机性及仿真误差的存在，可以认为这样的相对差距是较小的。下界随着机器数量M的增加而降低，随着产品数量T的增加而增加，这是因为机器数量的增加有助于分担加工需求，而产品数量的增多加重了系统的工作负荷。此外，通过对比表 1和表 2中的相应数据可以看出，当需求量变动性较大时，即客户订单的需求更加不确定时，下界的数值会变大。这可由下界的表达式得出，而更多的不确定性也使得系统的信息更加不完备，加剧了分析的复杂程度，因此下界有变大的趋势。以上分析结果表明，所构建和使用的下界F很好地吻合了系统的特点，对算法性能评估而言，可以作为良好的基准。由于该下界与最优解之间的差距相对较小且容易计算，所以在实践中，也可以使用该下界来对系统的当前状态进行评估和分析，进而制定相应的优化措施。

对比图 3和图 4中的相关数据可以发现，当需求量变动性变大时，3种算法的平均生产周期都有变大的趋势，这是因为更多的不确定性会导致系统未来的干扰变大，进而进一步削弱当下决策的正确性，降低系统加工的效率，延长订单的完工时间。与下界类似，对于问题规模变化的影响，随着机器数量M的增大，3种算法下的期望生产周期均有降低的趋势，而产品数量T的影响正相反。

对于3种算法之间的相对表现，表 1和表 2中第3列~第5列中的性能差距结果表明，本文所构建的算法MPC-C总体而言要好于所对比的其他两种算法。从性能差距的平均值“均值”一行中的数据可以看出，相比于下界F，算法MPC-C的平均差距最小，与算法Fix相比的差距高达3%以上。由此可以猜测，对于本文所考虑的复杂随机加工系统而言，良好的动态决策有助于提高系统的灵活性与适应性，从而更好地提升系统的加工效率。此外，算法Myopia的表现要差于本算法，这与性质1的观察相一致，即使得每台机器同时完工的单一订单优化策略，并不能保证系统的高效运行。虽然本算法的计算时间要稍长于其他两种算法，但是通过对未来订单影响的预估与权衡，可以更好地实现订单的快速响应，这在高度迅速变化的市场是十分重要的。

对于算法MPC-C，可以看到随着机器数量的增多，性能差距有变小的趋势，这表明对于现实中的大规模生产，本算法可以给出高质量的优化方案来提升系统的效率。随着产品数量的增多，性能差距有变大的趋势，然而即使产品数量增加了3倍，性能差距的变化也不超过14%。在制造系统中，客户订单的需求波动是导致生产周期延长的主要原因之一，产品数量的增多加大了系统的不确定性及协调的困难程度。同时，随着需求随机性的增加(对比表 1和表 2)，算法MPC-C的性能差异稍有增加，这意味着需求变化的降低有助于更快地完成订单需求。在实际应用中，可以使用诸多方法来减少需求的波动，其中提供价格激励是使需求变化趋于平缓的最有效方法之一，如沃尔玛为各种SKU(stock keeping unit)提供每天平价以平滑其需求，这种做法也发生在汽车租赁、活动票务和电视广告等多种场景下。

5 结论

本文针对异质并行机下的随机客户订单，在峰值能耗约束下通过对能源分配与生产调度的优化，来最小化订单的生产周期。研究对影响系统的相关因素进行了详细的理论分析，并基于模型预测控制理论设计了针对随机客户订单的优化算法。大量数值实验表明，本研究问题的决策及算法有助于提高系统效率及对环境的适应性，保证订单在能源约束下的快速响应。

本研究的主要贡献有：1) 将随机客户订单产品调度问题研究从传统的静态决策引入到动态决策。现有随机客户订单的调度优化研究大多采用静态的决策方式，这虽然有利于简化问题的研究，但是却很有可能带来方案灵活性差、资源不匹配、系统潜能不能充分挖掘等诸多问题。本研究对产品分配方案进行动态决策，根据实际情况的变化适应性地调整优化方案，从而有助于更加有效地完成订单的产品需求。2) 将并行机上的能源配置分析对象由静态单一产品的工件拓展到随机多产品的客户订单。现代客户需求具有极大的不确定性和多样性，对此，并行机上的能源配置有助于实现机器间的协调与协作及系统产能的充分利用。然而现有研究大多围绕确定性的单一产品需求展开，所探讨的能源分配方案缺乏对需求复杂性的考虑。与之相反，本研究针对包含了多种产品需求且具有随机性的客户订单进行研究，通过对有限峰值能源的合理配置，来实现机器之间的协同优化进而降低订单的完成时间。

对于未来的工作，一个有趣的研究方向是考虑其他常见的能演消耗及供应函数，如微电网供电。此外，采用多目标优化方法来研究能源目标与生产目标之间的权衡，也需要进一步的探索。可以想见，这些因素会使得研究问题编的更复杂，其他算法如强化学习可能可以提供这些问题的有效解答。