第1页 / 共15页
第2页 / 共15页
第3页 / 共15页
第4页 / 共15页
第5页 / 共15页
第6页 / 共15页
第7页 / 共15页
第8页 / 共15页
数学建模中的工件加工排序.doc
数学建模竞赛试题：
C 题：工件加工排序
计划排序问题中的车间作业问题，研究 n 个工件在 m 台机器上有序的加工问题，每个
工件都有完工的日期（DD，Due date）, 加工的时间（PT，Processing time）和工件的价值
（VAL，Value if job is selected）. 现研究一个工厂生产工序的计划和安排，需要计划与合理
安排各个工件在这些机器上加工的先后次序，即拟订加工工序，通过各个工件在各种机器上
加工次序的合理安排，使得完成这批工件加工任务所需的总时间最省（注：总时间即为各个
零件的加工时间和加工其他零件时它们等待时间之和）或要求整个选择加工的工件价值最
大。
有一个工厂现在有 12 种工件（编号为工件 1，工件 2，…，工件 12）需要在车床，钻
床，铣床几种不同的设备上加工。考虑下面的工件加工的排序问题：
(一) 这 12 种工件都要求在车床上加工，车床一次只能加工一种工件，这 12 种工件加工
所需时间，每个工件的完工时间和每个工件的价值如表（1）所示：
工件
加工时间（h）
完工时间(h)
工件价值
1
2
3
4
5
6
7
8
9
10
11
12
2.8
3.2
1.2
4
2.7
0.9
2.5
3.3
1.7
2.5
3.6
4.7
9
7.5
15
23
10
22
17
33
7
18
25
11
表（1）
8
4
16
3
7
20
17
11
7
12
5
18
1) 不考虑工件的完工时间和工件的价值，为该工厂安排工件加工的次序，使得完成这批
工件加工任务所需的总时间最省。建立数学模型并给出相应的算法。
2) 由于工件必须在它们要求的时间内完工，按照表（1）的数据，为该工厂安排选择加
工工件的种类及加工的次序，使得整个选择加工的工件价值最大。建立数学模型并给
出相应的算法。
(二) 如果这 12 种工件都要求先在车床上加工，然后再在钻床上加工（即工件在钻床加工
之前必须先在车床上加工过），每种机器一次只能加工一种工件，这 12 种工件加工所需
时间如表（2）所示：
- 1 -
工件
1
2
3
4
5
6
7
8
9
10
11
12
车床加工时间（h）
钻床加工时间(h)
2.8
3.2
1.2
4
2.7
0.9
2.5
3.3
1.7
2.5
3.6
4.7
表（2）
4
1.3
1.8
2.2
3
4.5
1.7
2.5
4.5
2.5
3.8
1.9
为该工厂安排工件加工的次序，使得完成这批工件加工任务所需的总时间最省。建立数
学模型并给出相应的算法。
(三) 如果这 12 种工件都要求先在车床上加工，然后再在钻床上加工，最后再在铣床上加
工，每种机器一次只能加工一种工件，这 12 种工件加工所需时间如表（三）所示：
工件
车床加工时间（h）
钻床加工时间(h)
铣床加工时间(h)
1
2
3
4
5
6
7
8
9
10
11
12
2.8
3.2
1.2
4
2.7
0.9
2.5
3.3
1.7
2.5
3.6
4.7
4
1.3
1.8
2.2
3
4.5
1.7
2.5
4.5
2.5
0.9
1.9
表（3）
3
1
2.5
1.3
1.8
2
3.6
0.8
1
1.1
1.3
0.7
为该工厂安排工件加工的次序，使得完成这批工件加工任务所需的总时间最省。建立数
学模型并给出相应的算法。
(四) 对于上述问题你做出的数学模型和相应的算法给出评价。并将模型推广到 n 个工件
在 m 台机器上加工的一般的工件排序问题，给出你的想法和解决问题的思路。
解题正文：
- 2 -
C 题：工件加工排序
（建模小组成员： AP0308306 陈运标 AP0308307 邓风仪 AP0206311 黄深泉）
摘要
本题根据已知数据，结合问题中的具体要求，我们引入 0/1 变量建立工件排
序的数学规划模型。借助 Lingo 软件进行求解运算，得出其中的最优排序方案。
使得完成这批工件加工任务所需要的总时间最省。在这里，我们通过对各个工件
（排序后）完成某项特定工序所需总时间进行求和得到整个加工任务所需要的总
时间。而各工件的总时间包括其机床加工时间和加工其他零件时的等待时间。
模型的假设：在后面的模型中，我们都假定了忽略工件在转换工序时的运输时间。即
将整个工件加工过程简化为一个连续的过程，只考虑机床在加工工件时其他工件的等待时
间。
模型的建立：我们的思路是引入 0/1 变量对工件进行动态排序，根据问题要求得出排
序后的目标函数（即数学模型）。根据题目的约束条件，利用 Lingo 软件算出模型的最优解，
从而获得工件的最优排序。
问题（一）题目要求：12 种工件都要求在车床上加工，车床一次只能加工一种工件。设 i
工件车床加工时间为 A i
,规定完工时间为 B i ,工件价值为 C i
1） 不考虑工件的完工时间和工件的价值，安排工件加工的次序，使得完成这批工件加工任
务所需的总时间最省。
分析：引入 0/1 变量，利用目标函数最优化工件排序。
设 iT 为 i 工 件 实 际 完 工 时 间 ， 所 以 完 成 这 批 工 件 的 总 时 间 为 T=
iT =A 1i +A i =A 2i +A 1i +A i =A 1+A 2 +………+ iA =
i
j
1
A
j
12
, 而
T
i
i
1
因此: 建立问题（1）的目标函数即数学模型为 Min=
i
12
i
1
j
1
A
j
定义 x 1 ，x 2 ……x 144 为 0/1 变量， 1a ， 2a ，… 12a 为原始工件序列下 i 工件的车床加工
时间；所以
- 3 -
A 1=x 1a 1+x 2 a 2 +……..+x 12 a 12
A 2 =x 13 a 1+x 14 a 2 +……..+x 24 a 12
.
.
A 12 =x 133 a 1 +x 134 a 2 +……..+x 144 a 12
x 1+x 2 +…….+x 12 =1
x 13 +x 14 +…….+x 24 =1
.
.
.
x 133 +x 134 +…….+x 144 =1
x 1+x 13 +x 25 +……+x 121 +x 133 =1
x 2 +x 14 +x 26 +……+x 122 +x 134 =1
.
.
.
x 12 +x 24 +x 36 +……+x 132 +x 144 =1
Lingo 程序：（附 wenti(1).lg4 文件）
model:
!不考虑完工时间和工件价值的排序问题;
sets:
gongjian/g1..g12/:shijian; !属性为原始排序下各个工件的机床加工时间;
shunxu/s1..s12/:time,fin_time; !属性为重新排序后各工件的机床加工时间和完成车工序的
时间;
links(shunxu,gongjian): note;
endsets
!目标函数：求各个工件的加工总时间和最小;
min=@sum(shunxu(I):fin_time(I));
!重新排序后各工件的机床加工时间;
@for(shunxu(J):
time(J)=@sum(gongjian(I):shijian(I)*note(I,J));
);
!排序后各个工件的加工总时间;
@for(shunxu(I):
- 4 -
fin_time(I)=@sum(shunxu(J)|J#le#I:time(J));
);
!每个顺序位只能有一个工件;
@for(shunxu(I):
@sum(gongjian(J): note(I,J))=1;
);
!每个工件只能排在一个顺序位上;
@for(gongjian(J):
@sum(shunxu(I): note(I,J))=1;
);
!定义 0/1 变量;
@for(links:@bin(note));
data:
!输出数据到 Excel 文档;
@OLE('D:\liebiao.XLS')=time,fin_time;
!原始排序下各个工件的机床加工时间;
shijian= 2.8,3.2,1.2,4,2.7,0.9,2.5,3.3,1.7,2.5,3.6,4.7;
enddata
end
结果数据：
工件
加工时间 iA 完成时间 T i
6
3
9
10
7
5
1
2
8
11
4
12
0.9
1.2
1.7
2.5
2.5
2.7
2.8
3.2
3.3
3.6
4
4.7
表 1-1
0.9
2.1
3.8
6.3
8.8
11.5
14.3
17.5
20.8
24.4
28.4
33.1
总计：171.9
所以最优排序是 6－3－9－10－7－5－1－2－8－11－4－12
完成这批工件加工任务所需的最省总时间为 171.9
- 5 -
2) 分析：由于工件必须在它们要求的时间内完工，即某工件在任务开始起到该工件加工完
毕之间所用的总时间应少于该工件的规定完工时间。所以要使整个加工任务的工件总价值最
大，必须合理选择加工工件的种类及其加工的次序。
引入 0-1 变量,若选择 i 工件加工,则记 Y i =1.否则记 Y i =0;
工件的排序算法同问题 1），但约束条件有所不同。在本题中，12 种工件不一定都可以入选
到最优加工序列中（即目标排序中可能出现工件空缺），所以
12
X
,
j i
i
1
0
( j =1, 2, ….12)，
且
12
X
j
i
,
j
1
0
(i =1, 2, ….12)， ,i
jX 为 0-1 变量。用 Lingo 进行编程，工件集加入原始排序
下车床加工时间，完工时间和工件价值属性；顺序集加入重新排序后车床加工时间，完工时
间和工件价值属性；因此该模型为：
目标函数: Max=
12
iYC
i
i
1
（在排序算法及程序中已隐含有 iY ）
工件选择：
12
X
,
j i
i
1
0
( j =1, 2, ….12)，
12
X
i
j
,
j
1
0
(i =1, 2, ….12)
完工时间约束：
j
AY
i
i
i
1
B
j
( j =1, 2, ….12)
Lingo 程序：（wenti(2).lg4 文件）
model:
!考虑完工时间和工件价值的排序问题;
sets:
gongjian/g1..g12/:shijian,endtime,gj_value; ! 属性为原始排序下各个工件的机床加工时间，
完工时间，工件价值;
shunxu/s1..s12/:time,overtime,fin_value; ! 属性为重新排序后各个工件的机床加工时间，完
工时间，工件价值;
links(shunxu,gongjian): note;
endsets
!目标函数;
max=@sum(shunxu(I):fin_value(I));
!从新排序后各工件的机床加工时间（可能为零，即表示未选中工件）;
@for(shunxu(I):
time(I)=@sum(gongjian(J):shijian(J)*note(I,J)));
!从新排序后各工件的完工时间（可能为零，即表示未选中工件）;
@for(shunxu(I):
overtime(I)=@sum(gongjian(J):endtime(J)*note(I,J));
);
!从新排序后各工件的工件价值（可能为零，即表示未选中工件）;
@for(shunxu(I):
- 6 -
fin_value(I)=@sum(gongjian(J):gj_value(J)*note(I,J));
);
!每个顺序位只能有一个工件或者没有工件;
@for(shunxu(I):
@sum(gongjian(J): note(I,J))<=1);
!每个工件只能排在一个顺序位上;
@for(gongjian(J):
@sum(shunxu(I): note(I,J))<=1);
!各工件的完工时间约束;
@for(shunxu(I):
@sum(shunxu(J)|J#le#I:time(J))<=overtime(I);
);
!定义 0/1 变量;
@for(links:@bin(note));
data:
!原始排序下各个工件的机床加工时间;
shijian= 2.8,3.2,1.2,4,2.7,0.9,2.5,3.3,1.7,2.5,3.6,4.7;
!原始排序下各个工件的完工时间;
endtime=9,7.5,15,23,10,22,17,33,7,18,25,11;
!原始排序下各个工件的工件价值;
gj_value=8,4,16,3,7,20,17,11,7,12,5,18;
enddata
end
模型结果：
导出列表：
工件顺序
车床加工时间
规定的完工时间
各工件价值
1
5
12
10
3
6
7
2
11
8
0
0
2.8
1.7
4.7
2.5
1.2
0.9
2.5
4
3.6
3.3
表 1-2
0
0
9
7
11
18
15
22
17
23
25
33
0
0
8
7
18
12
16
20
17
3
5
11
总价值：117
由上表可知，最优方案是选择工件 1－5－12－10－3－6－7－2－11－8，并
按此顺序进行加工。从而获得最大的工件总价值为 117.
- 7 -
关于问题（二），（三），（四）
分析：问题（二）要求：如果这 12 种工件都要求先在车床上加工，然后再在钻床上加
工（即工件在钻床加工之前必须先在车床上加工过），每种机器一次只能加工一种工件，求
工件加工的最优排序，使得完成这批工件加工任务所需的总时间最省。根据总时间的定义，
某工件从任务开始时刻起到完成钻床工序止所需要的总时间包括该工件完成车工序的时间，
等待上一个工件加工完的时间（即从该工件在车床加工完毕时刻起到其上一个工件在钻床上
加工完毕这一段时间），该工件在钻床上加工的时间。我们假设i 工件在车床 (1)M 加工所需
时间为 (1)
iX ，在钻床上 (2)M 加工所需时间为 (2)
iX ；i 工件完成在车床 (1)M 加工的总时间为
(1)
iM ；（ 1i ）工件完成在钻床 (2)M 加工的总时间为 (2)
1iM ，（ 1i ）。这里要分两种情况进
行分析：
(2)
iM
1).当 (1)
1iM 时，即i 工件完成车工序的总时间大于或等于（ 1i ）工件完成钻工序的
总时间，此时i工件不需要等待（ 1i ）工件而立即就进入钻工序，因此i 工件完成钻床工序
的总时间表达式为 (2)
iM
(1)
iM +
(2)
iX ;
(2)
iM
2).当 (1)
1iM 时，即i 工件完成车工序的总时间小于或等于（ 1i ）工件完成钻工序的
总时间，此时i工件需要等待（ 1i ）工件完成钻床工序才能进入钻床加工。因此i 工件完成
钻床工序的总时间表达式为 (2)
(2)
iM
(2)
1iM +
iX 。
综合以上两种情况，得到i 工件完成钻床工序的总时间计算公式为
（ 1i ）
iM Max（ (1)
1iM ）+ (2)
iX
iM ， (2)
(2)
同理，对于问题（三），我们也可以得到类似的计算公式.，下面是以列表的形式将这一
推导公式推广到i 工件 j 个工序的情况：
假设 i 工件在车床 (1)M 加工所需时间为 (1)
iX ；在钻床上 (2)M 加工所需时间为 (2)
iX ；在
铣床 (3)M 上加工所需要的时间为 (3)
iX ；在后续的各工序（ ( )jM ）中加工所需要的时间设为
( )j
iX ；下表中内容表示 i 工件从任务开始时刻起到完成 ( )jM 道工序止所需要的总时间 j
iM
- 8 -
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
