【导语】以下是小编整理了加工时间线性递减的平行机排序问题（共3篇），希望你喜欢，也可以帮助到您，欢迎分享！
篇1：加工时间线性递减的平行机排序问题
加工时间线性递减的平行机排序问题
主要讨论了具有两台处理机的平行机排序问题和每批恰为k个工件的串行工件同时加工排序的平行机排序问题.在这两个问题中,工件加工时间均为开工时间的线性递减函数,目标函数为极小化总完工时间.对于第一个问题,证明了其最优排序可由工件按基本加工时间不减排列得到,由此得出其最优算法,并指出了该结论对于加工时间随开工时间线性递增的.情况并不成立.对于第二个问题,根据其与第一个问题在某些性质上的相似性,给出了其最优算法.最后指出所讨论的两个问题的结论均可推广到m台处理机的情况.
作 者：李俊杰 赵传立 作者单位：沈阳师范大学数学与系统科学学院,辽宁,沈阳,110034 刊 名：系统工程与电子技术 ISTIC EI PKU英文刊名：SYSTEMS ENGINEERING AND ELECTRONICS 年，卷(期)： 30(7) 分类号：O223 关键词：排序 平行机 串行工件同时加工排序 线性递减 总完工时间篇2：具有服务等级的三台平行机排序问题
具有服务等级的三台平行机排序问题
考虑带服务等级的三台平行机排序问题.预先赋予每台机器和每个任务一个服务等级(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) 年，卷(期)： 34(4) 分类号：O223 关键词：服务等级 最坏情况界 FFD算法 Muhifit算法篇3：具有特殊工件的平行机在线排序问题
具有特殊工件的平行机在线排序问题
本文研究一类具有特殊工件的平行机在线排序问题,目标是最小化最大完工时间.此模型有两种工件:正常工件和特殊工件.正常工件能够在m台平行机的任何一台机器上加工,而特殊工件仅能够在它唯一被指定的机器上加工.文中所有特殊工件的指定机器为M1.我们提供了竞争比为(2m2-2m+1)/(m2-m+1)的在线近似算法.当m=2时,算法是最好可能的.当m=3时,算法的'竞争比为13/7≈1.857,并且提供了竞争比的下界(1+(平方根33))14≈1.686.
作 者：刘瑞芳 Liu Ruifang 作者单位：Department of Mathematics, East China Normal University, Shanghai 200241, China 刊 名：运筹学学报 ISTIC PKU英文刊名：OPERATIONS RESEARCH TRANSACTIONS 年，卷(期)：2008 12(3) 分类号：O22 关键词：运筹学 平行机排序 列表在线 特殊工件 竞争比 Operations research parallel machine scheduling on-line-list special jobs competitive ratio
文档为doc格式