流水车间调度与最短路径问题的结合-研究论文

本文研究了结合流水车间调度问题和最短路径问题获得的组合优化问题。 获得的问题的目的是选择构成最短路径问题的可行解决方案的作业的子集，并在流水车间的机器上执行所选的作业以最小化制造时间。 我们认为，即使机器数量为2，这个问题也是NP难题，而从一般意义上讲，这个问题在很强的意义上是NP难题。 对于机器数量为输入的情况，我们提出了一种直观的近似算法，对于固定数量的机器，我们提出了一种改进的近似算法。