B题 工件加工
组号：14
执笔人：彭嘉续
B题 工件加工
摘要
本文探讨的问题是如何安排工件的加工顺序以使得各工件的完工时间之和最短、机床花费的总时间最小、加工工件的总补偿费用最少。求解这一问题主要用到了图论和线性规划的数学方法。在第一问与第三问中，本文先将题中所给出的数据、条件转换为图，在此基础上表示出目标函数及约束条件，利用非线性规划求得最优解。第二问中，文本利用了图论中哈密顿链原理，将完成工件加工的问题转化为有向图中点的遍历，所建立的模型可遍历哈密顿链中的全部点且得到最短路径。
最终求解模型，结果如下：
(1) 加工顺序为4→10→9→7→11→5→3→8→6→1→2→14→12→13时，各工件的完工时间和最小，为2588。
(2) 加工顺序为4→7→11→10→9→5→3→8→6→2→1→14→12→13时，机床花费的总时间最小，为114。
(3) 加工顺序为4→7→11→10→5→9→3→8→6→1→2→14→12→13时，总补偿费最小，为142.42。
关键词：工件加工；非线性规划；图论；哈密顿链；最优化
1
一、问题重述与分析
1、问题重述
现有14件工件等待在一台机床上加工，某些工件的加工必须安排在另一些工件加工完工以后才能开始，第j号工件的加工时间tj及先期必须完工的工件号i由下表给出。 工件号j tj 0 前期工件号4 3,28 5,7,8 9 25 5,26 - 12 10,142 3,8,9 12 4 30 3,5,7 14 4 20 - 7 1 2 3 4 5 6 7 8 9 0 20 4,11 44 6,7,112 26 5,12 13 36 1,2,6 14 11（1） 若给出一个加工工序，则确定了每个工件的完工时间（包括等待与加工两个阶段）。试设计一个满足条件的加工顺序，使各工件的完工时间之和最小。 （2） 若第j号工件紧接着第i号工件完工后开工，机床需要花费的准备时间是：
?i?ji?j tij??
?2(i?j)i?j（3） 假定工件的完工时间（包括等待与加工两个阶段）超过一确定时限u时，则需支付一定的补偿费用，其数值等于超过时间与费用率之积，各工件的补偿费用率ωi如下： j ωi 1 12 2 10 3 15 4 16 5 10 6 11 7 10 8 8 9 5 10 4 11 10 12 10 13 8 14 12 u=100，tij=0，安排一个加工顺序，使总补偿最小。 2、问题分析
三个问题都是要求一种最优加工次序，使得工件完工时间和、机床花费时间、总补偿费分别达到最小。由于题中安排了各工件的前期工件，所以解题时可以先利用图论的知识将加工工件之间的先后关系表示出来。由于第j号工件完工时间和补偿费与其前置加工工件完工时间的累加密切相关，所以单纯用图论解决完工时间和补偿费的最优化是很复杂的，但是可以在有向图的基础上将目标函数、约
2
束条件巧妙表示出来，再结合非线性规划解出最优解。在第二问中，求得的是机床花费总时间的最小值问题，实质就是要解决机床的总准备时间最短的问题。该问题可转化为最短路径问题，但是同时要考虑到各加工工件的前期工件。这就需要构造一个好的有向图，再遍历点并求得最短路径。
二、模型假设与符号说明
1、模型假设
(1) 假设相邻工件之间的加工是紧挨着进行的，即除了准备时间外，不浪费任何时间。
(2) 假设机床在加工工件的过程中运转正常。 (3) 假设 2、符号说明
yi—第i号工件在加工流程中的加工序号 Z1—各工件完工时间之和 Z2—机床花费的总时间
Z3—加工时的总补偿费
wij—表示从节点i(表示加工工件i)到节点j(表示加工工件j)的准备时间。
xij—是0-1变量，表示是否选取直接从加工第i号工件接替到加工第j号工件这一顺序
?0，表示选取了从加工i号工件到加工j号工件的顺序
xij???1，表示不选取从加工i号工件到加工j号工件的顺序
三、模型建立与求解
1、总完工时间最优模型
问题1中要求根据各个工件的加工时间，以及其前期工件的要求，建立以总的完工时间最少为目标的目标函数。在加工时间一定的情况下，对其进行合理的排序，使目标函数达到最小值。
3
(1)模型建立
总的完工时间包括各工件的等待时间之和与各工件的加工时间之和。由于各工件的加工时间之和是一定的，所以完工时间最优问题等价于各工件等待时间总和的最优化问题。
设第i个工件的加工次序为yi，总的完工时间为Z1。
每个工件都被其后置加工工件所等待，因此，总的工件等待时间即每个工件被等待的时间总和。
第i个工件被等待的时间为(14-yi)ti，则所有工件被等待的时间为?(14?yi)ti
i?114所有工件的加工时间为?ti=345
i?114因此总的完工时间之和为：Z1??(14?yi)ti??ti??(15?yi)ti。
i?1i?1i?1141414(2) 约束条件分析
设yi是yj的前期工件，则第i个工件的加工次序应早于第j个工件的加工次序，所以yi?yj
由题目当中的表可得约束条件为：
y1-y3?1;y2-y8?1;y3-y5?1;y3-y9?1;y5-y10?1;y5-y11?1;y6-y8?1;y7-y4?1;y8-y3?1;y9-y4?1;y11-y7?1;y12-y14?1;y13-y12?1;y14-y1?1;y14-y2?1;y14-y6?1;(y10-y11)2?1;(y1-y2)2?1;(y1-y6)2?1;(y2-y6)2?1;y13=14;y4=1;
yi均为正整数，i=1,2,3…14。 (3) 相关图形
由题目中的表可作图如下：
4