当前位置：文档之家 › Johnson算法

Johnson算法

  • 格式：doc
  • 大小：34.50 KB
  • 文档页数：4

Johnson算法

1 / 4 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)

Johnson算法

2 / 4 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

Johnson算法

3 / 4 FFD算法：

先将物体按长度从大到小排序,然后按FF算法对物体装箱. 不失一般性，对n件物品的体积按从大到小排好序，即有v1≥v2≥…≥vn，然后按排序结果对物品重新编号即可。

CF算法：

step1:把物件naaaL,...,,21按其大小进行非增序排列，不妨设nasasas...21 。

step2:首先把1a放入箱子中1B，然后从最右端开始，依次把物件,...,1nnaa放入1B，直到下一个物件不能再放入箱子为止，开启新的箱子2B。

step3:设在第i 步循环时，打开第i 个箱子，此时把物件ia放入iB中. 假设第i-1 个箱子中最后一个放入的物件为ka，则在i 步循环时最右端的物件为1ka，那么当

Casasaski11...且Casasasasllki11...时，把121,...,,aaakk放入iB中，开启新的箱子1iB。

step4：直到把所有物件都放入箱子中，循环终止，并输出箱子数目m.

Johnson算法

4 / 4 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;

else

TW=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);

end

end

fprintf('输出每个箱子里的物品：');

[NW(1),CW]

end

NW=sort(setdiff(NW,[NW(1),CW]),2,'descend');

A=sort(NW);

end

disp('输出箱子的数量：');

X

合集下载

Stevens-Johnson综合征

Stevens-Johnson综合征

史-约综合征

概述:

概述：1922年，首先由Stevens和Johnson对史-约综合征即“Stevens-Johnson综合征”进行了详细地描述。该综合征是一种累及皮肤和黏膜的急性水疱病变。Stevens-Johnson综合征可发生在某些感染或口服某些药物后，出现多形性红斑是皮肤的轻度水疱性病变，多形性红斑进一步发展形成毒性表皮坏死溶解，这是一种急性致命性的病变。该病的眼部表现比较严重，病变可累及角膜、睑结膜、球结膜和眼睑。

流行病学:

流行病学：

1.发病率 Stevens-Johnson综合征的发病率较低。Char等报道每年在每100万人中仅有4.2人发生Stevens-Johnson综合征。Schoph等报道在德国Stevens-Johnson综合征每年的发生率为1.1/100万。法国所报道的发病率为每年1.2/100万～1.3/100万，而意大利的发病率为0.6/100万。目前国内尚无Stevens-Johnson综合征发病率的报道。

2.眼部并发症的发生率 Stevens-Johnson综合征患者中，80%出现眼部并发症。在某些严重病例，急性并发症包括角膜炎、角膜穿孔，严重者发生眼内炎。慢性并发症有结膜瘢痕、睑内翻、干眼症和睑球粘连等。这些并发症可继发角膜损害，从而导致长期并发症的出现。约有1/3的Stevens-Johnson综合征患者会出现明显的视力改变。由于艾滋病患者经常出现泪液分泌减少，所以其并发症的发生率要明显升高。

病因:

病因：Stevens-Johnson综合征的发生与多种因素有关，如全身用药、局部用药、感染、恶性肿瘤和胶原血管性疾病等。

发病机制:

发病机制：在Stevens-Johnson综合征中，引起免疫反应的诱导因素尚不明确。虽然药物在Stevens-Johnson综合征的发生中起着重要作用，但其临床特点和实验研究并不支持它是一种速发型超敏反应。感染因素在其发病机制中的作用也尚未确定。

流水线作业排序问题

流水线作业排序问题

流水线作业排序问题

/productioncontrol/200908091604.html

流水作业排序问题的基本特征是每个工件的加工路线都一致。在流水生产线上制造不同的零件，遇到的就是流水作业排序问题。我们说加工路线一致，是指工件的流向一致，并不要求每个工件必须经过加工路线上每台机器加工。如果某些工件不经某些机器加工，则设相应的加工时间为零。

一般说来，对于流水作业排序问题，工件在不同机器上的加工顺序不尽一致。但本节要讨论的是一种特殊情况，即所有工件在各台机器上的加工顺序都相同的情况。这就是排列排序问题。流水作业排列排序问题常被称作“同顺序”排序问题。对于一般情形，排列排序问题的最优解不一定是相应的流水作业排序问题的最优解，但一般是比较好的解；对于仅有2台和3台机器的特殊情况，可以证明，排列排序问题下的最优解一定是相应流水作业排序问题的最优解。

这里只讨论排列排序问题。但对于2台机器的排序问题，实际上不限于排列排序问题。

一、最长流程时间Fmax的计算

