面向供应链的高级计划与排程的混合整数规划模型

陈可嘉 叶舒婷

福州大学，福州，350108

0 引言

生产计划与排程是制造企业生产运作的核心内容。当前，许多制造企业都采用企业资源计划（enterprise resource planning，ERP）进行生产管理，但是ERP无论在计划技术或功能方面都不具备协调多个企业资源的能力，它仍旧是面向企业内部的事务处理系统［1－2］。在市场竞争日益激烈、供应链上各企业间合作日趋紧密的环境中，ERP已不能满足现代制造企业的生产需求，寻找一种替代ERP的生产运作管理系统势在必行。面向供应链的高级计划与排程（advanced planning and scheduling，APS）的出现正迎合了这一趋势，是生产计划与排程技术的一个飞跃［3］。

随着APS的重要性的日益凸显，越来越多的学者开始对其进行研究［4－5］。但是，对于 APS模型的研究仍然较少，并且多是采用启发式方法进行求解，未能给出模型的最优解。文献［6］研究了制造－装配两阶供应链中的APS问题，以最小化存储和准备成本为目标，给出了混合整数规划模型以及基于两阶段逆向求解的启发式方法。文献［7］考虑了具有柔性加工顺序、机器可选等主要特征的供应链生产系统，以最小化流程时间为目标，建立了面向供应链的APS模型，通过算例验证了遗传算法在求解这一模型上的有效性。文献［8］考察了每个客户订单有确定交付期且外包可用情形下的APS问题，以最小化总制造时间为目标，提出了APS数学模型，并采用遗传算法进行了求解。

在日益重视合作生产的同时，现代制造企业也越来越强调准时交货的重要性。因此，最小化提前/拖期惩罚已成为排程研究的又一热点［9－10］。文献［11］分析了并行机提前/拖期排程问题，论证了该问题最优加工顺序的特点。文献［12］针对提前/拖期Job Shop排程问题，建立了相应的数学模型，提出了约束满足与禁忌搜索相结合的混合求解算法。然而，在APS问题中考虑提前/拖期惩罚，尚没有受到足够重视。

本文在考虑供应链物理约束、机器能力约束、工件加工顺序约束、可选机器、订单交付期的基础上，以最小化提前/拖期惩罚为目标，建立了面向供应链的高级计划与排程的混合整数规划模型，应用LINGO软件对算例进行了求解，得到了最优生产排程，验证了模型的有效性。

1 模型构建

1.1 基本假设

（1）工件的加工时间是预知的，辅助时间包含在加工时间内；

（2）工件必须连续加工，一旦开始加工就不能中断；

（3）每台机器一次只能加工一个工件；

（4）一个工件不能同时在两台机器上加工；

（5）产品的加工批量、运输批量等于产品的订货量。

1.2 问题描述

考虑一个具有多个工厂的供应链网络，在每个工厂中，有多台不同功能的机器，每台机器都受到一定的能力约束。供应链系统能够生产多种产品，不同的产品具有不同的物料清单、工件加工顺序，每一工件有一台或多台不同工厂的机器可供选择加工。在供应链系统中，有多份待加工的订单，不同的订单所需的产品不同、订货量不同、交付期不同。

面向供应链的高级计划与排程的目标是：在充分考虑供应链物理约束、机器能力约束、工件加工顺序约束的基础上，找到满足客户订单要求的、跨越整个供应链的、可行且最优的生产方案，使得提前/拖期惩罚最小。

1.3 参数定义

本文所涉及的参数定义如下：n为订单数；f为供应链网络中的工厂数；mk为工厂k的机器数，k＝1，2，…，f；Oi为订单编号，i＝1，2，…，n；TQi为订单Oi的订货量；Qip为订单Oi的工件p的数量；Pi为订单Oi的最终产品；tipkl为订单Oi的工件p在工厂k的机器l上的单件加工时间；Tipkl为订单Oi的工件p在工厂k的机器l上的批量加工时间；A（p）为工件p的子工件集；B为工件p的集合，即A（p）＝∅；Npq为工件q需要的子工件p的数量，p∈A（q）；TRuv为工厂u与工厂v之间的运输时间，当u＝v时，TRuv＝0（u，v＝1，2，…，f）；tt为机器每天的加工时间，即机器的加工能力；M为一个足够大的整数；DDi为订单Oi的交付期；ECi为订单Oi的提前惩罚系数；TCi为订单Oi的拖期惩罚系数。

1.4 变量定义

