可自由离线批处理机最小化加权完工时间和排序

摘要

批处理排序是排序领域中一类重要问题。批处理是指处理机可以同时将b个工件作为一批,在相同的批开工时间同时加工。对于输入的n个工件,要求将n个工件安排到若干批中,并且决定这些批的开始加工时间,使得给定的目标函数值最小。
　　 在本文中,工件具有自由离线的性质,目标函数是总加权完工时间。工件可自由离线(item—availabili锣)是指,同一批中的每个工件完工时间等于该批的开工时间与该工件的加工时间之和。
　　 本文对完工工件可自由离线的单台批处理机最小化加权完工时间和排序的在线和离线情况分别做了研究。在线情形下,对于批容量无限(b=+∞)的模型,给出了一个竞争比是2+α的柔性算法(α=√5-1／2),并证明了该竞争比是紧的(tight)。对于容量有限(b