一种基于带有释放时间流水车间的双代理问题的下界求解方法

摘要

本发明属于生产调度领域，提出了求解NP难问题下界的方法，即一种基于带有释放时间流水车间的双代理问题的下界求解方法，下界即为松弛掉一些约束的排序所求得的解，所用算法的排序求解得一个可行解即上界，排序的最优解则介于上界与下界之间。因此下界作为一种评价算法求解性能的重要手段。该发明所设计的下界使用了基于单机问题的方法，即在每台机器上都求得一个下界，最后取大。并在每台机器上采用了可中断的方式来松弛约束条件。由仿真结果可得，下界是收敛的，即当工件数趋于无穷大的时候，下界收敛于最优解。在大规模情况下，这对于评价算法求解性能具有很大意义。