武汉科技大学第六届数学建模竞赛
承 诺 书
我们仔细阅读了武汉科技大学第六届数学建模竞赛的竞赛细则。
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。
参赛队员 (手写签名) ：
队员1：
队员2：
队员3：
武汉科技大学数学建模协会
武汉科技大学第六届数学建模竞赛
论 文
队员信息
监制: 武汉科技大学数学建模协会
题目：A 题：装配线平衡问题的随机算例生成
【摘 要】
装配线平衡问题是制造业和其它流水生产行业中的一类重要问题。目前针对这类问题已有较多有效的求解算法，但是算法的有效性检验主要依赖对标杆算例的求解。由于标杆算例的个数有限，所以检验的可靠性难以信服。我们希望对随机生成的大量实验数据进行求解，验证算法的有效性。
本文通过利用统计分析的方法，依据操作时间具有随机性与独立性，假设其满足统计分布规律中的正态分布，而对于操作间优先关系我们假设其满足均匀分布的规律。通过对于操作时间的随机性与操作优先关系间的随机性研究，在满足统计规律的条件下，随机生成装配线平衡问题中的操作时间数组和直接优先关系矩阵。
通过随机生成的装配线平衡问题的随机算例，可以增强对于给定算法有效性检验的可靠性。
关键字：装配线平衡 随机算例 正态分布 均匀分布 检验可靠性
一．问题重述
装配线平衡问题是制造业和其它流水生产行业中的一类重要问题。装配线平衡问题可描述为：给定一个存在优先关系的操作集合和一个工位集合，将操作分配至各个工位，要求每项操作只能被分配至一个工位，每个工位可包含多项操作，但其作业时间不能超出装配线的节拍，其主要目标是使得各个工位的工位时间达到平衡。 目前针对这类问题已有较多有效的求解算法，但是算法的有效性检验主要依赖对标杆算例的求解。由于标杆算例的个数有限，所以检验的可靠性难以信服。我们希望对随机生成的大量实验数据进行求解，验证算法的有效性。为了生成随机算例，你需要先随机生成算例中的基本参数，包含操作的个数，操作时间的最大、最小值和优先关系的个数，再依据操作时间的某种统计分布规律（自己可自由选用合适的统计规律，选用时需给出理由）和操作间优先关系的某个统计规律（同上），生成装配线平衡问题的操作时间数组和直接优先关系矩阵；最后根据所生成的直接优先关系矩阵，生成其优先关系矩阵。
所需要解决的问题如下：
（1）给出随机算例生成的理论依据，如所用统计规律的依据，所生成优先关系矩阵的可行性控制策略等；
（2）给出随机算例生成算法的一般步骤（语言描述，不能使用伪代码或者流程图形式）；
（3）编写随机算例生成函数，就300项操作，200个优先关系生成一组随机算例，算例数据为操作时间数组、直接优先关系矩阵和优先关系矩阵。
二．问题假设与符号说明
1. 问题假设：
（1）任务时间是服从正态分布的随机分布。 （2）任务间操作的优先关系是服从均匀分布的。 （3）序号大的操作不可能是序号小的优先操作。
2. 符号说明： J:随机生成的操作个数
tmax:随机生成操作时间时的上限 tmin:随机生成操作时间时的下限 S:优先关系个数 P:直接优先关系矩阵 FY:优先关系矩阵
三．问题分析
为了生成随机算例，需要先随机生成算例中的基本参数，包含操作的个数，操作时间的最大、最小值和优先关系的个数及操作间的优先关系。
对于操作的个数及操作时间的最大值, 最小值及优先关系个数，可以同过随机数生成器生成。
对于各个操作的操作时间的分布，由于装配线上各个操作具有一定的相似性与独立性，则我们可以假定操作时间t 在最大值与最小值之间波动，其中期望为u=μ，方差为d=σ^2, t~N（μ，σ^2）, 由数学变换可知，经过变换可将其变换为标准正态分布t~N （0，1）, 通过生成时间随机数序列然后乘以时间上限tmax, 再从其中按序选出满足要求的时间组。
对于操作间的优先关系，可以同调整使得序号大的不可能成为序号小的优先操作，这样也可以使得操作间不会陷入死循环，保证其可行性。由于操作间关系具有随机性，可以通过均匀分布产生不重复随机数的方法来产生直接优先矩阵。再由直接优先矩阵生成优先矩阵。
例如记直接优先关系矩阵为P ，矩阵的元素可取值为0或1，当
P i , i '=1
时，表示操作i '为操作i 的直接优先操作，否则取 P i , i '=0。
记优先关系矩阵为Q ，矩阵的元素可取值为0或1，当Q i , i '=1时，表示操作i '为操作i 的直接优先操作，否则取 Q i , i '=0。
四．算法步骤
1. 利用随机数生成器随机生成给定范围一个操作数J.
2. 随机生成操作时间的最大值tmax 与最小值tmin ，检查最大值与最小值保证其有效性。
3. 由正态分布随机数生成器生成在一系列随机数，从中按序选出在最大值与最小值范围内的数，由此构成操作时间序列t 。
4. 通过均匀分布随机数生成器生成随机数组，由该随机数组指定操作间的直接优先关系，由此生成操作间直接优先关系矩阵P 。 5. 通过直接优先矩阵P , 逐步查找，生成优先关系矩阵FY 。
五．模型分析
本文分析的是如何随机生成的大量实验数据进行求解，验证装配线平衡算法的有效性并增加其可靠性。首先根据其随机性，对于操作个数J ，操作时间最大tmax ，最小值tmin, 可以通过随机数生成模型产生，根据对于操作时间t 与操作间直接优先关系P 的随机性分析，我们可以建立正态分布模型求解操作时间t 序列，建立均匀分布模型求解操作间关系P 。由P 则可得出操作间优先关系矩阵FY 。
通过最终生成的操作个数J, 操作时间序列t 及操作间直接优先关系矩阵P, 则可确定一个随机生成的算例。
六．模型建立与求解
根据所建立的数学模型，编写求解程序，运行即可得随机生成的算例。
例如：（任务数小于10时） 随机算例： 任务个数: J = 5
随机工作时间组: t =
12 4 10 20 1 优先关系个数: S = 6 直接优先矩阵: P =
0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 1 0
优先关系矩阵： FY =
0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 1 0
七．模型的应用
在对于解决装配线问题的算法进行分析时，可以通过控制随机数生成的范围，对生成的随机算例加以约束，由此生成符合条件的随机算例，通过随机算例来检验原算法的有效性，将更加可靠。
八．模型评价与总结
此模型考虑随机状态下，装配线流程的随机算例，一定程度上可以增加装配线平衡算法检验的可靠性。但是，由于未通过大量数据间的研究，无法准确判断操作时间服从的统计规律和操作之间的关系服从的统计规律，因此在应用时，还是存在一定的偏差。
九．参考文献
[1] 茆诗松《概率论与数理统计》 [2] 李德宜 李明 《数学建模》
[3] 黄卫平 张建 周支立 《随机型混合模式装配线平衡问题的集束搜索算法 西安交通大学
http://www.doc88.com/p-[1**********]31.html
[4] 苑清敏 李健《具有随机作业时间的装配线平衡方法》 天津理工学院 http://www.doc88.com/p-[1**********]9.html
附录：
函数程序代码：
%%随机生成算例
%%操作个数 J
%%操作时间最大值 tmax
%%操作时间最小值 tmin
%%优先关系个数 S
%%假设单个任务操作时间不超过20，任务个数不超过100
clc;
clear;
J=randint(1,1,[3,10]);
J=300;
disp('任务个数:');
J
tmax=randint(1,20,[0,20]);
tmax=max(tmax);
tmin=randint(1,20,[0,20]);
tmin=min(tmin);
if tmin==0
tmin=1;
end
if tmax
t=tmax;
tmax=tmin;
tmin=t;
if tmax==tmin
tmin=floor(tmax/2);
end
end
%%生成时间序列
J1=J;
t=randn(1,J)*tmax;
t=floor(t);
tnum=length(find(t>=tmin&t
J11=J1-2;
while tnum
J=J*J1;
t=randn(1,J)*tmax;
t=floor(t);
tnum=length(find(t>=tmin&t
end
tt=find(t>=tmin&t
time(i)=t(tt(i));
end
time(i+1)=tmin;
time(i+2)=tmax;
xulie=randperm(J1);
t=[];
for i=1:J1
t(i)=time(xulie(i));
end
disp('随机工作时间组:');
t
%%直接优先矩阵
ss=J1*(J1-1)/2;
S=randint(1,10,[1,ss]); %%优先关系个数
S=ceil(mean(S)); %%为防止优先关系个数过大或过小，多次取随机值求其均值
S=200;
disp('优先关系个数:');
S
pr=randperm(ss);
for j=1:J1-1
A(j)=j*(j+1)/2;
end
P=zeros(J1,J1);
for k=1:S
kk=[];
pr(k);
kk=find(A>=pr(k));
col=kk(1)+1;
col1=(col-1)*(col-2)/2;
row=pr(k)-col1;
P(row,col)=1;
end
P=P'; %%直接优先矩阵
disp('直接优先矩阵:');
P
%%优先矩阵生成
Y=P;
YF=zeros(J1,J1);
for i=2:J1
if ~any(Y(i,:))
continue;
else
place=[];
place=find(Y(i,:)~=0);
for k=1:length(place)
pz=find(YF(i,:)==0);
YF(i,pz(1))=place(k);
end
place=find(YF(i,:)~=0);
for j=1:length(place)
temp=Y(YF(i,place(j)),:);
tempp=find(temp~=0);
if length(tempp)~=0
pw=find(YF(i,:)==0);
for k=1:length(tempp)
if isempty(find(YF(i,:)==YF(YF(i,place(j)),k)))
YF(i,pw(1))=YF(YF(i,place(j)),k); end
end
end
end
end
end
FY=zeros(J1,J1);
for i=1:J1
if isempty(find(YF(i,:)~=0))
continue;
else
V=find(YF(i,:)~=0);
for j=1:length(V)
FY(i,YF(i,V(j)))=1;
end
end
end
disp('优先关系矩阵：');
FY
武汉科技大学第六届数学建模竞赛
承 诺 书
我们仔细阅读了武汉科技大学第六届数学建模竞赛的竞赛细则。
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。
参赛队员 (手写签名) ：
队员1：
队员2：
队员3：
武汉科技大学数学建模协会
武汉科技大学第六届数学建模竞赛
论 文
队员信息
监制: 武汉科技大学数学建模协会
题目：A 题：装配线平衡问题的随机算例生成
【摘 要】
装配线平衡问题是制造业和其它流水生产行业中的一类重要问题。目前针对这类问题已有较多有效的求解算法，但是算法的有效性检验主要依赖对标杆算例的求解。由于标杆算例的个数有限，所以检验的可靠性难以信服。我们希望对随机生成的大量实验数据进行求解，验证算法的有效性。
本文通过利用统计分析的方法，依据操作时间具有随机性与独立性，假设其满足统计分布规律中的正态分布，而对于操作间优先关系我们假设其满足均匀分布的规律。通过对于操作时间的随机性与操作优先关系间的随机性研究，在满足统计规律的条件下，随机生成装配线平衡问题中的操作时间数组和直接优先关系矩阵。
通过随机生成的装配线平衡问题的随机算例，可以增强对于给定算法有效性检验的可靠性。
关键字：装配线平衡 随机算例 正态分布 均匀分布 检验可靠性
一．问题重述
装配线平衡问题是制造业和其它流水生产行业中的一类重要问题。装配线平衡问题可描述为：给定一个存在优先关系的操作集合和一个工位集合，将操作分配至各个工位，要求每项操作只能被分配至一个工位，每个工位可包含多项操作，但其作业时间不能超出装配线的节拍，其主要目标是使得各个工位的工位时间达到平衡。 目前针对这类问题已有较多有效的求解算法，但是算法的有效性检验主要依赖对标杆算例的求解。由于标杆算例的个数有限，所以检验的可靠性难以信服。我们希望对随机生成的大量实验数据进行求解，验证算法的有效性。为了生成随机算例，你需要先随机生成算例中的基本参数，包含操作的个数，操作时间的最大、最小值和优先关系的个数，再依据操作时间的某种统计分布规律（自己可自由选用合适的统计规律，选用时需给出理由）和操作间优先关系的某个统计规律（同上），生成装配线平衡问题的操作时间数组和直接优先关系矩阵；最后根据所生成的直接优先关系矩阵，生成其优先关系矩阵。
所需要解决的问题如下：
（1）给出随机算例生成的理论依据，如所用统计规律的依据，所生成优先关系矩阵的可行性控制策略等；
（2）给出随机算例生成算法的一般步骤（语言描述，不能使用伪代码或者流程图形式）；
（3）编写随机算例生成函数，就300项操作，200个优先关系生成一组随机算例，算例数据为操作时间数组、直接优先关系矩阵和优先关系矩阵。
二．问题假设与符号说明
1. 问题假设：
（1）任务时间是服从正态分布的随机分布。 （2）任务间操作的优先关系是服从均匀分布的。 （3）序号大的操作不可能是序号小的优先操作。
2. 符号说明： J:随机生成的操作个数
tmax:随机生成操作时间时的上限 tmin:随机生成操作时间时的下限 S:优先关系个数 P:直接优先关系矩阵 FY:优先关系矩阵
三．问题分析
为了生成随机算例，需要先随机生成算例中的基本参数，包含操作的个数，操作时间的最大、最小值和优先关系的个数及操作间的优先关系。
对于操作的个数及操作时间的最大值, 最小值及优先关系个数，可以同过随机数生成器生成。
对于各个操作的操作时间的分布，由于装配线上各个操作具有一定的相似性与独立性，则我们可以假定操作时间t 在最大值与最小值之间波动，其中期望为u=μ，方差为d=σ^2, t~N（μ，σ^2）, 由数学变换可知，经过变换可将其变换为标准正态分布t~N （0，1）, 通过生成时间随机数序列然后乘以时间上限tmax, 再从其中按序选出满足要求的时间组。
对于操作间的优先关系，可以同调整使得序号大的不可能成为序号小的优先操作，这样也可以使得操作间不会陷入死循环，保证其可行性。由于操作间关系具有随机性，可以通过均匀分布产生不重复随机数的方法来产生直接优先矩阵。再由直接优先矩阵生成优先矩阵。
例如记直接优先关系矩阵为P ，矩阵的元素可取值为0或1，当
P i , i '=1
时，表示操作i '为操作i 的直接优先操作，否则取 P i , i '=0。
记优先关系矩阵为Q ，矩阵的元素可取值为0或1，当Q i , i '=1时，表示操作i '为操作i 的直接优先操作，否则取 Q i , i '=0。
四．算法步骤
1. 利用随机数生成器随机生成给定范围一个操作数J.
2. 随机生成操作时间的最大值tmax 与最小值tmin ，检查最大值与最小值保证其有效性。
3. 由正态分布随机数生成器生成在一系列随机数，从中按序选出在最大值与最小值范围内的数，由此构成操作时间序列t 。
4. 通过均匀分布随机数生成器生成随机数组，由该随机数组指定操作间的直接优先关系，由此生成操作间直接优先关系矩阵P 。 5. 通过直接优先矩阵P , 逐步查找，生成优先关系矩阵FY 。
五．模型分析
本文分析的是如何随机生成的大量实验数据进行求解，验证装配线平衡算法的有效性并增加其可靠性。首先根据其随机性，对于操作个数J ，操作时间最大tmax ，最小值tmin, 可以通过随机数生成模型产生，根据对于操作时间t 与操作间直接优先关系P 的随机性分析，我们可以建立正态分布模型求解操作时间t 序列，建立均匀分布模型求解操作间关系P 。由P 则可得出操作间优先关系矩阵FY 。
通过最终生成的操作个数J, 操作时间序列t 及操作间直接优先关系矩阵P, 则可确定一个随机生成的算例。
六．模型建立与求解
根据所建立的数学模型，编写求解程序，运行即可得随机生成的算例。
例如：（任务数小于10时） 随机算例： 任务个数: J = 5
随机工作时间组: t =
12 4 10 20 1 优先关系个数: S = 6 直接优先矩阵: P =
0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 1 0
优先关系矩阵： FY =
0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 1 0
七．模型的应用
在对于解决装配线问题的算法进行分析时，可以通过控制随机数生成的范围，对生成的随机算例加以约束，由此生成符合条件的随机算例，通过随机算例来检验原算法的有效性，将更加可靠。
八．模型评价与总结
此模型考虑随机状态下，装配线流程的随机算例，一定程度上可以增加装配线平衡算法检验的可靠性。但是，由于未通过大量数据间的研究，无法准确判断操作时间服从的统计规律和操作之间的关系服从的统计规律，因此在应用时，还是存在一定的偏差。
九．参考文献
[1] 茆诗松《概率论与数理统计》 [2] 李德宜 李明 《数学建模》
[3] 黄卫平 张建 周支立 《随机型混合模式装配线平衡问题的集束搜索算法 西安交通大学
http://www.doc88.com/p-[1**********]31.html
[4] 苑清敏 李健《具有随机作业时间的装配线平衡方法》 天津理工学院 http://www.doc88.com/p-[1**********]9.html
附录：
函数程序代码：
%%随机生成算例
%%操作个数 J
%%操作时间最大值 tmax
%%操作时间最小值 tmin
%%优先关系个数 S
%%假设单个任务操作时间不超过20，任务个数不超过100
clc;
clear;
J=randint(1,1,[3,10]);
J=300;
disp('任务个数:');
J
tmax=randint(1,20,[0,20]);
tmax=max(tmax);
tmin=randint(1,20,[0,20]);
tmin=min(tmin);
if tmin==0
tmin=1;
end
if tmax
t=tmax;
tmax=tmin;
tmin=t;
if tmax==tmin
tmin=floor(tmax/2);
end
end
%%生成时间序列
J1=J;
t=randn(1,J)*tmax;
t=floor(t);
tnum=length(find(t>=tmin&t
J11=J1-2;
while tnum
J=J*J1;
t=randn(1,J)*tmax;
t=floor(t);
tnum=length(find(t>=tmin&t
end
tt=find(t>=tmin&t
time(i)=t(tt(i));
end
time(i+1)=tmin;
time(i+2)=tmax;
xulie=randperm(J1);
t=[];
for i=1:J1
t(i)=time(xulie(i));
end
disp('随机工作时间组:');
t
%%直接优先矩阵
ss=J1*(J1-1)/2;
S=randint(1,10,[1,ss]); %%优先关系个数
S=ceil(mean(S)); %%为防止优先关系个数过大或过小，多次取随机值求其均值
S=200;
disp('优先关系个数:');
S
pr=randperm(ss);
for j=1:J1-1
A(j)=j*(j+1)/2;
end
P=zeros(J1,J1);
for k=1:S
kk=[];
pr(k);
kk=find(A>=pr(k));
col=kk(1)+1;
col1=(col-1)*(col-2)/2;
row=pr(k)-col1;
P(row,col)=1;
end
P=P'; %%直接优先矩阵
disp('直接优先矩阵:');
P
%%优先矩阵生成
Y=P;
YF=zeros(J1,J1);
for i=2:J1
if ~any(Y(i,:))
continue;
else
place=[];
place=find(Y(i,:)~=0);
for k=1:length(place)
pz=find(YF(i,:)==0);
YF(i,pz(1))=place(k);
end
place=find(YF(i,:)~=0);
for j=1:length(place)
temp=Y(YF(i,place(j)),:);
tempp=find(temp~=0);
if length(tempp)~=0
pw=find(YF(i,:)==0);
for k=1:length(tempp)
if isempty(find(YF(i,:)==YF(YF(i,place(j)),k)))
YF(i,pw(1))=YF(YF(i,place(j)),k); end
end
end
end
end
end
FY=zeros(J1,J1);
for i=1:J1
if isempty(find(YF(i,:)~=0))
continue;
else
V=find(YF(i,:)~=0);
for j=1:length(V)
FY(i,YF(i,V(j)))=1;
end
end
end
disp('优先关系矩阵：');
FY