论文部分内容阅读
研究一类具有线性恶化效应的单机在线分批排序问题，工件乃的加工时间为Pj=bj-αt，其中bj为基本加工时间，α〉0为恶化率，t是开工时间．工件的到达时间是未知的，工件的基本加工时间只有在工件到达之后才能知道．多个工件可以作为一批被机器同时加工，批的加工时间为该批中工件最大加工时间．对于目标为极小化makespan的批容量无限的单机问题给出一个在线算法βH^∞，并证明其竞争比和问题的下界相同，进而算法是最优的．