图形处理中一类Flow-shop问题的改进算法

作     者：蒋义伟 魏麒 

作者机构：浙江理工大学理学院杭州310018 浙江大学宁波理工学院宁波315100 

基　　金：国家自然科学基金(11001242 11071220) 浙江省自然科学基金(Y6090175 Y6090554)资助 

出 版 物：《自动化学报》 (Acta Automatica Sinica)

年 卷 期：2011年第37卷第11期

页      码：1381-1386页

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

主 题 词：调度 近似算法 最早完成时间 流水作业 

学科分类：08[工学] 080203[080203] 0802[工学-机械学] 

核心收录：

D　O　I：10.3724/sp.j.1004.2011.01381

馆 藏 号：203479996...