摘要
研究一类具有线性恶化效应的单机在线分批排序问题,工件乃的加工时间为Pj=bj-αt,其中bj为基本加工时间,α〉0为恶化率,t是开工时间.工件的到达时间是未知的,工件的基本加工时间只有在工件到达之后才能知道.多个工件可以作为一批被机器同时加工,批的加工时间为该批中工件最大加工时间.对于目标为极小化makespan的批容量无限的单机问题给出一个在线算法βH^∞,并证明其竞争比和问题的下界相同,进而算法是最优的.
An online batch scheduling chine is considered. Jobs arrive over time. with linear deterioration effect on single ma A batch processing machine can handle up to B jobs simultaneously. The actual processing time pj of Job Jj is assumed to be a linear function of its starting time t, i.e., pj = bj + αt, where α 〉 0 is the deterioration ratio, bj is the basic processing time, which is unknown until it arrives. The processing time of a batch is given by the longest processing time of any job in the batch. For single machine with unbounded capacity to minimize makespan problem, we give an optimal online algorithm, which competitive ratio matches the lower bound of the problem.
出处
《运筹学学报》
CSCD
2011年第3期107-114,共8页
Operations Research Transactions
基金
国家自然科学基金(71101081
70971076
11071142)
山东省自然科学基金(ZR2011AL017
ZR2010AM034)
山东省"泰山学者"建设工程专项经费(曲阜师范大学应用数学)
关键词
分批排序
恶化效应
竞争比
在线算法
batch scheduling, deterioration effect, competitive, online algorithm