工件加工问题.doc

B题 工件加工问题 第十三组 执笔人：侯慧慧  B题：工件加工问题 摘要 本题目要求中十四个工件都在同一台机床上加工，分别求出在给定的三个条件下的最优加工工序，且一些工件的加工必须在某些工件的加工之后进行。故考虑设0-1变量，建立线性规划模型求解。构造0-1矩阵 其中，表示第一号工件，表示第二号工件，，表示第十四号工件；表示第一号工件的加工次序为，表示第二号工件的加工次序为，，表示第十四号工件的加工次序为。 问题1构造目标函数： 其中，表示第次加工的工件的加工时间。根据题目条件列出约束条件，用Lingo编程，求解得最佳加工工序为： 问题2构造目标函数：，同样根据题目条件列出约束条件，用Lingo编程，求解得最佳加工工序为： 问题3构造目标函数： 也根据题目条件列出约束条件，用Lingo编程，求解得最佳加工工序为： 关键词：0-1变量 线性规划 最优解 一、问题的重述 现有14件工件等待在一台机床上加工，某些工件的加工必须安排在另一些工件完工以后才能开始，第号工件的加工时间及先期必须完工的工件号由下表给出： 工件号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 20 28 25 16 42 12 32 10 24 20 40 24 36 16 前期 工件号 3,4 5， 7,8 5,9 — 10， 11 3， 8,9 4 3， 5,7 4 — 4,7 6,7 14 5, 12 1, 2，6 (1)若给出一个加工顺序，则确定了每个工件的完工时间（包括等待与加工两个阶段），试设计一个满足条件的加工顺序，使各个加工工件的完工时间之和最小。 (2)若第号工件紧接着第号工件完工后开工，机床需要花费的准备时间是， 试设计一个满足条件的加工顺序，使机床花费的总时间最小。 (3)假定工件的完工时间（包括等待与加工两个阶段）超过一确定时间，则需支付一定的补偿费用，其数值等于超过的时间与费用率之积（各工件的补偿率见下表）： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 12 10 15 16 10 11 10 8 5 4 10 10 8 12 安排一个加工顺序，使得总补偿费最小。 二、基本假设与符号说明 2.1基本假设 (1)假设机床在加工过程中不会出现损坏的情况，一切运转正常； (2)不考虑到其他因素，如每个工件的装卸时间和刀具及夹具更换的时间——第个加工的工件的加工时间 ——第个加工的工件的完成时间 ——14个工件的完工时间之和 ——第次加工的工件的准备时间 ——第次加工的工件的加工时间 ——第一号工件 ——第二号工件 ——第十四号工件 ——第一号工件的加工次序为 ——第二号工件的加工次序为 ——第十四号工件的加工次序为 ——各个加工工件的等待时间之和 ——第次加工的工件的编号 ——第号工件的超时数， ——第号工件的加工次序， ——第号工件的完工时间（包括等待和加工两个阶段）。 三、模型的建立 3.1问题一 模型一 观察题目表格中的数据，每个工件都有自己的加工时间，而又规定：每个工件的完工时间既包括等待阶段，又包括加工阶段，因此，每个工件的完工时间应是前面所有已经加工过的工件的加工时间之和与自身加工时间的总和，设第个加工的工件的加工时间为，完工时间为，则有 设14个工件的完工时间之和为，整理得 (1) 显然，当数列是一个递增序列时，的值最小。下面是简单的证明过程： 不妨假设，保持不变，若在(1)式中交换的位置，即有 则 模型二 题中所给的14个工件都有各自的加工时间，且某些工件还必须安排在另一些工件完工以后才能开始。问题要求给出满足条件的加工顺序，使各个工件的完工时间之和最小，这与排课问题很相似，故可以考虑建立线性规划模型求最优值。 构造0-1矩阵 其中，表示第一号工件，表示第二号工件，，表示第十四号工件；表示第一号工件的加工次序为，表示第二号工件的加工次序为，，表示第十四号工件的加工次序为。 约束条件的限制： ①每个工件都只需加工一次，所以0-1矩阵中每行的元素之和为1，即 ②每次只能加工一个工件，所以0-1矩阵中每列的元素之和为1，即 上述约束条件①和②就保证了不同工件间的加工次序不同。 ③前期工件条件的限制：根据题目给出的数据，构造优先关系矩阵： 其中，以为例，表明是的前期工件，则工件的加工次序大于工件的加工次序，即： 因为要求以加工顺序，使得所有工件的完工时间之和最小，所以有 目标函数 其中，表示第次加工的工件的加工时间。 模型三 由题目中一些工件加工的先后关系，考虑用数据结构中的DAG图表示各个工件之间的关系，使用拓扑排序的算法求出所有合理的排序序列，然后根据等待加工工件的等待时间之和最小来确定最优的加工顺序。即用下