本文所涉及的变量定义如下：STipkl为订单Oi的工件p在工厂k的机器l上的开始加工时间；FTipkl为订单Oi的工件p在工厂k的机器l上的结束加工时间；当订单Oi的工件p先于订单Oj的工件q在工厂k的机器l上加工时，Xipjqkl＝1，其他情况下Xipjqkl＝0；当订单Oi的工件p在工厂k的机器l上加工时，Yipkl＝1，其他情况下Yipkl＝0；Ci为订单Oi的完工时间；Li为订单Oi的拖后时间（实数值）；Ei为订单Oi的提前时间（实数值）为订单Oi的拖后时间（整数值）；为订单Oi的提前时间（整数值）。

1.5 数学模型

（1）工件加工约束如下：

式（1）确保各个零件的开始加工时间大于或等于0。式（2）表明，订单Oi的最终产品的数量等于订货量，订单Oi的其他工件的数量等于该工件的上级工件需要该工件的数量乘以其上级工件的数量。式（3）表明，订单Oi的工件p在工厂k的机器l上的批量加工时间等于工件p在工厂k的机器l上的单件加工时间乘以订单Oi对工件p的总需求量。式（4）表明：当Yipkl＝1时，即当订单Oi的工件p在工厂k的机器l上加工时，其结束加工时间等于该工件在工厂k的机器l上的开始加工时间加上批量加工时间；当Yipkl＝0时，即当订单Oi的工件p不在工厂k的机器l上加工时，其在工厂k的机器l上的结束加工时间等于开始加工时间，即该工件在工厂k的机器l上的加工时间为0。式（5）表明，各订单的完工时间等于该订单的最终产品的结束加工时间。式（6）和式（7）确保同一机器在同一时刻只加工一个工件。式（6）表明，当订单Oi的工件p和订单Oj的工件q都在工厂k的机器l上加工（Yipkl＝Yjqkl＝1）时，工件p和q必须按照一定的先后顺序进行加工，工厂k的机器l不得同时对二者进行加工，即Xipjqkl＋Xjqipkl＝1。式（7）表明，当订单Oi的工件p后于订单Oj的工件q在工厂k的机器l上加工（Xipjqkl＝0，Xjqipkl＝1）时，订单Oi的工件p的开始加工时间不得小于订单Oj的工件q的结束加工时间；当Xjqipkl＝0时，式（7）恒成立。式（8）表明，订单Oi的工件p在工厂k的机器l上的开始加工时间大等于其子工件的结束加工时间，若其子工件在其他工厂加工，则订单Oi的工件p在工厂k的机器l上的开始加工时间大等于其子工件在工厂u的机器v上的结束加工时间加上工厂u与工厂k之间的运输时间。式（9）确保各个工件都能得到加工，并且一个工件只在一台机器上加工。

（2）提前/拖期约束如下：

式（10）和式（11）分别定义了订单的提前时间和拖后时间。由于设定机器每天工作tt小时，在约束式（10）和式（11）中将订单的完工时间除以tt，实现了将“小时（h）”换算成“天（d）”。当提前/拖期惩罚以天为单位时，式（12）和式（13）将各订单的提前时间和拖后时间转换成整数。也就是说，如果一个订单在交付期前0.5d完工，则认为该订单提前期为0d；反之，如果一个订单在交付期后0.5d完工，则认为其拖期为1d。为了保证计算的精确性，引入0.99来实现转换。

（3）变量约束如下：

（4）目标函数如下：

ECi和TCi分别为订单Oi的提前、拖期惩罚系数，一般情况下ECi＜TCi。目标函数式（18）表明，模型的优化目标是最小化提前/拖期惩罚，即尽量使各订单准时完工。

2 算例分析

为了验证模型的有效性，现参考文献［13］中的算例进行测试。

考虑如图1所示的产品结构，最终产品F1由组件S1、S2、S3与零件 C1、C2、C3、C4、C5组成。在所有工件中，C4与C6是通用件，其中C4是F1与S1的通用件，C6是S1与S3的通用件。零件C1、C2、C4与C5需要通过两道工序（P1、P2）加工，因此它们可进一步分解为CiP1与CiP2（i＝1，2，4，5）；零件C10需要通过三道工序（P1、P2、P3）加工，因此它可进一步分解为C10P1、C10P2、C10P3。

图1 产品结构

供应链中有两个工厂（记为FAi，i＝1，2），每个工厂各有三台机器（记为 Mik，i＝1，2，k＝1，2，3）。每台机器每天的加工能力为8h。从工厂FA1到工厂FA2的单向运输时间为8h，并且产品的运输批量、加工批量等于产品的订货量。

