具有线性恶化效应的在线分批排序问题

Online Batch Scheduling with Linear Deterioration Effect

研究一类具有线性恶化效应的单机在线分批排序问题，工件乃的加工时间为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.