这里所讨论的是n／m／P /Fmax，问题，其中n为工件数， m为机器数，P表示流水线作业排列排序问题，Fmax为目标函数。目标函数是使最长流程时间最短，最长流程时间又称作加工周期，它是从第一个工件在第一台机器开始加工时算起，到最后一个工件在最后一台机器上完成加工时为止所经过的时间。由于假设所有工件的到达时间都为零(ri=0， i= 1，2，„，n)，所以Fmax等于排在末位加工的工件在车间的停留时间，也等于一批工件的最长完工时间Cmax。

设n个工件的加工顺序为S＝(S1，S2，S3，„，Sn)，其中Si为第i位加工的工件的代号。以 表示工件Si在机器 M k上的完工时间, 表示工件Si在 Mk上的加工时间，k= 1，2，„，m； i=1，2，„，n，则 可按以下公式计算：

在熟悉以上计算公式之后，可直接在加工时间矩阵上从左向右计算完工时间。下面以一例说明。

【图论】Johnson算法

【图论】Johnson算法

【图论】Johnson算法

适⽤于求解没有负环的全源最短路，最坏时间复杂度 O(nmlogm) ⽐Floyd要优秀（但是Floyd可以找出负环）。

在没有负权边时，使⽤n次单源最短路Dijkstra代替即可。

算法流程：

1、新建⼀个虚拟节点（编号为n+1），向[1,n]连接⼀条边权为0的虚拟边。

2、从n+1号节点开始跑⼀次队列优化BellmanFord，得到从n+1号虚拟节点到节点i的最短路hgt[i]，假如存在负环，则⽆法求解。

3、删除虚拟节点和虚拟边（也可以直接选择忽视他们）

4、把每条⾮虚拟边(u,v,w)改为(u,v,w+hgt[u]-hgt[v])

5、对于每个点i属于[1,n]，跑⼀次Dijkstra，得到从i节点到[1,n]的⾮虚拟节点的最短路dis[j]。

6、原本的[i,j]的最短路为dis[j]+hgt[i]-hgt[j]

最后把边权修改回来的操作可以省去。

namespace Johnson {

const int MAXN = 2e5 + 10;

int n;

vector G[MAXN];

ll hgt[MAXN];

ll dis[MAXN];

int cnt[MAXN];

bool vis[MAXN];

queue Q;

priority_queue PQ;

bool bellmanford() {

fill(hgt + 1, hgt + 1 + n, LINF);

fill(cnt + 1, cnt + 1 + n, 0);

fill(vis + 1, vis + 1 + n, 0);

while(!Q.empty())

Q.pop();

hgt[n] = 0;

vis[n] = 1;

Q.push(n);

while(!Q.empty()) {

int u = Q.front();

Q.pop();

vis[u] = 0;

++cnt[u];

if(cnt[u] == n)

return false;

流水作业调度问题

流水作业调度问题

一、 问题描述

给定n个作业，每个作业有两道工序，分别在两台机器上处理。一台机器一次只能处理一道工序，并且一道工序一旦开始就必须进行下去直到完成。一个作业只有在机器1上的处理完成以后才能由机器2处理。假设已知作业i在机器j上需要的处理时间为t[i,j]。流水作业调度问题就是要求确定一个作业的处理顺序使得尽快完成这n个作业。

二、 算法分析

n个作业{1,2,…,n}要在由2台机器1M和2M组成的流水线上完成加工。每个作业加工的顺序都是先在1M上加工，然后在2M上加工。1M和2M加工作业i所需要的时间分别为t[i,1]和t[i,2], ni1.流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器1M上开始加工，到最后一个作业在机器2M上加工完成所需的时间最少。

从直观上我们可以看到，一个最优调度应使机器1M没有空闲时间，且机器2M的空闲时间是最少。在一般情况下，机器2M上会有机器空闲和作业积压两种情况。

设全部作业的集合为},....,2,1{nN。NS是N的作业子集。在一般情况下，机器1M开始加工S中作业时，机器2M还在加工其他作业，要等时间t后才能利用。将这种情况下完成S中作业所需的最短时间计为),(tST。流水作业调度问题的最优解为)0,(NT。

1. 证明流水作业调度问题具有最优子结构

设a是所给n个流水作业的一个最优调度，它所需要的加工时间为']1),1([Tat。其中，'T是在机器2M的等待时间为]2),1([at时，安排作业)(),......,3(),2(naaa所需的时间。

记)}1({aNS，则我们可以得到])2),1([,('atSTT。 事实上，有T的定义可知])2),1([,('atSTT.若])2),1([,('atSTT，设'a是作业集S在机器2M的等待时间为]2),1([at情况下的一个最优调度。则)('),.....,2('),1(naaa是N的一个调度且该调度所需的时间']1),1([])2),1([,(]1),1([TatatSTat。这与a是N的一个最优调度矛盾，所以])2),1([,('atSTT。从而])2),1([,('atSTT。这就是证明了流水作业调度问题具有最优子结构的性质。