研究生数学建模竞赛选拔赛.docx

研究生数学建模竞赛选拔赛.docx

《研究生数学建模竞赛选拔赛.docx》由会员分享，可在线阅读，更多相关《研究生数学建模竞赛选拔赛.docx（21页珍藏版）》请在冰点文库上搜索。

研究生数学建模竞赛选拔赛

武汉大学

第十届全国研究生数学建模竞赛选拔赛

学 院：

信息管理学院

专 业：

管理科学与工程

姓 名：

叶珍芳

学 号：

2012201040002

流水线车间调度优化问题

摘要

本文通过建立三个模型：

遗传算法模型、n/m/P/Fma模型、穷举算法模型，对题设的问题进行了全面的分析。

遗传算法模型中，以占用约束和顺序约束为约束条件，所有加工件完成加工所需的总时间最短为决策目标，运用遗传算法对模型求解，因而称之为遗传算法模型。

虽然该模型适用性强，但对算法的要求高，作者没有做出成功的结果展示。

n/m/P/Fmax模型是解决流水线车间调度优化问题的典型模型，该模型计算量小，简单易用。

本文给出来了工序完成时间

的递推公式，运用启发式算法pamler的两种斜度指标，得到两个完工时间为35分钟的最优调度：

（1,3,4,6,5,2）和（1,4,3,6,5,2），并画出（1,3,4,6,5,2）顺序下的各工件的移动方式图。

以上两种模型都是解决车间调度问题的常用模型。

具体问题需要具体分析，作者认为穷举法对于本问题是可行的。

作者以matlab为辅助计算工具，穷举6种加工件的排列，得到14种不同的调度，工序完成时间均为35分钟。

该模型较为全面的给出最优调度，同时验证了n/m/P/Fmax模型结论的正确性。

关键词：

 车间调度优化 遗传算法 n/m/P/Fmax调度穷举法

Abstract

Thispaperputsforwardthreemodelstosolvetheparticularflowshopschedulingproblemcomprehensively.

Inthefirstmodel,thepaperanalysistheflowshopschedulingproblemanddescribestheproblemthroughmathematicdepiction.Geneticalgorithmisappliedtosolvethismodel.Butitdemandsaveryunderstandingofthealgorithmsothattheauthorfailedtoshowasuccessfulresult.

Then,thepaperintroducesthen/m/P/Fmaxmodel，whichisclassicaltosolvelineshopschedulingoptimizationproblem.Inthispart,theauthorobtainsrecursionformulatocomputeeveryjob'scompletetimeandusesaheuristicalgorithmcalledPamler.Twooptimalschedulingstrategiesisfoundandtheircompletetimeisboth35minutes.Theyare（1,3,4,6,5,2）and（1,4,3,6,5,2）.

Althoughbothmodelsaboveareclassicalinsolvingjobshopschedulingproblem,enumerationmethodisfeasibleinthissmall-scaleproblem.Withthehelpofmatlab,trytodisplayalltheschedule,calculatetheircompletetimeandfindouttheminimum.Inthisway,14differentschedulingisfoundandthetwostrategiesprovidedinthesecondmodelareincluded.Thismodelfindsoutalltheoptimalschedulingstrategies.Also,itverifiesthecorrectnessofthesecondmodel.

Keyword:

 Shopschedulingoptimization GeneticAlgorithm 

n/m/P/Fmaxscheduling methodofexhaustion

一、问题重述

某车间有三台机器,分别用于弯折金属管,焊接连接处,以及装配各单元。

此车间需要生产六种加工件，每个加工件都需要首先进行弯折，然后进行焊接，最后进行装配，各加工工序所需时间已知。

在进入工序之后，每项加工工序都不允许打断，但在两道工序之间可以等待一段时间。

每台机器每次只能处理一个加工件。

如果在一开始为所有加工件建立了一个加工顺序，则在每台机器上都将严格按照此顺序进行加工。

现需确定工件的加工次序，使六种工件的加工完成时间最短。

二、模型假设

1、同一阶段上各机器的处理性能相同，不存在机器故障问题。

2、加工件不断送达，即第一道工序（弯折）不存在等候。

