两台机器下的流水车间调度算法与程序实现

关键词：生产调度；流水车间调度；精确求解算法

中图分类号：TP311 文献标识码：A

文章编号：1009-3044（2024）18-0043-04

0 引言

自动化技术的广泛应用让制造业的发展呈现出井喷式的增长。这加剧了竞争的压力，也创造了无数机会。企业要抓住这些机会，就必须不断提高自己的核心竞争力，例如依靠科学的管理模式[1]就是其中重要的一环。在科学的管理模式中，如何更加高效率、低消耗地实现生产调度[2]是其中一个最为核心的问题。因此，加大对生产调度的研究不仅具有重要的学术价值，而且对当前的全球化市场而言有着巨大的商业价值。

本文使用Johnson算法[3]研究了生产调度中的一类典型问题——两台机器下的流水车间调度问题[4]。Johnson算法属于精确求解算法，其步骤原理经过严格的数学证明。通过使用Johnson算法编程，最终可以得到最短完工时间及最优加工顺序。

1 两台机器下的流水车间调度问题

1.1 问题描述

n个工件在两台机器（下面简称机器A和机器B） 上流水加工。每个工件在机器A和机器B上加工所需时间已知。每台机器一次只能加工一个工件，并且每个工件最多只能在一台机器上加工一次。问题要求得到最短完工时间及其最优加工顺序。

1.2 Johnson算法的原理思想

设有机器A和B两台，有工件n件，每个工件在每台机器上的加工时间已知。Ai、Bi 分别表示第i件工件在机器A、机器B上的加工时间。要获得最短完工时间下的最优加工顺序，必须满足Johnson定理。下面对Johnson定理进行解释和证明。

Johnson定理：在最优加工顺序下，工件j在工件j+1之前加工需满足以下条件：