两类极小化最大加权完工时间排序问题研究

摘要

研究两个单机排序问题,目标函数均是最大加权完工时间。对于问题1‖maxwjcj,证明了LW规则序是最优排序,而问题1|rj|maxwjcj,用3-划分问题归结,证明是强NP困难的。