带传递时间的通信模型中的树约束排序问题

作     者：马蕾 

作者单位：兰州大学 

学位级别：硕士

导师姓名：王海明

授予年度：2007年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

主      题：排序 拟传递时间 算法复杂性 多项式时间归结 出树 

摘      要：本文主要讨论一类平行机带传递时间，且任务的先后加工顺序约束于一棵出树，目标函数为极小化时间表长的排序问题。即 P|pseudo-delivery times，outtree|C。 首先给出排序问题P|pseudo-delivery times，outtree|C的一个实例排序问题(k-OPTS)。通过将背包问题(KNP)归结为限制背包问题(k-KNP)，将限制背包问题(k-KNP)归结为排序问题(k-OPTS)来证明排序问题P|pseudo-delivery times，outtree|C是NP-完全的。然后给出了适合所有情况的启发式算法，并证明了算法的复杂性为O(n)。进而对任务数小于机器数的特殊情况给出了一个启发式算法，并证明了算法的最优性及算法复杂性为O(nβ／log n)。