启发式算法在电梯生产计划领域的应用

孙加洲 周炳海

(同济大学 机械与能源工程学院 上海201804)

回顾过去一个世纪，随着国内国际市场竞争的日益激烈，市场对制造企业的生产计划与控制提出了新的挑战，因此，继传统MRP之后，最优化技术、约束理论以及高级计划与排程，日益成为了生产计划领域研究的热点问题，而最近提出的“智能制造”和“中国制造2025”等理念，更是对企业的科学化、智能化管理提出了更高的要求。

传统的MRP系统在实际应用过程中逐渐暴露出以下弱点：（1）MRP计划方式中对于DS设定的是固定提前量；（2）MRP计划一般是建立在工作能力无限的基础上；（3）由于MRP不具有动态择优逻辑，当有多个排程方案时，需要人工去判断和比较；（4）由于人工介入的内容较多，MRP计划编制耗时较长，当计划变更时，更是相当困难。

为了解决上述问题，引入了高级计划与排产技术，高级计划与排产是“Advanced Planning and Scheduling”的中文翻译，简称APS，该技术是数学算法、计算机技术与IE管理思想三者的结晶，它对于解决部门内部、不同部门之间甚至是企业之间的全局优化，提供了一套系统的方法论。

全局优化的过程中会建立合适的数学模型，采取基于直观经验构造的智能化算法，明确限制条件，通过复杂的运算得出一系列可行解或最优解。通过引入APS排程，企业可以识别制造瓶颈，精确排产天数，减少在制品和库存，快速同步计划，并最终实现企业资源的最优化调度。

1 问题说明与目标提出

伴随着中国城镇化进程的推进，住宅建筑、商业建筑以及基础设施的投入均处于较高水平，电梯行业也迎来了黄金时期，目前我国电梯年产量和保有量都居世界第一位，电梯产品的市场前景良好。

为响应市场对电梯安全性，外观装潢，运行稳定性等方面的诉求，企业采用了订货工程型的生产方式（Engineer to Order, ETO），从接受客户订单后开始着手设计与制造，在满足客户的同时，也带来了其他负面影响。

一方面，由于机种、速度、载重及提升高度等选配指标的多样化，导致同一功能的各种部件生产时间差异很大，而工作中心的可供工时几乎恒定，必然造成产能供需不均衡。

另一方面，电梯需要现场安装的产品特点决定了电梯部件一般是以多组木箱的形式交付客户，为了降低仓储成本，减少工段在制品，各木箱内的部件需要集中产出并及时装箱。

在传统的MRP计划模式下，只能考虑预先设置的静态单一的限制条件，常用的限制条件有：一条工艺线路所涉及的多个工作中心之中的瓶颈工作中心负荷、内作部品所在箱子的箱内同期性、特殊规格排产连续性、重要客户的提前交货期限、未进行备库的外协部品最短交货期等。

一般以其中一种限制条件完成排产后，通过得出的排产结果，反向验证其余限制条件是否被满足。如果满足则计划可行，如果不满足，则需要调整计划。除了运算过程复杂、调整费时费力之外，这样的计划方式存在以下几点主要矛盾：（1）如果根据各工作中心的生产能力独立安排产能，会造成装箱成套率低，工段在制品大量堆积，进而造成每日成套台数和装箱负荷波动很大。（2）如果根据装箱情况进行排产，满足了箱内同期性，则各工作中心的负荷波动会增加，工段时忙时闲，情况严重时工段无法完成生产任务。（3）如果选定一个工作中心作为主流，其余工作中心参照其进行排产，虽然是一个介于两者之间的方案，但是评定以哪个工作中心为标准，这个工作本身就比较困难。

基于上述分析不难发现，传统MRP计划模式已无法解决企业面临的问题，为了从公司整体角度做好资源合理分配，平衡生产负荷，减少在制品，在保持各品目原有生产方式不变的前提下，通过引入APS对原有排程逻辑进行优化，最终给出一个可以兼顾每日产能波动性和装箱同期性的生产组织方案。

