[原创]Johnson调度规则及其Matlab实现

对于加工顺序相同的两个或两个以上作业在两台机器上的加工排序，称之为：n个作业两台机床的作业排序问题，经典的启发式排序方法为Johnson规则，其目的是最小化Makespan。

该启发式规则的步骤如下：

1）列出n个作业在两台机床上的作业时间；

2）根据作业时间将n个作业分成P和Q两组。分组原则是：P组的作业在第二台机器上的加工时间比在第一台机器上加工时间长；其余作业为Q组；

3）将P组作业按他们在第一台机器上加工时间递增顺序排列，将Q组作业按他们在第二台机器上加工时间递减的顺序排列。

4）将P组作业顺序和Q组作业顺序连接在一起，构成的就是生产周期最短的最优作业顺序。

 

如何使用Matlab计算Johnson调度的Makespan？

在获得最优的排程之后，根据如下步骤获取Makespan

1）计算机器1上各作业的开始加工时间:

StartTime(1,i)=StartTime(1,i-1)+WorkTime(1,i-1) i>1

StartTime(1,1)=0

其中：WorkTime(1,i)为排程后机器1上的第i个作业的加工时间；

2）计算各作业在机器2上的开始加工时间：

StartTime(2,1)=WorkTime(1,1)

StartTime(2，i)=Max([StartTime(2，i-1)+WorkTime(2,i-1)],[StartTime(1,i)+WorkTime(1,i)]) i>1

3）计算Makespan=StartTime(2,n)+WorkTime(2,n)

 

Matlab程序

 

function Johnson()
%Johnson rule to obtain the optimal schedule and calculate the makespan
TimeArray=[10 5 11 3 7 9;4 7 9 8 10 15];%The process data could be changed by yourself

%Get the optimal schedule by Johnson rule
[m,n]=size(TimeArray);
if m~=2
    error('the process time must have two rows')
end
TimeArray(3,:)=(1:n);
P=TimeArray(:,TimeArray(2,:)>TimeArray(1,:));
Q=TimeArray(:,TimeArray(2,:)<=TimeArray(1,:));
P=(sortrows(P',1))';
Q=(-sortrows((-Q)',2))';
Schedule=[P Q];

%Calculate the optimal makespan of the optimal schedule
WorkTime(1:2,:)=Schedule(1:2,:);
StartTime(1,1)=0;
for i=2:n
    StartTime(1,i)=StartTime(1,i-1)+WorkTime(1,i-1);
end
StartTime(2,1)=WorkTime(1,1);
for i=2:n
    StartTime(2,i)=max([StartTime(2,i-1)+WorkTime(2,i-1)],[StartTime(1,i)+WorkTime(1,i)]);
end
Makespan=StartTime(2,n)+WorkTime(2,n);
Schedule(1:2,:)=[];
TheOptimalScheduel=Schedule
TheOptimalMakespan=Makespan 

推荐到鲜果： 查阅更多相关主题的帖子: 生产管理 调度 Matlab