具有服务等级的三台平行机排序问题
考虑带服务等级的三台平行机排序问题.预先赋予每台机器和每个任务一个服务等级(grade of service)标号.每个任务只能被某台服务等级不高于该任务服务等级的机器加工.目标是最小化最大机器完工时间.本文给出了求解这个问题的算法.并证明算法的最坏情况界不超过5/4+(1/2)k,其中k是算法中预先给定的迭代次数.已有的算法仅为3/2.
作 者: 周萍 蒋义伟 华荣伟 ZHOU Ping JIANG Yi-wei HUA Rong-wei 作者单位: 周萍,ZHOU Ping(浙江大学,数学系,浙江,杭州,310027)蒋义伟,JIANG Yi-wei(浙江理工大学,理学院,浙江,杭州,310018)
华荣伟,HUA Rong-wei(浙江医学高等专科学校,浙江,杭州,310053)
刊 名: 浙江大学学报(理学版) ISTIC PKU 英文刊名: JOURNAL OF ZHEJIANG UNIVERSITY(SCIENCE EDITION) 年,卷(期): 2007 34(4) 分类号: O223 关键词: 服务等级 最坏情况界 FFD算法 Muhifit算法