内容发布更新时间 : 2024/6/24 19:54:35星期一 下面是文章的全部内容请认真阅读。
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];
%计算最有排序
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
FFD算法：
先将物体按长度从大到小排序,然后按FF算法对物体装箱. 不失一般性，对n件物品的体积按从大到小排好序，即有v1≥v2≥…≥vn，然后按排序结果对物品重新编号即可。 CF算法：
step1:把物件L??a1,a2,.a?,按其大小进行非增序排列，不妨设.n.s?a1??s?a2??..?.s?an? 。
step2:首先把a1放入箱子中B1，然后从最右端开始，依次把物件an,an?1,...放入B1，直到下一个物件不能再放入箱子为止，开启新的箱子B2。
step3:设在第i 步循环时，打开第i 个箱子，此时把物件ai放入Bi中. 假设第i-1 个箱子中最后一个放入的物件为ak，则在i 步循环时最右端的物件为ak?1，那么当
s?ai??s?ak?1??...?s?a1??C且s?ai??s?ak?1??...?s?al??s?al?1??C时，把ak?1,ak?2,...,a1放入Bi中，开启新的箱子Bi?1。
step4：直到把所有物件都放入箱子中，循环终止，并输出箱子数目m.