论文部分内容阅读
考虑图形处理中的一类两台处理器上的Flow-shop调度问题,目标是极小化最早完工时间.每个任务包含两道工序,第一道工序可以在两台处理器中的任何一台上处理,而第二道则只能在第二台处理器上处理,且必须在第一道工序完工之后才能进行.对该问题,设计了一个改进的多项式时间近似算法,在绝对性能方面,该算法的最坏情况界为3/2;而从实例计算的平均效果方面,该算法所得的结果比原有的贪婪算法所得的结果要好20%左右.