【老生谈算法】matlab实现CDS启发式算法源码——CDS启发式算法

CDS启发式算法及Matlab程序

---

1、文档下载：

本算法已经整理成文档如下，有需要的朋友可以点击进行下载

---

2、算法详解：

用于求解n-job，m-machine的流水作业调度问题；即n项作业都需要顺序进行m个工序，m个工序中，每道工序仅有一台机器，如何安排n项作业的加工先后关系。

CDS(Campbell-Dudek-Simth)：是Johnson算法的扩展，被认为是好的具有鲁棒性的启发式算法；

算法步骤：
1、将m台机器分组，产生m-1个两台机器问题的集合；
2、然后利用Johnson算法获得m-1个加工顺序(每个两台机器问题获得一个加工顺序)；
3、选取这m-1个加工顺序中考核指标最好（一般为Makespan最短）的加工顺序作为近似最优调度解；

分组及每组组合加工时间示意表

示例：
现在有四项作业需要在6台机器上加工，时间数据如下(n行m列)，试使用CDS方法获取最优调度，即最短加工时间Makespan。

CDS法求解结果如下：

Makespan =106

Schedule =
3 1 2 4
3 1 2 4
3 1 2 4
3 1 2 4
可以看出，分组后的5（m-1）组两机器问题中，通过Johnson法获取的最优调度中，有4组获得了最优调度： 3 1 2 4
也验证了CDS法具有较高的

Matlab程序–CDS.m

function [Makespan,Schedule]=CDS(PT)
[n,m]=size(PT);
if n<=1
    error('The job qty must large than 2')
end
PT=double(PT);
%Create new 2-stage-machine time
NewPT(1:n,1:2,1:m-1)=0.0;
for i=1:m-1
    for j=1:i
        NewPT(:,1,i)=NewPT(:,1,i)+PT(:,j);
        NewPT(:,2,i)=NewPT(:,2,i)+PT(:,m-j+1);
    end
end
 
%Calculate the m-1 group 2-machine problem using Johnson Rule
for i=1:m-1
    [MidMakespan(i),MidSchedule(i,:)]=Johnson(NewPT(:,:,i)');
end
 %Calculate the Makespan of the m-1 MidSchedule
for i=1:m-1
    StartTime(1:m,1:n)=0;
    StartTime(1,MidSchedule(i,1))=0;
    for j=2:n
       StartTime(1,MidSchedule(i,j))=StartTime(1,MidSchedule(i,j-1))+PT(MidSchedule(i,j-1),1);
    end
    for k=2:m
        StartTime(k,MidSchedule(i,1))=StartTime(k-1,MidSchedule(i,1))+PT(MidSchedule(i,1),k-1);
        for j=2:n
            StartTime(k,MidSchedule(i,j))=max(StartTime(k,MidSchedule(i,j-1))+PT(MidSchedule(i,j-1),k),...
                StartTime(k-1,MidSchedule(i,j))+PT(MidSchedule(i,j),k-1));
        end        
    end
    MMidMakespan(i)=StartTime(m,MidSchedule(i,n))+PT(MidSchedule(i,n),m);
end
% Sort the Makespan and obtain the optimal Schedule          
[Best,BestIndex]=sort(MMidMakespan);
OptNum=1;
Makespan=MMidMakespan(BestIndex(1));
Schedule=MidSchedule(BestIndex(1),:);
%Statistic the total optimal shedules
for i=2:m-1
    if MMidMakespan(BestIndex(i))==MMidMakespan(BestIndex(1))
        OptNum=OptNum+1;
        Schedule(OptNum,:)=MidSchedule(BestIndex(i),:);
    end
end
       
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48