论文部分内容阅读
本论文主要就以下两方面的问题进行了研究。首先，目标函数是最大完工时间情形，当图G是一般二部图、完全二部图、完全m部图、直径不超过4的树以及分裂图时，分别给出了排序问题的多项式时间的算法。具体结论如下：
(1)排序问题1|p-batch；G|Cmax的判定问题是NP-完全的。
(2)当把图G限定为一般二部图G=(X，Y；E)，X={p1,…，pm}，Y={q1,…，qn}时，其中pi，qj(对所有的i，j)也表示相应工件的加工时间，则对问题1|p-batch；bipartite|Cmax给出了多项式算法，使得在O(n3)时间内给出问题的最优排序。
(3)给定完全二部图G=(X，Y；E)，其中X={p1,…，pm}，Y={q1,…，qn}，而pi，qj也分别代表相应的工件的加工时间。不失一般性，我们假定m≤n。这种情况下给出了时间界为D(nlogn)的多项式算法，使得在该时间内给出排序问题1|p-batch；completebipartite|Cmax的最优排序。
其次，研究了目标函数是批的完工时间和情形，即1|p-batch；G|ΣC(Bi)，讨论了目标函数为批的完工时间和情形，其中ΣC(Bi)表示批的完工时间和。给出了两个基本结果：
(1)排序问题1|p-batch,pj=1；G|ΣC(Bi)的判定问题是NP-完全的。
(2)排序问题1|p-batch,pj=1；bipartite|∑C(Bi)存在O(n2)算法。