表1中，工件（列）与机器（行）的对应数字表示的是该工件在此机器上的加工时间，均以“小时”为单位，“－”表示该工件不能在此机器上进行加工。

现有一个客户订单：订购2个产品F1，交付期为25d。提前惩罚系数为0.15/d，拖期惩罚系数为0.75/d。

表1 工件加工时间 h

将建立的混合整数规划模型，运用LINGO软件进行求解，关键代码如下所示：

对于上述算例，混合整数规划模型共有7702个约束条件，3892个变量，其中3600个整数变量。在Pentium（R）Dual－Core E5500 2.8GHz处理器、2GB内存、Windows XP系统下，算例通过软件LINGO进行求解用时为18min29s，主要结果归纳于表2中。根据求解结果绘制出甘特图，如图2所示。其中，通用件表示为“通用件上级工件编号＋通用件自身编号”。例如，S1C6表示用于装配S1的C6部件，而S3C6表示用于装配S3的C6部件。由图2可以看出，算例订单的最优完工时间为200h，即25个工作日，订单准时完工，提前/拖期惩罚为0。

表2 求解结果

图2 求解结果的甘特图

上述结果说明，本文所建立的模型能在满足供应链物理约束、机器能力约束、工件加工顺序约束的基础上，得出使订单提前/拖期惩罚最小化的最优排程。

3 结语

以ERP为代表的传统生产计划排程系统多局限于单个企业内部，并且多以最小化流程时间为目标，难以适应现今面向供应链的准时生产模式。本文在考虑供应链物理约束、机器能力约束、工件加工顺序约束、可选机器、订单交付期的基础上，以最小化提前/拖期惩罚为目标，建立了面向供应链的高级计划与排程的混合整数规划模型。构建的APS模型突破了ERP的局限，针对供应链范围内的合作生产问题，优化了不同节点企业的生产排程，更加符合现实的需要，为进一步研究供应链优化问题提供了重要的参考。

［1］蓝伯雄，陈晖娜.一个集成化企业生产计划模型［J］.系统工程理论与实践，2001，21（9）：33－41.

［2］Rom W O，Tukel O I，Muscatello J R.MRP in a Job Shop Environment Using a Resource Constrained Project Scheduling Model［J］.OMEGA－International Journal of Management Science，2002，30（4）：275－286.

［3］徐晓芳，张伟，叶春明.APS剖析［J］.计算机辅助设计与制造，2002，8（4）：13－17.

［4］Marriott P，Kleinschmidt R，Glatzer V，et al.Advanced Production Planning as the Core Element of a Supply Chain［J］.Metallurgical Plant and Technology International，2002，25（1）：78－80.

［5］陆杉.浅析APS在供应链中的应用［J］.中国管理信息化，2008，11（20）：76－79.

［6］Kolisch R.Integrated Assembly and Fabrication for Make－to－order Production［J］.International Journal of Production Economics，2000，68（3）：287－306.

［7］Moon C，Kim J S，Gen M.Advanced Planning and Scheduling Based on Precedence and Resource Constraints for E－plant Chains［J］.International Journal of Production Research，2004，42（15）：2941－2955.

［8］程文明，齐二石.制造业供应链外包下的高级计划与排程［J］.组合机床与自动化加工技术，2005（5）：90－92.

［9］Gordon V，Proth J M，Chu C B.A Survey of the State－of－the－art of Common Due Date Assignment and Scheduling Research［J］.European Journal of Operational Research，2002，139（1）：1－25.

［10］Singh A.A Hybrid Permutation－coded Evolutionary Algorithm for the Early/tardy Scheduling Problem［J］.Asia－Pacific Journal of Operational Research，2010，27（6）：713－725.

［11］Toksari M D，Güner E.Parallel Machine Scheduling Problem to Minimize the Earliness/Tardiness Costs with Learning Effect and Deteriorating Jobs［J］.Journal of Intelligent Manufacturing，2010，21（6）：843－851.

［12］李俊芳，李铁克，王伟玲.约束满足混合算法求解提前/拖期Job Shop调度问题［J］.计算机工程与应用，2010，46（16）：12－15.

［13］Lee Y H，Jeong C S，Moon C.Advanced Planning and Scheduling with Outsourcing in Manufacturing Supply Chain［J］.Computers and Industrial Engineering，2002，43（1/2）：351－374.