具有前瞻区间和不相容工件族的流水车间在线排序问题

研究对多台单位流水车间上具有前瞻区间的不相容工件族无界批处理的在线排序问题。通过组合优化的方法分类讨论得到问题的下界，对算法Am（β）进行了竞争比分析说明这是该问题最好可能的在线算法。给出了该问题的下界为1+η，其中η是方程(2f－1)η2+(f+β)η+β－f=0的一个正根，这里0≤β<1。同时提供了一个最好可能的在线算法Am（β）。通过竞争比分析说明了算法的可行性。