2台并行机上的批在线调度

Batch on-line scheduling on two parallel machines

针对在2台同构并行机上的批在线调度问题,将经典在线调度中工件顺次到达的列表调度,推广为批在线列表调度,其目标函数是使最大完成时间(makespan)最小.给出了一个批在线启发式算法(BLPT-算法),要求在每一个批中的工件按LPT规则调度.证明了该算法的竞争率为3/2,并给出了该算法的一个实例.

Aiming at the batch on-line scheduling on two identical parallel machines, extends the classical on-hne scheduling in which jobs arrive one by one, to batch on-line scheduling in which jobs arrive by batch, its object function is to make maximum completion time minimum. Give a heuristic BLPT-algorithm, it requires scheduling jobs in every batch by LPT rule. Proves the competitive ratio of this algorithm is 3/2, gives a example as well as.