Johnson算法讲课讲稿

1、Johnson调度规则及其Matlab实现对于加工顺序相同的两个或两个以上作业在两台机器上的加工排序，称之为：n个作业两台机床的作业排序问题，经典的启发式排序方法为Johnson规则，其目的是最小化Makespan。该启发式规则的步骤如下：列出n个作业在两台机床上的作业时间；根据作业时间将n个作业分成P和Q两组。分组原则是：P组的作业在第二台机器上的加工时间 比在第一台机器上加工时间长；其余作业为Q组；将P组作业按他们在第一台机器上加工时间递增顺序排列，将Q组作业按他们在第二台机器上加 工时间递减的顺序排列。将P组作业顺序和Q组作业顺序连接在一起，构成的就是生产周期最短的最优作业顺序。如何使用

2、Matlab计算Johnson调度的Makespan？在获得最优的排程之后，根据如下步骤获取Makespan计算机器1上各作业的开始加工时间：StartTime(1,i)=StartTime(1,i-1)+WorkTime(1,i-1) i1StartTime(1,1)=0其中：WorkTime(1,i)为排程后机器1上的第i个作业的加工时间；计算各作业在机器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)

3、 i1计算 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 rulem,n=size(TimeArray);if m=2error(th

4、e process time must have two rows)endTimeArray(3,:)=(1:n);P=TimeArray(:,TimeArray(2,:)TimeArray(1,:);Q=TimeArray(:,TimeArray(2,:). s (a )。step2:首先把a放入箱子中B，然后从最右端开始，依次把物件a ,a ，放入B，直到下 11n n-11一个物件不能再放入箱子为止，开启新的箱子B 2。step3:设在第i步循环时，打开第i个箱子，此时把物件a,放入B中.假设第i-1个箱子中最后一个放入的物件为a，则在,步循环时最右端的物件为a-1，那么当s(a.)+

5、s(ak -1)+. + s(a1 ) C 时， 把a ,a ,.,a放入B中，开启新的箱子B 。 k -1k - 21ii+1step4:直到把所有物件都放入箱子中，循环终止，并输出箱子数目m.function cf(W,C)fprintf(输入物品重量);W=input(W=);fprintf(输入箱子容量);C=input(C=);%按物品重量降序排序B,IX = sort(W,2,descend);NW=B(IX);A=sort(NW);X=0;for j=1:length(NW)TW=0;if isempty(NW)break;elseTW=TW+NW(1);X=X+1;CW=;for i=1:length(A)if C-TW=A(i)TW=TW+A (i);CW(i)=A(i);endendfprintf(输出每个箱子里的物品：)