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

多机Flow Shop加权完成时间调度问题的渐近最优算法研究
引用本文:古春生,陈华平,卢冰原,谷峰.多机Flow Shop加权完成时间调度问题的渐近最优算法研究[J].计算机科学,2006,33(5):231-233.
作者姓名:古春生  陈华平  卢冰原  谷峰
作者单位:1. 江苏技术师范学院计算机科学与工程学院,常州213001;中国科学技术大学商学院,合肥230052
2. 中国科学技术大学商学院,合肥230052
基金项目:安徽省自然科学基金;中国科技大学校科研和教改项目
摘    要:最近Chou、Queyranne和Simchi—Levi,Liu分别证明了恒速平行机调度问题和Flow shop调度问题的基于有效作业加权最短处理时间的启发式算法是渐近最优的。本文使用分组机器模型的方法证明:即使对于多机Flow shop加权完成时间调度问题,基于有效作业加权最短处理时间的启发式算法也是渐近最优的。关键词调度,多机Flow shop调度,启发式算法,渐近最优分析

关 键 词:调度  多机Flow.shop调度  启发式算法  渐近最优分析

Asymptotically Optimal Algorithm for the Multiprocessor Flow Shop Weighted Completion Time Scheduling Problem
GU Chun-Sheng,CHEN Hua-Ping,LU Bing-Yuan,GU Feng.Asymptotically Optimal Algorithm for the Multiprocessor Flow Shop Weighted Completion Time Scheduling Problem[J].Computer Science,2006,33(5):231-233.
Authors:GU Chun-Sheng  CHEN Hua-Ping  LU Bing-Yuan  GU Feng
Abstract:Recently,Chou,Queyranne,Simchi-Levi and Liu respectively prove that the heuristics based on weigh- ted shortest processing time among the available jobs are asymptotically optimal for the uniform parallel machine and the flow shop problem scheduling problems.By grouping this machine setting,this paper proves that the heuristic based on weighted shortest processing time among the available jobs is also asymptotically optimal,even for the multi- processor flow shop weighted completion time scheduling problem.
Keywords:Scheduling  Multiprocessor flow shop scheduling  Heuristic algorithm  Asymptotically optimal analysis
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《计算机科学》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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