2 解决思路与步骤

2.1 APS概念与参数

1） 计划负荷波动

计划负荷是工段生产任务与生产能力关系的体现，等于每日计划时间与增值作业时间（在岗时间*综合率）的比值，其值越小，说明计划的可执行度越高，平准性越好；

2） 箱内同期性

反映一个箱内所有部件完工日期的差异天数。其数值越小，反映需要装入同一个箱子的部件越集中产出，中间在制品越少；

3） 订单离散性

反映一个订单的电梯部件排产在同一天的情况；

4)WC(Work Center)

工作中心缩写，指的是直接改变物料形态或性质的生产作业单元，以WCk表示第k个工作中心；

5)WCk的利用率

ηk=WCk上的已排工时/WCk的可供工时；

6)WCk欠排利用率密度

ηk欠=（WCk上的可供工时×排产系数-WCk上的已排工时）/（WCk的可供工时×排产系数×剩余可排台数）；

7)WCk累计欠排利用率密度

ηk欠=（WCk上的可供工时×排产系数-WCk上的累计已排工时）/（WCk的可供工时×排产系数×剩余可排台数）；

8)排产系数

计划排产时每天可用系数，完整一天的系数为1.0，假设前旬最后一天已排产当日产能的30%，则后旬第一天的排产系数为0.7；

9)WCk可供工时

WCk可供工时=WCk的可供人数×出勤时间×综合能率；

10)WCk可用可供工时：

WCk可用可供工时=WCk的可供人数×出勤时间×综合能率×排产系数；

11)TS折合比

TS折合比=该工事番号在WCk上的TS/本旬所有工事番号在WCk上的平均TS；

2.2 总体思路

对于一次排程，先计算瓶颈工作中心负荷和设定最大利用率，确定本次投产的订单所需的生产天数，然后读取之前排产的情况，将两者结合后，动态排入一个本次投产中最合适的订单，并刷新负荷，接下来循环执行排入订单与刷新负荷的操作，直到所有订单都被赋予了日期。

2.3 具体步骤

(1)找出投产对象中涉及所有工作中心中，最大与最小单天累积的欠排利用率密度之差最大的工作中心，设为WCk；

(2)从各天中找出工作中心欠排利用率密度最高的一天，设为Day i；

(3)找出对WCk的TS 折合比最大的工事番号，设为Type j；若投产的工事番号对该工作中心TS折合比相同，则找出对其他工作中心TS折合比最大的规格；

(4)将该Type j工事番号排入Day i；

(5)更新本次投产所有工作中心的累计欠排定利用率密度；

(6)重复步骤(1)至(5)，直到所有工事番号都被赋予了排产日期。

3 案例分析

3.1 适用对象

K01箱、K02箱、K03箱、K04箱。

3.2 对象特点分析

(1)K01箱、K02箱、K03箱、K04箱相关部件及其涉及工作中心状况如表1、表2所示。

表1 K01箱情况介绍

表2 K02、K03、K04箱情况介绍

3.3 模型建立

(1)手配方式为整体外协的部件（灰色底色部分），由对应的外协厂结合各自公司产能等实际情况予以考虑；

(2)手配方式为汇总的部件，由制造科室指定专人进行统一作业，通过产能规划予以考虑；

(3)手配方式为内做的部件， K01箱、K02箱、K03箱、K04箱涉及工作中心品目较多，将各品目工作中心分为两类：共线与非共线工作中心。由于后者影响的范围较小，在排产顺序上，先排定非共线工作中心，再排定共线工作中心；

由于大型层门门机数量较少，虽然涉及多道工序，但一定不会成为本次K01排产瓶颈工作中心，在后续排产标准层门门机时，通过装配负荷予以考虑；由于轿门门机对激光机负荷影响有限，一定不会成为本次K01排产瓶颈工作中心，故在后续排产盘式袖壁操作面板时，通过临时外协调整予以考虑；由于轿门门机对特种折弯机，铆接工作中心影响有限，一定不会成为本次8#排产瓶颈工作中心，也同样在标准层门门机排产时予以考虑；

