给定2台并行专用机器,每个作业都有专有的机器进行加工,资源的有限性导致属于不同机器的作业之间相互冲突,即相互冲突的作业不能同时加工。对于极小化作业最大完工时间的目标函数,即使其中1台机器上作业的加工顺序已确定,该问题仍然是NP-难的。在其中1台机器上作业加工顺序已经确定的情况下,为了使机器完工时间尽可能小,该文引用贪婪算法,设计了求解此问题的多项式时间近似算法,并从理论上证明了算法的近似比为5/3,且给出相关紧例。
科研之友
微信
新浪微博
Facebook
分享链接
