Matlab【多台机器上等长作业调度】【差分约束系统】【Bellman-Ford算法】

【多台机器上等长作业调度问题】给定n个作业，m台机器，其释放时间分别为：r1，r2,...,rn，最晚开始时间分别为：u1,u2,...,un，每个作业需要的处理时间均为p。求一个可行调度。

该问题的约束条件可以表示为：

其中，yt表示t时刻之前，开始的作业的总个数。只需要满足约束条件7、8、9的一组y，就是一个可行的调度。

上述约束条件是一种特殊的线性规划问题，该问题可以规约为单源最短路径问题，进而可以通过图论中的最小路径理论可以求出一个满足该约束条件的解，这种特殊的线性规划问题称为差分约束系统。

【差分约束系统】

在一个差分约束系统中，线性规划矩阵A中的每一行包括一个1和一个-1，其他项皆为0。因此，由Ax<=b所给出的约束条件变为m个涉及n个变量的差额限制条件，其中每个约束条件是如下所示的简单线性不等式：

xj-xi<=bk

这里，1<=i，j<=n，i≠j，且1<=k<=m。

【实例】

现有5个作业，2台机器，每个作业在每台机器上的处理时间均为3，作业的释放时间分别为1、2、2、3、4，作业的最迟开始时间9、4、7、5、6，求一个可行的调度方案。

首先，我们需要确定该问题对应的调度图。

由于最小的释放时间rmin=1，最大的最迟开始时间umax=9，所以，调度图中的顶点个数为umax-rmin+1=9

根据约束条件可以确定调度图中存在哪些边，并通过下列公式（可以由上述约束条件总结出来）求出这些边的权重。

Matlab【多台机器上等长作业调度】【差分约束系统】【Bellman-Ford算法】

接着，由于边中存在负的权重，因此不能使用Dijkstra算法求最短路径，采用Bellman-Ford算法求最短路径。

如下是matlab实现的程序代码：

%% 差分约束系统求解多个等长任务在多处理器上的调度问题
%作业个数
n = 5;
%机器的个数
m = 2;
%作业处理时间
p = 3;
%作业的释放时间
r = [1 2 2 3 4];
%作业的最迟开始时间
u = [9 4 7 5 6];
%作业总时间
B=sort([r u]);
rmin = min(B);
umax = max(B);
%以时间为顶点
T = rmin:umax;
%图G中边的权重
G=ones(length(T))*inf;
%标识图G中的边
M=zeros(length(T));
M = existsedge( M,rmin,umax,r,u,p)';
for i=1:length(T)
    for j=1:length(T)
        %判断是否存在边，若存在，则计算边的权重
        if M(i,j) == 1
            if i < j
                G(i,j)=m;
            else
                count = 0;
                for k = 1:length(r)
                    if r(k) >= j && u(k) <= i
                        count = count + 1;
                    end
                end
                G(i,j)=-count;
            end
        end
    end
end

%绘出调度图
graph(G);
%求解问题
[flag,dis] = bellmanford(G,umax);
%确定各个作业的开始时间
[val,ind]=sort(u);
starttimes = zeros(1,length(u));
k=1;
for i=1:length(T)-1
    if dis(i) ~= dis(i+1)
        %当前时刻i开始的作业个数
        tmp = dis(i+1) - dis(i);
        while(tmp > 0)
            starttimes(ind(k)) = i;
            k = k+1;
            tmp = tmp - 1;
        end
    end
end
%依次输出各个作业的开始时间
starttimes

function [ M ] = existsedge( M,rmin,umax,r,u,p)
%判断图中是否存在边
	%% 约束1
    for i=1:size(M,1)
        if i >= rmin && i <= umax-p
            M(i+p,i) = 1;
        end
    end
    
	%% 约束2
	for i=1:size(M,1)
        if i >= rmin && i < umax
            M(i,i+1) = 1;
        end
    end
    
	%% 约束3
    for i=1:length(r)
        for j=1:length(r)           
            if(r(i)<u(j))
                M(r(i),u(j)) = 1;
            end
        end
    end
end

function [flag,dis]=bellmanford(G,s)
% 输出：是否存在可行解
    %G—图的邻接矩阵表示，元素值为权重
    %s—图的源点
    dis = ones(1,size(G,1))*inf;
    %初始化
    dis = init(G,s,dis);
    %执行松弛操作
    for l=1:size(G,1)-1
        for j=1:size(G,1)
            for k=1:size(G,1)
                dis = relax(G,j,k,dis);
            end
        end
    end
    %判断是否存在权重为负值的环路
    for m=1:size(G,1)
        for n=1:size(G,1)
            %是否存在估计错误的情况，若存在，则代表存在权重为负值的环
            if dis(n)>dis(m) + G(m,n)
                flag = 0;
                return;
            end
        end
    end
    flag = 1;
    %输出可行解
    dis
end

%dis：最短路径估计值数组
%G：图的邻接表表示法，元素代表行数i到列数j之间边的权重
function [dis] = init(G,s,dis)
    for i=1:size(G,1)
        dis(i) = inf;
    end
    dis(s) = 0;%源点的距离为0
end

%dis：最短路径估计值数组
%G：图的邻接表表示法，元素代表行数i到列数j之间边的权重
function [dis] = relax(G,u,v,dis)
    %dis(v):表示G中从源点到点v的距离估计值，若估计值大于前驱节点的距离+u和v的距离，则更新
	if dis(v)>dis(u)+G(u,v)
        dis(v) = dis(u)+G(u,v);
 	end
end

function graph(cm)
    %% 去除图中的权重为inf的边
    for i=1:size(cm,1)
        for j=1:size(cm,2)
            if cm(i,j) == inf
                cm(i,j) = 0;
            end
        end
    end
    
    %% 设置图显示权重并可视化
     bg=biograph(cm);
     bg.showWeights='on';
     view(bg);
end

运行结果：

Matlab【多台机器上等长作业调度】【差分约束系统】【Bellman-Ford算法】

flag =

     1


dis =

    -5    -5    -4    -3    -3    -2    -1    -1     0

根据差分约束系统中解的性质：若x是一个解，则x+k也是一个解。这里，k为任意自然数。

     0     0     1     2     2     3     4     4     5

解的含义：y2=0，代表t=1时，没有运行作业；y3=1，代表t=2开始运行一个作业，依次类推，运行作业的时刻分别为2、3、5、6、8。接着，按照最晚开始时间从大到小的顺序开始运行作业，即各个开始运行作业的时刻分别对应的作业为2、4、5、3、1。各个作业的开始时间依次如下：

starttimes =

     8     2     6     3     5

Matlab【多台机器上等长作业调度】【差分约束系统】【Bellman-Ford算法】

相关推荐