因此可以将原先复杂的排产模型简化，如表3所示。（其中共线工作中心后面用-G表示，非共线工作中心后面用-FG表示）

表3 排产因素简化表

(4)基于以上客观条件，制定排产逻辑如图1所示。

图1 排产逻辑流程图

(5)理论排产效果如图2所示。

图2 排产预期效果图

3.4 详细算法

1）工作中心TS收集

将本次展开BM数据，通过TS和计划模块进行匹配，汇总成以工事番号为单位的各工作中心TS，完成排产基础数据的准备工作；

2）旬分析

通过多能工调配，加班率设定，平衡各个工作中心工作天数与标准工作天数之间差异，满足既定的交货期，通过旬分析中与标准天数的差异及其累计差异，判断计划范围是否符合公司进行状况，并确定多能工调整，加班，调休等措施；

3)排产天数确定

非共线WC天数=各自WC排产天数

共线WC排产天数=MAX（各共线WC天数）

4)分类集合

以工事番号+品目+TS为单位，按照30min为标准将总TS分类集合，集合后名称以品目+该集合最小TS命名，这样便于提升启发式排产的效率；

5)启发式排产

TS折合比计算：

TS折合比=该工番在WCk上的TS/本旬所有工番在WCk上的平均TS

其中，平均TS=∑本旬所有工番在该WCK上的TS/工番数量；

各WC天与天之间利用率差值GAP的计算：

WCk的GAP=MAX(各天ηk)-MIN(各天ηk)；

排产系数即可排天数，由于非共线WC和共线WC的排产天数不同，故排产系数分开设置；

DS设定，指一批物料经过一道加工工序所需要的时间；

非共线WC排产

每个工作中心的利用率=已排工时/（可供工时×排产系数）

排产步骤（终止条件，当有一个WC负荷超过110%时，则终止该天的排产）

当本旬和上旬有交叉时，交叉处的可供工时全部按照上旬的可供工时计算；

修正由于上旬和本旬可供工时差异造成的天数差异：

如果交叉天数大于1天，则分别对每天进行计算，将合计影响天数计入本旬；

设首日系数为a，修正前天数为t，修正后天数为T，前旬可供工时Ga，本旬可供工时Gb，本旬需求TS为Y，则有以下等式；

将式（1）式（2），两式联立，有Gb×a+（t-a）×Gb=Ga×a+（T-a）×Gb

得到修正前后天数之间的关系：

整理成文字性描述为：

修正后的WCk排产天数=本旬WCk排产天数+（1-上旬WCk可供工时/本旬WCk的可供工时）×本旬数首日排产系数；

确定每日排产系数，分成三部分，分别是首日，中间天数和最后一天

首日排产系数=1-上旬末日的排产系数；

中间天数一般为1，如果当中有某几天排产过，参考首日系数的计算及修正方式；

最后一天系数=总排产天数-本旬已确定排产系数之和；

判断各非共线WC的GAP，找出GAP最大的一个WC（如果GAP相同，则选择限速器装配WC）；

选择该WC在TS折合比计算表格中最大的一个类别，在排产表格中找到该WC利用率最小的一天，把该规格中一个的该WC的生产日期标记为该天；

工番选择时，优先选择和当天已排工番相同图号、参数的工番；

根据DS Master，推出各相关WC的生产日期，DS Master如表4所示；

DS（单位为天）样例如下：通过以下DS直接推出工艺线路中各WC的生产日期，如表4所示。

表4 DS推算设定表

刷新排产表格（全表格刷新），如此重复，直到排产表格中各规格全部排完；

修正排产系数不是1的该天的利用率显示，也就是下次排产的首日系数a；

显示利用率=计算出利用率×本旬排产系数。

6）共线WC排产

排产步骤（终止条件，当有一个WC负荷超过110%时，则终止该天的排产。）

当本旬和上旬有交叉时，交叉处的可供工时全部按照上旬的可供工时计算；

修正由于上旬和本旬瓶颈WC可供工时差异造成的天数差异；

