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

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

面向流程工业的批在线调度问题

从钢铁生产热轧流程中提炼出了在同构并行机上的批在线调度问题,它是流程工业中MES的重要环节。从理论上给出算法并研究了算法的性能。工件以批的形式到达,目标函数是使工件的最大完成时间最小。当一个批到达时,将这一批中的工件分成若干组,要求在同一组中的工件可以具有不同的开始加工时间但必须具有相同的完成时间。通过将批调度与在线调度的结合,给出了最坏情况比(竞争率)分别为m/(1+(m-1)ε),m(1-ε)/(1-εm),m/(1+gε)的批在线调度算法。

工件具有区间限制的批在线调度

研究同构并行机上的批在线调度问题,目标函数是使最大完成时间(最后一个工件的完成时间makespan)最小.工件以批方式到达且每个批中有m个工件,每个工件的加工时间随其批的到达而给定且限定在某个时间区间上.当一批工件到达时,在对其后批的信息不了解的情况下,要立即对该批中的工件进行调度,调度过程中不允许中断.针对这一问题,给出了一个批在线启发式列表调度算法,在同一批中的工件按LPT规则调度,当一批中的全部工件被调度完后,调度下一批中的工件.对算法的最坏情况进行了分析并给出了算法的竞争率.

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

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