首页 | 本学科首页   官方微博 | 高级检索  
     检索      

具有服务等级的三台平行机排序问题
引用本文:周萍,蒋义伟,华荣伟.具有服务等级的三台平行机排序问题[J].浙江大学学报(理学版),2007,34(4):378-383.
作者姓名:周萍  蒋义伟  华荣伟
作者单位:1. 浙江大学,数学系,浙江,杭州,310027
2. 浙江理工大学,理学院,浙江,杭州,310018
3. 浙江医学高等专科学校,浙江,杭州,310053
基金项目:浙江省自然科学基金资助项目(Y605316)
摘    要:考虑带服务等级的三台平行机排序问题.预先赋予每台机器和每个任务一个服务等级(grade of service)标号.每个任务只能被某台服务等级不高于该任务服务等级的机器加工.目标是最小化最大机器完工时间.本文给出了求解这个问题的算法.并证明算法的最坏情况界不超过5/4+(1/2)^k,其中k是算法中预先给定的迭代次数.已有的算法仅为3/2.

关 键 词:服务等级  最坏情况界  FFD算法  Muhifit算法
文章编号:1008-9497(2007)04-378-06
修稿时间:2005-12-26

Parallel scheduling on three machines under a grade of service provision
ZHOU Ping,JIANG Yi-wei,HUA Rong-wei.Parallel scheduling on three machines under a grade of service provision[J].Journal of Zhejiang University(Sciences Edition),2007,34(4):378-383.
Authors:ZHOU Ping  JIANG Yi-wei  HUA Rong-wei
Institution:1. Department of Mathematics, Zhejiang University, Hangzhou 310027, China ; 2. Faculty of Science, Zhejiang Sci-Tech University, Hangzhou 310018, China ; 3. Zhejiang Medical College, Hangzhou 310053, China
Abstract:Parallel scheduling problem on three machines with a grade of service provision is introduced.That process service requests from various customers who are entitled to many different grade of service(GoS) levels.Hence,each job and machine are labelled with prespecified GoS levels,and each job can be processed by a particular machine only when the GoS level of the job is not less than that of the machine.The objective is to minimize the maximum machine completion time.For this problem,an algorithm with a worst-case ratio of 54+12k is presented,where k is the desired number of iteration,which has improved the known result 32.
Keywords:grade of service  worst-case ratio  FFD algorithm  Multifit algorithm
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《浙江大学学报(理学版)》浏览原始摘要信息
点击此处可从《浙江大学学报(理学版)》下载免费的PDF全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号