工件允许重启的平行分批在线排序研究
排序论是运筹学与组合最优化的重要分支.分批排序是人们十分关注的现代排序模型;其特点是可将工件分批进行加工,每一批工件具有相同的开工时间和相同的完工时间.在本文研究的平行分批排序模型中,每一批的加工时间等于该批中工件的最长加工时间.按照每一批可以加工的工件数目b的限制(称为批容量),平行分批排序又可分为批容量有限(b<∞)和批容量无限(b=∞)两种情形.在线排序问题是近年来排序论研究的热点方向;其特点是工件的信息事先并不确定,决策者在没有获得所有工件信息之前就必须对已有工件进行排序.本文所研究的在线排序是工件实时到达(over time)的情形,即工件是随着时间逐渐到达的.工件的所有信息在其到达时刻才能获知.针对在线优化问题设计的算法称为在线算法.人们常用竞争比来衡量在线算法性能的好坏.对于一个极小化目标函数的优化问题,我们称一个在线算法是ρ-竞争的,如果对于该问题的任意实例,算法所产生的目标函数值不大于最优离线算法所产生的目标函数值的ρ倍.在线算法A的竞争比定义为ρA=inf{ρ:A是ρ-竞争的}.不难看出,ρA总是大于等于1的.由于信息的缺乏 ...