修正后的瓶颈WC天数=本旬瓶颈WC排产天数+（1-上旬瓶颈WC可供工时/本旬瓶颈WC的可供工时）×本旬首日排产系数，如果交叉天数大于1天，则分别对每天进行计算，将合计影响天数计入本旬；（推导过程与非共线一致，不再推导）；

计算共线WC的瓶颈WC排产天数：

先计算共线WCk的初始需求天数设为T'k，由于初始非共线WC的排产天数与共线WC的排产天数存在差异，当非共线WC排入后，共线WC的天数相应发生变化；

设变化后的排产天数为Tk，则Tk=Tk’-∑非共线WCk利用率；

瓶颈WC的天数=MAX（Tk）

确定每日排产系数，系数的分类和确定方法与非共线一致；

判断各共线WC的GAP，找出GAP最大的一个工作中心（如果GAP相同，则选择机械剪板WC）；

选择该WC在TS折合比计算表格中最大的一个类别，在排产表格中找到该WC利用率最小的一天，把该规格中一个工番的该WC的生产日期设定为该天，工番选择时，优先选择和当天已排工番相同图号、参数的工番；

根据DS Master，推出各相关WC的生产日期，样例参考非共线；

DS有无判断条件，该WC有TS则有，否则则无；

如果TS为0，有可能是内外内的工艺线路，需要进行DS推算。

刷新排产表格（全表格刷新），如此重复，直到排产表格中各规格全部排完；

修正排产系数不是1的该天的利用率显示，修正方式同非共线。

由于限速器、安全钳装配、导靴装配有同期性要求，故在进行启发式排产的时候进行捆绑处理。

整体外协品目排产：由于整体外协品目与内做品目有同期性要求，故采取将整体外协跟随内做品目的排产方法。

小日程的输出顺序：以日期为第一优先级，图号和参数为第二第三优先级，这样利于工段集中生产。

表5 排产结果对比表

图3 箱内同期性对比折线图

4 效果评价与对比

对当年12月份的订单按照两种方式进行了模拟排产，并将结果按照箱内同期性、订单离散性、计划负荷波动性以及排程时间，分别进行了对比，数据如下：

首先，不难看出，通过引入APS排程，箱内同期性从原来的平均0.92天下降为平均0.11天，约每天减少生产现场40箱左右的装箱区域在制品堆积，极大地缓解了该区域的装箱成套性；

并且，对参与模拟的100个工事番号制成如图3所示折线图，横轴代表工事番号的序号，纵轴代表箱内同期性的天数，可以明显看出箱内同期性从原先的高位大幅度震动，转变为低位的小幅度震动，由此得出，在箱内同期性上，APS排程相比MRP排程有了极大的改善，排产结果对比如表5所示。

其次，对改善前后的计划负荷的波动性制成如图4所示统计图，计划波动从原来的峰谷波动12%，下降到峰谷波动4.6%，总共下降了7.4个百分点，极大地提升了生产的稳定性和可操作性。

图4 排产负荷峰谷统计图

最后，排产时间方面，从原来的纯手动排产120分钟，下降到人工调整排产基础数据20分钟，系统运算4分钟，总共24分钟，排产用时缩短了五分之四，极大提升了排产效率。

综上所述，APS排程相比于原来的手动排程，在订单离散性上有一定改善，而在工作中心负荷波动性箱内同期性，计划排程时间，这三项指标上有十分明显的改善。

5 结语

本文展示的方法既满足了多品种部件的同期性要求，又兼顾每日产出台数及其工作中心负荷，在生产计划领域具有一定的普遍适用性。

但是，阶段性成功的背后也客观地看到：

(1)由于多能工调配逻辑难以构建等问题，导致存在瓶颈工序的共线多工序部件，在瓶颈工序负荷排满后，其余工序负荷还有空余；

(2)没有考虑短交货项目插单对标准工期的排产项目影响。

今后会带着这些问题对现有排程逻辑做进一步的优化，完善APS排产的逻辑，提升企业的生产管理科学性。