3、每一道工序完成，加工件便离开机器（若此工件进入下一道工序需要等待，则认为其进入缓存库），机器开始加工新的工件。

4、机器工作不需要准备时间。

三、问题分析

车间调度优化问题属于排队问题，模型刻画包括多服务员平行排队模型、串联排队模型、有限资源排队模型等[1]。

根据题设，每台机器在每个时刻只能加工某个工件的某道工序，只能在上道工序加工完成后才能开始下一道工序的加工，前者称为占用约束，后者称为顺序约束[2]。

本题中，顺序约束、占用约束均已知，可列出约束条件，决策目标为加工总时间最短，据此列出目标函数。

遗传算法是此模型的经典求解方法。

车间调度模型的一种特殊类型的流水车间排序问题——n个工件在m台机器上的加工顺序都相同，被称为排列排序问题，即n/m/P/Fmax问题。

而本题的流水作业问题可以描述为：

6个工件在3台机器上加工，一个工件分为3道工序，每道工序只在1台机器上加工，即6/3/P/Fmax。

1965年Palmer提出求解n/m/P/Fmax的启发式算法，称为Palmer法[3]。

本题可用此方法求解。

再者，本问题的工件数和机器数都已知且数量少，枚举法不失为一个好方法，可以设计算法，使用matlab辅助运算。

四、模型建立与求解

根据以上分析，从不同的角度，可以对本问题建立三种模型。

4.1遗传算法模型

该调度问题中的约束条件有：

（1）占用约束：

每一台机器在每个时刻只能加工某个工件的某道工序。

（2）顺序约束：

只能在上道工序加工完成后才能开始下一道工序的加工。

决策目标为：

工件完工时间最小化

根据约束条件和决策目标可建立以下模型：

约束条件：

（1）工件i先于工件h在机器j上加工，即Chj-Cij≥Thji,h=1,2,…6;j=1,2,3

（2）机器k先于机器j加工工件i，即Cij-Cik≥Tiji=1,2,…6;j,k=1,2,3 

（3）Cij≥0,i=1,2…6；j=1,2,3

目标函数：

模型可用遗传算法进行求解[4]。

由于作者编程水平有限，程序调试不成功，在此不做结果的展示，程序及部分结果附在文后，请读者更正。

4.2 6/3/P/Fmax模型

4.2.1模型建立

在问题分析中已经知道该问题属于n/m/P/Fmax问题。

首先，介绍流水作业问题表示法n/m/P/Fmax各字母的含义。

n：

工件数

m：

机器数

P：

流水作业排列序列

Fi：

第i个工件在车间停留的时间

Fmax：

使最长流程时间最短，即

本题中工件数为6，机器数为3，所以可建立6/3/P/Fmax模型。

4.2.2模型求解——Palmer法

1965年PalmerD.S提出按斜度指标排列工件的启发式算法，称为Palmer法[3]。

工件i的斜度指标Pi为

i=1,2,…，n  

（1）

式中，n为工件数；m为机器数；Pij为工件i在机器Mj上的加工时间。

按Pi减少的顺序排列工件的加工顺序可以得到问题的最优解或者近优解。

但Pamler法在解决问题时常常会出现不同的工件，斜度指标却相等的情况，不少学者提出了改进方法，比如李大卫提出用Si作为斜度指标[5]，定义Si为

i=1,2,…，n       

（2）

式中，n,m和Pij的意义如

（1）式所述。

此改进法以Si增加的顺序排列工件的加工顺序得到最优解或者近优解。

Fmax的值是由加工时间矩阵计算得出：

表示工件

在机器

上的完工时间，

表示工件

在机器

上的加工时间，

的递推计算公式为：

s=1,2,…,m; k=1,2,…,n   （3）

s=1,2,…,m; k=2,…,n   （4）

下面采用Pamler原始方法和改进法解法分别求解模型。

4.2.2.1用Palmer法求解

P（1,2,…,6）=（2,-4,1,1,-2,-1），则按Pi减少的顺序排列工件的加工顺序有两个：

R1=（1,3,4,6,5,2）和R2=（1,4,3,6,5,2）。

下面以R1为例，计算Fmax。

