工件加工问题.doc

B题 工件加工问题第十三组执笔人：侯慧慧B题：工件加工问题摘要本题目要求中十四个工件都在同一台机床上加工，分别求出在给定的三个条件下的最优加工工序，且一些工件的加工必须在某些工件的加工之后进行。故考虑设0-1变量，建立线性规划模型求解。构造0-1矩阵其中，表示第一号工件，表示第二号工件，表示第十四号工件；表示第一号工件的加工次序为，表示第二号工件的加工次序为，表示第十四号工件的加工次序为。问题1构造目标函数：其中，表示第次加工的工件的加工时间。根据题目条件列出约束条件，用Lingo编程，求解得最佳加工工序为：问题2构造目标函数：，同样根据题目条件列出约束条件，用Lingo编程，求解得最佳加工工序为：问题3构造目标函数：也根据题目条件列出约束条件，用Lingo编程，求解得最佳加工工序为：关键词：0-1变量 线性规划 最优解一、问题的重述现有14件工件等待在一台机床上加工，某些工件的加工必须安排在另一些工件完工以后才能开始，第号工件的加工时间及先期必须完工的工件号由下表给出：工件号12345678910111213142028251642123210242040243616前期工件号3,45，7,85,910，113，8,943，5,744,76,7145,121,2，6(1)若给出一个加工顺序，则确定了每个工件的完工时间（包括等待与加工两个阶段），试设计一个满足条件的加工顺序，使各个加工工件的完工时间之和最小。(2)若第号工件紧接着第号工件完工后开工，机床需要花费的准备时间是，试设计一个满足条件的加工顺序，使机床花费的总时间最小。(3)假定工件的完工时间（包括等待与加工两个阶段）超过一确定时间，则需支付一定的补偿费用，其数值等于超过的时间与费用率之积（各工件的补偿率见下表）：1234567891011121314121015161011108541010812安排一个加工顺序，使得总补偿费最小。二、基本假设与符号说明2.1基本假设(1)假设机床在加工过程中不会出现损坏的情况，一切运转正常；(2)不考虑到其他因素，如每个工件的装卸时间和刀具及夹具更换的时间；(3)每个工件都一次性加工成功，不会出现返工的情况。2.2符号说明第个加工的工件的加工时间第个加工的工件的完成时间14个工件的完工时间之和第次加工的工件的准备时间第次加工的工件的加工时间第一号工件第二号工件 第十四号工件第一号工件的加工次序为第二号工件的加工次序为 第十四号工件的加工次序为各个加工工件的等待时间之和第次加工的工件的编号第号工件的超时数，第号工件的加工次序，第号工件的完工时间（包括等待和加工两个阶段）。三、模型的建立3.1问题一模型一观察题目表格中的数据，每个工件都有自己的加工时间，而又规定：每个工件的完工时间既包括等待阶段，又包括加工阶段，因此，每个工件的完工时间应是前面所有已经加工过的工件的加工时间之和与自身加工时间的总和，设第个加工的工件的加工时间为，完工时间为，则有设14个工件的完工时间之和为，整理得(1)显然，当数列是一个递增序列时，的值最小。下面是简单的证明过程：不妨假设，保持不变，若在(1)式中交换的位置，即有则 模型二题中所给的14个工件都有各自的加工时间，且某些工件还必须安排在另一些工件完工以后才能开始。问题要求给出满足条件的加工顺序，使各个工件的完工时间之和最小，这与排课问题很相似，故可以考虑建立线性规划模型求最优值。构造0-1矩阵其中，表示第一号工件，表示第二号工件，表示第十四号工件；表示第一号工件的加工次序为，表示第二号工件的加工次序为，表示第十四号工件的加工次序为。约束条件的限制：每个工件都只需加工一次，所以0-1矩阵中每行的元素之和为1，即每次只能加工一个工件，所以0-1矩阵中每列的元素之和为1，即上述约束条件和就保证了不同工件间的加工次序不同。前期工件条件的限制：根据题目给出的数据，构造优先关系矩阵：其中，以为例，表明是的前期工件，则工件的加工次序大于工件的加工次序，即：因为要求以加工顺序，使得所有工件的完工时间之和最小，所以有目标函数 其中，表示第次加工的工件的加工时间。 模型三由题目中一些工件加工的先后关系，考虑用数据结构中的DAG图表示各个工件之间的关系，使用拓扑排序的算法求出所有合理的排序序列，然后根据等待加工工件的等待时间之和最小来确定最优的加工顺序。即用下面公式来求出各个加工工件的等待时间之和。其中，第一个加工工件的等待时间为0,表示各个加工工件的等待时间之和，表示第个加工的工件的加工时间。3.2问题二引入0-1变量，其中，表示第一号工件的加工次序为，表示第二号工件的加工次序为，表示第十四号工件的加工次序为。十四个工件的加工时间之和为345，设表示第次加工的工件的准备时间，要使机床花费的时间最少，建立目标函数：设表示第次加工的工件的编号，有约束条件如下： 3.3问题三同上述两问相同，首先引入0-1变量，其中，表示第一号工件的加工次序为，表示第二号工件的加工次序为，表示第十四号工件的加工次序为。根据题目所求，构建目标函数如下：其中，表示第号工件的超时数，表示第号工件的加工次序，表示第号工件的完工时间（包括等待和加工两个阶段）。列出约束条件如下：四、模型的求解与结果4.1问题一4.11模型一根据上面的分析，因为题目的特殊性：有些工件的加工必须在某些工件之后，所以首先在表格中寻找没有前期工件的工件号，只有工件4和10，因为工件4的加工时间比10少，所以优先加工4；接着寻找前期工件只有4号工件的工件，即工件7,9，将其加工时间和10号工件的相比较，选择加工时间最短的10号工件作为第二个加工的工件；然后，再找前期工件号是4或10的工件，即7和9，选择工件9第三个加工。依次类推，每次都在剩余工件中寻找其前期工件均已经完成加工，且所需加工时间最少的工件进行加工，直到所有的14个工件都选择完毕。最终得到的排序序列为：计算得，14个工件的完工时间之和为：4.12模型二利用LINGO编程，对上述模型中的优先关系矩阵中的元素进行操作，使前期工件限制问题得到解决。程序代码如下：MODEL:SETS: TASK/A B C D E F G H I J K L M N/:T; PRED(TASK,TASK)/A,C A,D B,E B,G B,H C,E C,I E,J E,K F,C F,H F,I G,D H,C H,E H,G I,D K,D K,G L,F L,G L,N M,E M,L N,A N,B N,F/; ORDER/1.14/:Y; TXO(TASK,ORDER):X;ENDSETSDATA: T=20 28 25 16 42 12 32 10 24 20 40 24 36 16;ENDDATAFOR(TASK(I):SUM(ORDER(K):X(I,K)=1); FOR(ORDER(K):SUM(TASK(I):X(I,K)=1); FOR(PRED(I,J):SUM(ORDER(K):K*X(I,K)-K*X(J,K)0);FOR(ORDER(K):Y(K)=SUM(TXO(I,K):T(I)*X(I,K);MIN=14*Y(1)+13*Y(2)+12*Y(3)+11*Y(4)+10*Y(5)+9*Y(6)+8*Y(7)+7*Y(8)+6*Y(9)+5*Y(10)+4*Y(11)+3*Y(12)+2*Y(13)+Y(14);FOR(TXO:BIN(X);END运行结果为：排序结果为：其所有工件的完工时间之和为 2588。4.13模型三首先，根据上面表中的前期工件号i(实际上是对应工件序号j顶点的入度)，画出DAG图，图形如下：为了求出全部的加工有序序列，采用了栈进行探索的程序设计方法(直接递归的方法)。编写的程序的主要步骤如下：(1) 定义一个集合类型的数组，并先求出入度为零的顶点的序号，且存放在S1中，此题的S1为4,10。然后再求出其他集合中允许加工的顶点的集合。(2) 用栈进行探索的方法求出符合要求的全部加工有序序列。(3) 编写输出每一种加工序列的过程。(4) 按上述公式求出每种加工序列中各个加工工件的等待时间之和并排序。结果表明，拓扑排序的结果不唯一，共有多种可选择的加工方案。通过编程排序，可以求得最优拓扑排序序列。4.2问题二利用Lingo编程求最优解，程序代码如下：MODEL:SETS: TASK/A B C D E F G H I J K L M N/:T; PRED(TASK,TASK)/A,C A,D B,E B,G B,H C,E C,I E,J E,K F,C F,H F,I G,D H,C H,E H,G I,D K,D K,G L,F L,G L,N M,E M,L N,A N,B N,F/; ORDER/1.14/:Y; KONG/1.13/:Z; TXO(TASK,ORDER):X;ENDSETSDATA: T=1 2 3 4 5 6 7 8 9 10 11 12 13 14; SUM=345;ENDDATAFOR(TASK(I):SUM(ORDER(K):X(I,K)=1); FOR(ORDER(K):SUM(TASK(I):X(I,K)=1); FOR(PRED(I,J):SUM(ORDER(K):K*X(I,K)-K*X(J,K)0);FOR(ORDER(K):SUM(TXO(I,K):T(I)*X(I,K)=Y(K);FOR(KONG(I):Z(I)=IF(Y(I+1)#GT#Y(I),Y(I)+Y(I+1),2*(Y(I)-Y(I+1);MIN=SUM(KONG(J):Z(J);FOR(TXO:BIN(X);END运行结果为：求得的加工顺序为：其机床花费的最少时间为： 4.3问题三使用Lingo编程求最优解，程序代码如下：MODEL:SETS: TASK/A B C D E F G H I J K L M N/:T; PRED(TASK,TASK)/A,C A,D B,E B,G B,H C,E C,I E,J E,K F,C F,H F,I G,D H,C H,E H,G I,D K,D K,G L,F L,G L,N M,E M,L N,A N,B N,F/; ORDER/1.14/:Y,Z,Q; TXO(TASK,ORDER):X;ENDSETSDATA: T=1 2 3 4 5 6 7 8 9 10 11 12 13 14;ENDDATAFOR(TASK(I):SUM(ORDER(K):X(I,K)=1); FOR(ORDER(K):SUM(TASK(I):X(I,K)=1); FOR(PRED(I,J):SUM(ORDER(K):K*X(I,K)-K*X(J,K)0);FOR(TASK(K):Y(K)=SUM(TXO(K,I):T(I)*X(K,I);!变化了 根据工件看次序;FOR(ORDER(K):Z(K)=IF(Y(K)#GE#Y(1),20,0)+IF(Y(K)#GE#Y(2),28,0)+IF(Y(K)#GE#Y(3),25,0)+IF(Y(K)#GE#Y(4),16,0)+IF(Y(K)#GE#Y(5),42,0)+IF(Y(K)#GE#Y(6),12,0)+IF(Y(K)#GE#Y(7),32,0) +IF(Y(K)#GE#Y(8),10,0)+IF(Y(K)#GE#Y(9),24,0)+IF(Y(K)#GE#Y(10),20,0) +IF(Y(K)#GE#Y(11),40,0)+IF(Y(K)#GE#Y(12),24,0)+IF(Y(K)#GE#Y(13),36,0) +IF(Y(K)#GE#Y(14),16,0);FOR(ORDER(I):Q(I)=IF(Z(I)#GT#100,Z(I)-100,0);MIN=12*Q(1)+10*Q(2)+15*Q(3)+16*Q(4)+10*Q(5)+11*Q(6)+10*Q(7)+8*Q(8)+5*Q(9)+4*Q(10)+10*Q(11)+10*Q(12)+8*Q(13)+12*Q(14);FOR(TXO:BIN(X);END运行结果为：求得的排序序列为：其总补偿费为： 五、模型的优缺点本次题目所使用的模型简单易懂，结果准确；但是使用Lingo编程时