10.3969/j.issn.1007-6093.2011.03.013
具有线性恶化效应的在线分批排序问题
研究一类具有线性恶化效应的单机在线分批排序问题,工件Jj的加工时间为Pj=bj +αt,其中bj为基本加工时间,α>0为恶化率,t是开工时间.工件的到达时间是未知的,工件的基本加工时间只有在工件到达之后才能知道.多个工件可以作为一批被机器同时加工,批的加工时间为该批中工件最大加工时间.对于目标为极小化makespan的批容量无限的单机问题给出一个在线算法βH∞,并证明其竞争比和问题的下界相同,进而算法是最优的.
分批排序、恶化效应、竞争比、在线算法
15
O223(运筹学)
国家自然科学基金71101081,70971076,11071142;山东省自然科学基金ZR2011AL017,ZR2010AM034;山东省“泰山学者”建设工程专项经费
2012-02-21(万方平台首次上网日期,不代表论文的发表时间)
共8页
107-114