表一 加工时间矩阵

i

1

2

3

4

5

6

Pi1

3

6

3

5

5

7

Pi2

5

4

2

4

4

5

Pi3

5

2

4

6

3

6

表二 顺序R1下的加工时间矩阵

i

1

3

4

6

5

2

Pi1

33

36

511

718

523

629

Pi2

58

210

415

523

427

433

Pi3

513

417

623

629

331

235

数字的上标为该工序的完工时间

，由上表可以看出F（R1）=35

图1 顺序R1下的移动方式图

计算排列R2的时间，发现F（R2）=F（R1）=35

4.2.2.2用改进法求解

S（1,2,…,6）=（24/13,28/127,17/9,29/15,26/12,37/18），则以Si增加的顺序排列工件的加工顺序R3=（1,3,4,6,5,2），R3=R1，说明对于本问题，改进法和Palmer法效果相同。

综上，加工顺序（1,3,4,6,5,2）与加工顺序（1,4,3,6,5,2）都能使所有加工件完成加工所需的总时间最短，最短时间为35分钟。

4.3穷举法

穷举法的思想为6个加工件的全排列个数为6！

=720个，根据4.2中计算Fmax的递推公式计算所有720个排列下的加工时间，得出时间最短的排列。

穷举法对于规模较小的问题是可行的，本题加工件的个数和机器数都较少，尽管全排列有720个，可借助matlab辅助计算。

作者在编程能力较弱，在按以上思想编写程序时遇到困难，使用了另一种算法，其思想为随机生成一个调度，计算该调度下完工所需时间T，将这个随机过程重复N次，当N》720时，可以认为720个全排列都已包括在这N个调度中。

这N个T的最小值即为6个加工件加工完毕所需的最短时间，对应的排列即为最有调度。

流程如图2所示，程序见附录。

图2 枚举法流程图

经试验，取N=2000，显示T的最小值为35，对应的排列有37个，经观察，不重复的有14个，也就是说这14个调度都能使完工时间为35分钟，都是最优调度。

列举14个调度如下：

（1,4,6,5,3,2） （4,1,6,3,5,2） （1,4,3,6,5,2） （3,1,6,5,4,2） （4,1,3,6,5,2） （3,4,1,6,5,4） （4,1,6,5,3,2） （3,1,6,4,5,2） （1,3,4,6,5,2）（4,3,1,6,5,2） （3,1,6,5,4,2） （1,4,6,3,5,2）（1,4,3,6,5,2） （3,1,4,6,5,2）

验证模型二，加工顺序（1,3,4,6,5,2）与加工顺序（1,4,3,6,5,2）在以上14个调度中，且最短时间为35分钟，结论相同。

经过多次试验，均未出现T值小于35的情况，不重复的调度最多为14个。

可以认为本问题最优调度有14种，最短时间为35分钟。

五、总结与模型评价

本文通过建立三个模型对题设的问题进行了全面的分析，且模型三较为全面的给出最优调度，很好地解决了问题。

对于车间调度问题，三个模型各有优缺点。

1.遗传算法模型是对车间调度问题普遍适用的，但对模型的理解存在难度，对小规模问题解决显得太繁琐，没有另外两个模型直观。

2.n/m/P/Fma模型的仅对流水车间排序问题适用，使用有较大限制，模型推广性不强。

但对该模型计算量小，简单易做。

但常常会遇到不同的工件的斜度指标相等的情况，此时需要对斜度指标相等的工件做全排列，分别计算Fmax。

尽管如此，计算量比穷举法仍小得多。

3.穷举法解决小规模的问题时采用的方法，这里的小规模不仅指的是机器及工件的个数小，还包括是否需要考虑工件到来间隔时间、机器是否存在阻塞问题等。

优点在于可以找全每个最优调度，保证了结论的完整性和准确性。

参考文献

[1]梁秋荣，VB与Matlab集成求解车间调度优化问题，装备制造技术，（02）：

60-61,2008。

[2]叶其孝，大学生数学建模竞赛辅导教材，湖南省：

湖南教育出版社，1993。

