NDP约束下的最小化最大加权完工时间单机一致性在线排序问题研究

摘要

本文在工件不能被强制推迟加工约束(即NDP约束)下研究最小化最大加权完工时间单台机器在线排序问题。每个工件Jj都具有一个释放时间rj≥0,一个加工时间pj≥0和一个权重wj≥0。每两个工件Ji和Jj的释放时间与加工时间均具有一致性,即若ri≥rj,则有pi≥pj。我们首先利用对手法构造出该排序问题的下界是1.5,其次设计出一个在线算法SLF并采用最小反例法证明其争比是1.732。