工件具有加工位置上限最小化加权总误工量的单机排序问题

摘要

考虑工件具有加工位置上限最小化总加权误工量的单机排序问题.在此排序问题中,每个工件Jj都具有一个加工位置上限(k)j.也就是说,如果工件Jj是一个可行排序中的第x个工件,那么就需要满足x≤(k)j.证明了(i)当工件具有相同工期时,该排序问题是二元NP-难的并且是拟多项式时间可解的,(ii)当工件具有单位权重时,该排序问题是一元NP-难的.