[3]PalmerDS.SequencingJobsthroughaMulti-StageProcessintheMinimumTotalTime-AQuickMethodofObtainingaNearOptimum..OperatResQ,（16）:

101-107,1965.

[4]梁迪，谢里阳，隋天中，陶泽，基于遗传和禁忌搜索算法求解车间调度优化问题，计算机应用，26（4）:

857-860,2006。

[5]李大卫，n/m/P/Fmax调度问题的一种新解法，鞍山钢铁学院学报，19（6）:

4-7,1996。

附件：

1.遗传算法

function[Zp,Y1p,Y2p,Y3p,Xp,LC1,LC2]=JSPGA（M,N,Pm,T,P）

% 流水线型车间作业调度遗传算法

N=20;M=100;Pm=0.02;T=[3,5,5;6,4,2;3,2,4;5,4,6;5,4,3;7,5,6];P=[1,1,1];

% 输入参数列表

% M   遗传进化迭代次数

% N   种群规模（取偶数）

% Pm   变异概率

% T   m×n的矩阵，存储m个工件n个工序的加工时间

% P   1×n的向量，n个工序中，每一个工序所具有的机床数目

% 输出参数列表

% Zp   最优的Makespan值

% Y1p  最优方案中，各工件各工序的开始时刻，可根据它绘出甘特图

% Y2p  最优方案中，各工件各工序的结束时刻，可根据它绘出甘特图

% Y3p  最优方案中，各工件各工序使用的机器编号

% Xp   最优决策变量的值，决策变量是一个实数编码的m×n矩阵

% LC1  收敛曲线1，各代最优个体适应值的记录

% LC2  收敛曲线2，各代群体平均适应值的记录

% 最后，程序还将绘出三副图片：

两条收敛曲线图和甘特图（各工件的调度时序图）

%第一步：

变量初始化

[m,n]=size（T）;%m是总工件数，n是总工序数

Xp=zeros（m,n）;%最优决策变量

LC1=zeros（1,M）;%收敛曲线1

LC2=zeros（1,N）;%收敛曲线2

%第二步：

随机产生初始种群

farm=cell（1,N）;%采用细胞结构存储种群

fork=1:

N

X=zeros（m,n）;

forj=1:

n

fori=1:

m

X（i,j）=1+（P（j）-eps）*rand;

end

end

farm{k}=X;

end

counter=0;%设置迭代计数器

whilecounter

%第三步：

交叉

newfarm=cell（1,N）;%交叉产生的新种群存在其中

Ser=randperm（N）;

fori=1:

2:

（N-1）

A=farm{Ser（i）};%父代个体

B=farm{Ser（i+1）};%父代个体

Manner=unidrnd

（2）;%随机选择交叉方式

ifManner==1

cp=unidrnd（m-1）;%随机选择交叉点

%双亲双子单点交叉

a=[A（1:

cp,:

）;B（（cp+1）:

m,:

）];%子代个体

b=[B（1:

cp,:

）;A（（cp+1）:

m,:

）];

else

cp=unidrnd（n-1）;%随机选择交叉点

a=[A（:

1:

cp）,B（:

（cp+1）:

n）];

b=[B（:

1:

cp）,A（:

（cp+1）:

n）];

end

newfarm{i}=a;%交叉后的子代存入newfarm

newfarm{i+1}=b;

end

%新旧种群合并

FARM=[farm,newfarm];

%第四步：

选择复制

FITNESS=zeros（1,2*N）;

fitness=zeros（1,N）;

plotif=0;

fori=1:

（2*N）

X=FARM{i};

Z=COST（X,T,P,plotif）;%调用计算费用的子函数

FITNESS（i）=Z;

end

%选择复制采取两两随机配对竞争的方式，具有保留最优个体的能力

Ser=randperm（2*N）;

fori=1:

N

f1=FITNESS（Ser（2*i-1））;

f2=FITNESS（Ser（2*i））;

iff1<=f2

farm{i}=FARM{Ser（2*i-1）};

fitness（i）=FITNESS（Ser（2*i-1））;

else

farm{i}=FARM{Ser（2*i）};

fitness（i）=FITNESS（Ser（2*i））;

end

end

%记录最佳个体和收敛曲线

minfitness=min（fitness）

