我要投稿 查看投稿进度
学术期刊
在线客服
客服电话：400-188-5008
客服邮箱：service@ccnpub.com
投诉举报：feedback@ccnpub.com
人工客服

工作时间（9：00-18：00）
官方公众号

科技成果·全球共享

请选择 目标期刊

一类带平行机的两阶段柔性流水调度近似算法 下载：56 浏览：350

张明会1,2 韩鑫1 《数学应用》 2018年3期

摘要:
本文研究一类柔性流水调度与平行机调度相结合的两阶段流水调度模型,模型中第1阶段有1台机器,第2阶段有m台同构并行机,每个任务在第2阶段需要sizei台机器同时并行执行.目标是所有任务都完成的完工时间最小化.该模型已被证明出是强NP难的,并给出了在某种特定情况下近似比为3的近似算法.本文首先详细分析了前人近似算法基本过程,给出该算法近似比分析的局限性;接着给出了一个近似比为3的算法,摒弃了前人给出的近似比为3时的约束条件;最后研究了当第2阶段机器数为2和3时的两种特定情况,采用列表调度思想,给出了近似比为2.5和2.67的近似算法.
[1/1]
|<
<
1
>
>|
在线客服：：点击联系客服
联系电话：：400-188-5008
客服邮箱：：service@ccnpub.com
投诉举报：：feedback@ccnpub.com
人工客服

工作时间（9：00-18：00）
官方公众号

科技成果·全球共享