关于平行机排序问题的两点注记

【摘要】 <正> 本文考虑了有完工约束的平行机排序问题,证明了问题 pm|T|∑c_i是 NP-完全的,而对问题 pm|T,[_i≡p|∑w_ic_i 提出 O(n~2)的算法,并证明其最优性.将 n 个互相独立的工件(工件集 N={1,2,…,n))放在 m 台等速率平行机(机器M={M_i,…,M_m})上加工.已知每个工件必须且仅须在一台机器上加工一次,并且加工时不允许中断.工件 i(i∈N)在不同机器上加工时间不变,设为 p_i,罚权 w_i 也与机器无关,p_i 和 w_i 皆为非负实数.我们将多台机器加工工件的一个安排称为一个时间表.当时间表π确定后,记工件 i 的完工时间为 c_i(π更多还原