meanfitness=mean（fitness）

LC1（counter+1）=minfitness;%收敛曲线1，各代最优个体适应值的记录

LC2（counter+1）=meanfitness;%收敛曲线2，各代群体平均适应值的记录

pos=find（fitness==minfitness）;

Xp=farm{pos

（1）};

%第五步：

变异

fori=1:

N

ifPm>rand;%变异概率为Pm

X=farm{i};

I=unidrnd（m）;

J=unidrnd（n）;

X（I,J）=1+（P（J）-eps）*rand;

farm{i}=X;

end

end

farm{pos

（1）}=Xp;

counter=counter+1

end

%输出结果并绘图

figure

（1）;

plotif=1;

X=Xp;

[Zp,Y1p,Y2p,Y3p]=COST（X,T,P,plotif）;

figure

（2）;

plot（LC1）;

figure（3）;

plot（LC2）;

function[Zp,Y1p,Y2p,Y3p]=COST（X,T,P,plotif）

% JSPGA的内联子函数，用于求调度方案的Makespan值

% 输入参数列表

% X   调度方案的编码矩阵，是一个实数编码的m×n矩阵

% T   m×n的矩阵，存储m个工件n个工序的加工时间

% P   1×n的向量，n个工序中，每一个工序所具有的机床数目

% plotif 是否绘甘特图的控制参数

% 输出参数列表

% Zp   最优的Makespan值

% Y1p  最优方案中，各工件各工序的开始时刻

% Y2p  最优方案中，各工件各工序的结束时刻

% Y3p  最优方案中，各工件各工序使用的机器编号

%第一步：

变量初始化

[m,n]=size（X）;

Y1p=zeros（m,n）;

Y2p=zeros（m,n）;

Y3p=zeros（m,n）;

%第二步：

计算第一道工序的安排

Q1=zeros（m,1）;

Q2=zeros（m,1）;

R=X（:

1）;%取出第一道工序

Q3=floor（R）;%向下取整即得到各工件在第一道工序使用的机器的编号

%下面计算各工件第一道工序的开始时刻和结束时刻

fori=1:

P

（1）%取出机器编号

pos=find（Q3==i）;%取出使用编号为i的机器为其加工的工件的编号

lenpos=length（pos）;

iflenpos>=1

Q1（pos

（1））=0;

iflenpos>=2

forj=2:

lenpos

Q1（pos（j））=Q2（pos（j-1））;

Q2（pos（j））=Q2（pos（j-1））+T（pos（j）,1）;

end

end

end

end

Y1p（:

1）=Q1;

Y2p（:

1）=Q2;

Y3p（:

1）=Q3;

%第三步：

计算剩余工序的安排

fork=2:

n

R=X（:

k）;%取出第k道工序

Q3=floor（R）;%向下取整即得到各工件在第k道工序使用的机器的编号

%下面计算各工件第k道工序的开始时刻和结束时刻

fori=1:

P（k）%取出机器编号

pos=find（Q3==i）;%取出使用编号为i的机器为其加工的工件的编号

lenpos=length（pos）;

iflenpos>=1

EndTime=Y2p（pos,k-1）;%取出这些机器在上一个工序中的结束时刻

POS=zeros（1,lenpos）;%上一个工序完成时间由早到晚的排序

forjj=1:

lenpos

MinEndTime=min（EndTime）;

ppp=find（EndTime==MinEndTime）;

POS（jj）=ppp

（1）;

EndTime（ppp

（1））=Inf;

end      

%根据上一个工序完成时刻的早晚，计算各工件第k道工序的开始时刻和结束时刻

Q1（pos（POS

（1）））=Y2p（pos（POS

（1））,k-1）;

Q2（pos（POS

（1）））=Q1（pos（POS

（1）））+T（pos（POS

（1））,k）;%前一个工件的结束时刻

iflenpos>=2

forj=2:

lenpos

Q1（pos（POS（j）））=Y2p（pos（POS（j））,k-1）;%预定的开始时刻为上一个工序的结束时刻

ifQ1（pos（POS（j）））

Q1（pos（POS（j）））=Q2（pos（POS（j-1）））;

end