公开(公告)号：CN107392384B

公开(公告)日：2020-10-16

申请号：CN201710628582.1

申请日：2017-07-28

Applicant: 东北大学

Inventor： 付尧 ,  崔晓智 ,  刘冰倩 ,  唐梦倩 ,  白丹宇 ,  任涛

IPC: G06Q10/04 ,  G06Q10/06

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

公开(公告)号：CN107392384A

公开(公告)日：2017-11-24

申请号：CN201710628582.1

申请日：2017-07-28

Applicant: 东北大学

Inventor： 付尧 ,  崔晓智 ,  刘冰倩 ,  唐梦倩 ,  白丹宇 ,  任涛

IPC: G06Q10/04 ,  G06Q10/06

CPC classification number: G06Q10/04 ,  G06Q10/06316

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