机器有等待的工件具有区间限制两台同构并行机上批在线调度

摘要

研究两台同构并行机上的批在线调度问题,工件以批方式到达且每个批中有m个工件,每个工件的处理时间限定在一个区间上,只有当前批中工件全部加工完成后才可以加工其后面的工件,目标函数是使最大完成时间最小.针对这一问题,给出了1个批在线启发式调度算法,在同一批中的工件按LPT规则调度.对算法的最坏情况进行了分析并给出了算法的最坏情况比与批中工件数有关,并由计算机程序进行了验证.