生产计划排程中 [算法] 对比

【1】前言

据相关统计,中国中小企业数量占据企业总数比例高达90%以上。中小企业的生产特点为多品种、小批量。

对于多品种、小批量生产模式的企业，生产计划排程是个难题，因为品种多，计算量大，而批量小又会导致换线频繁。APS是英文advanced planning and scheduling的缩写，翻译过来就是高级计划与排程，它是运用计算机技术实现对生产计划的自动排程。

计算机程序可以认为是算法和计算机语言语法的集合体。越复杂的计算问题，算法也越复杂。生产计划排程是非常复杂的问题，开发一套APS系统，算法方面是最大的难点。本文对生产计划排程的算法做一探讨。

生产计划排程既有相对简单的算法，例如，最短交货期算法，最短工序算法等，也有复杂的算法，例如，神经网络、模拟退火法、遗传算法、禁忌搜索法等。

复杂算法遗传算法是对非线性问题求出比较好的可行解，但计算量很大。一些理论上的最优化方法能提供最优排程，但由于其计算的复杂性，并且忽略了很多实际因素，离实际运用还有较大距离。

笔者认为简单算法较好，因为一般企业的数据计算量非常大，而且整个生产现场的形势不断变化，排程要在极短的时间内算出结果，最好在几分钟内完成计算。如果整个计算过程耗时过长，也就失去了它的指导意义，因此时间因素非常重要。

简单算法可以根据特定的问题设定特定的规则，相对来说是计算快速，比较实用的算法。另一方面，也不是算法越复杂，排程结果就越好，本文通过对四种简单算法的比较计算也可以看出该问题。

【2】四种简单算法的比较

本段对4种简单的排程算法进行比较计算。这些年的研究资料表明生产计划排程并不存在一个全局最优的排程规则，也不是算法越复杂结果就越好，这一点通过下面一个例子对4种简单算法进行计算就可以得到验证，这4种简单算法中计算复杂性稍有不同，并不是算法越复杂排程结果就越好。

要做比较计算的4种算法（计算的复杂性依次递增）是：

（1）最短工期

（2）最早交货期

（3）按照工期和交货期之间的距离

（4）CR值

下面借用一个例子，见下表。比较这4种算法的排程结果，我们按照作业逾期天数为评价标准。

1.1 按照最短工期的排程 

1.2 按照交货期先后排程

1.3  按照工期和交货期之间的距离排程

1.4  按照CR值排程

CR是英文critical ratio的缩写，可以翻译为重要比率。它的计算方法：交期减去目前日期之差额,再除以工期，数值越小表示紧急程度越高，排程优先级高。

上面4种算法中，最短工期法是最简单的，它不考虑各个作业的交货期先后，先排工期短的作业，再排工期长的作业，但对于我们随便给定的例子，它的总逾期天数是最少的，当然不能说所有例子它的总逾期天数都是最少的，这里面有偶然性。

这个例子也说明了，不意味者计算最简单的算法结果是最差的。企业在生产计划排程时，可以根据其计算能力选择合适的算法。

【3】正排和倒排的选择

生产计划排程时选择了排程的算法之后，是正排还是倒排也是一个重要问题。正排指的是按照预定的算法尽可能紧前安排，倒排指的是尽可能紧后安排。

用上一段的例子，如果是用最短工序算法排程的话。正排的结果如下图:

如果是倒排，如果还没有到最后期限，会是下面的排程结果：

正排的优点是设备和人会得到充分利用，设备闲置或人员休息，也要等生产任务都完成后，可能会因为提前完成生产任务，没有到交货期不能发货而形成库存。

倒排的优点和缺点正好相反，倒排是在最后期限前完成任务，库存最小化，但前期人员和设备可能会有闲置。

笔者所在企业为一机械加工企业，机械加工也是一个应用广泛的行业。就以本企业为例，谈一下正排和倒排的影响。

本企业有设备几百台，包括了数控车床，加工中心，普通车床，钻床，铣床，磨床等。这些设备中数控车床和加工中心是瓶颈设备，它们也是设备中价格昂贵的设备。在排产时，充分利用瓶颈设备产能是个重要课题。

在激烈竞争的市场环境下，企业的投资都需要得到充分利用，企业才能降低生产成本，取得利润维持生存。如果企业有大量资产闲置，生产计划排程容易了很多，但企业投资浪费，可能导致企业严重亏损，这不是企业经营者希望的局面。

一般说来，当企业需要考虑上APS系统解决企业生产计划排程问题时，面临的情况都是多品种，小批量，设备能力不足，需要更合理的调度安排。正排增加库存，倒排浪费产能，如何取舍？

笔者认为：在增加库存和浪费产能之间取舍，浪费产能造成的损失大大超过增加库存，原因有二：

一，设备是有故障的，而故障又是偶发的，无从判断何时设备会出现故障。如果生产安排是时，进行倒排，按照库存最小化的时间点安排，如果在生产过程中出现设备故障，就没有多余的缓冲时间用于检修设备，势必造成延迟了交货期。

二，设备产能浪费属于彻底浪费，如果当月设备能力浪费了，以后也无法再追回；而增加库存造成的浪费则属于一种临时的浪费，如果当月积压了库存，而下个月客户订单增加，正好将这些库存利用，避免了加班。笔者观点，对于一般性行业，正排是正确的选择。

【4】总结

笔者就职于一个机械加工企业，生产过程是典型的多品种，小批量和设备能力紧张。

算法并不是复杂性越高，得到的计算结果越好。企业在生产计划排程时，可以结合实际情况，选择合适的排程算法。对于正排还是倒排的问题，对于一般性行业，正排是正确的选择。