加载中…
个人资料
GreenSim团队
GreenSim团队
  • 博客等级:
  • 博客积分:0
  • 博客访问:448,622
  • 关注人气:680
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

并行设计子任务调度的遗传算法MATLAB源代码

(2012-09-01 20:04:33)
标签:

it

杂谈

知识/探索

    在研究并行设计环境下设计子任务的调度问题时,针对该问题的描述所给出的假设往往各不相同不失一般性,我们假设一个大的总任务已经按照某种分解规则被分解为若干个子任务,这些子任务的求解存在有序性和可并行性,并且各子任务将由不同的设计单元来承担,而不同的设计单元对各子任务的求解效率是不尽相同的。同时,假定需调度的子任务数多于可提供的设计单元数,并且各设计单元中的子任务之间的关系是非抢先式的,即在同一设计单元中的一个子任务没有完成之前,其他分配在该节点上的子任务不能开始执行。优化目标是,在满足任务偏序图中各子任务间时序约束关系的条件下寻找一个任务调度策略,将子任务集中的n个子任务分别调度到设计单元集中的m个设计单元中去执行,并使得整个任务(总任务)的总的执行效率最高,即总的完成时间最短。
并行设计子任务调度的遗传算法MATLAB源代码
并行设计子任务调度的遗传算法MATLAB源代码


%%
clc
clear
close all
%% 产生数据
%  GreenSim团队——专业级算法设计&代写程序
%  欢迎访问GreenSim团队主页→http://blog.sina.com.cn/greensim
%任务优先矩阵,n×n矩阵,Pij=1表示任务i需在j之前完成,Pij=0时任务i和j没有优先关系
TaskP=zeros(8,8);
TaskP(1,2)=1;
TaskP(1,3)=1;
TaskP(2,4)=1;
TaskP(2,5)=1;
TaskP(4,6)=1;
TaskP(5,6)=1;
TaskP(3,6)=1;
TaskP(3,7)=1;
TaskP(6,7)=1;
TaskP(7,8)=1;
%平均时间向量
MeanTime=[20,30,85,15,20,105,52,40];
%任务的效率矩阵
EFF=[0.9, 0.8, 0.7, 0.9, 1.2, 0.9, 0.8, 1.2;
     1.0, 1.0, 1.1, 0.8, 0.9, 1.1, 1.0, 1.0;
     0.8, 1.1, 0.9, 1.1, 0.7, 1.2, 1.0, 0.9];
[a,b]=size(EFF);
Time=zeros(a,b);
for i=1:a
    Time(i,:)=MeanTime./EFF(i,:);
end 
[AA,BB]=QJHJ(TaskP); 
%%
Iteration=1000;
MinT=Inf;
AllMinT=zeros(1,Iteration);
Best_f1=zeros(1,b);
Best_f2=zeros(1,b);
Best_ST=zeros(1,b);
Best_ET=zeros(1,b);
for i=1:Iteration
    [f1,f2]=Initialization(1,TaskP,EFF,AA,BB);
    [ST,ET]=DiaoDu(f1,f2,AA,Time);
    T=max(ET);
    if T<MinT
        MinT=T;
        Best_f1=f1;
        Best_f2=f2;
        Best_ST=ST;
        Best_ET=ET;
    end
    AllMinT(i)=MinT;
end
%%
figure
DRAW(Best_f1,Best_f2,Best_ST,Best_ET);
figure
plot(AllMinT);

function [ST,ET]=DiaoDu(f1,f2,AA,Time)
%% 输入参数列表
%  GreenSim团队——专业级算法设计&代写程序
%  欢迎访问GreenSim团队主页→http://blog.sina.com.cn/greensim
% f1        用于描述任务的排序(符合约束)
% f2        用于描述执行该任务的小组(机器)编号
% AA        各任务的前任务集
% Time      时间矩阵,各任务在各机器上的完成时间
%% 输出参数列表
% ST        各任务的开始时刻
% ET        各任务的结束时刻
%%
[a,b]=size(Time);%a为分组个数,b为任务个数
ET=zeros(1,b);
ST=zeros(1,b);
task=f1(1);%任务编号
group=f2(1);%机器编号
time=Time(group,task);
ST(task)=0;
ET(task)=time;
for i=2:b
    task=f1(i);
    group=f2(i);
    time=Time(group,task);
    AT=AA{task};
    L=length(AT);
    et1=0;
    if L>0
        for j=1:L
            if ET(AT(j))>et1
                et1=ET(AT(j));
            end
        end
    end
    P1=find(f2==group);
    BT=f1(P1);
    L2=length(BT);
    et2=0;
    if L2>0
        for j=1:L2
            if ET(BT(j))>et2
                et2=ET(BT(j));
            end
        end
    end
    ST(task)=max([et1,et2]);
    ET(task)=ST(task)+time;
end

0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有