学生建模报告-工件加工顺序问题

1、Importa nt & Selected Docume nts 工件加工的排序问题 问题提出 现在社会是建立在庞大的工业体系之上的。每天我们的社会都需要消耗大量的工 业产品，而在工业品生产中又存在着许多这样那样的问题， 如如何提高生产效率， 如何在一定的时间内生产出最大的产品价值等等。 下面的问题就是一个具体的例 子。 计划排序问题中的车间作业问题，研究n个工件在每个工件都有完工的日 期（DD，Duedate）,加工的时间（PT, Process in gtime ）和工件的价值（VAL, Valueifjobisselected ）.车间作业计划研究一个工厂生产工序的计划和安排，需 要计划

2、与合理安排各个工件在机器上加工的先后次序，即拟订加工工序，通过各 个工件在机器上加工次序的合理安排，或要求整个选择加工的工件价值最大。 有一个工厂现在有12种工件（编号为工件1，工件2，工件12 ）需要 在车床加工。考虑下面的工件加工的排序问题： 这12种工件都要求在车床上加工，车床一次只能加工一种工件，这12种工件 加工所需时间，每个工件的完工时间和每个工件的价值如表所示： 工件 加工时间（h） 完工时间（h） 工件价值 1 2.8 9 8 2 3.2 7.5 4 3 1.2 15 16 4 4 23 3 5 2.7 10 7 6 0.9 22 20 7 2.5 17 17 Importa

3、nt & Selected Docume nts 8 3.3 33 11 9 1.7 7 7 10 2.5 18 12 11 3.6 25 5 12 4.7 11 18 由于工件必须在它们要求的时间内完工，按照表的数据，为该工厂安排选择 加工工件的种类及加工的次序，使得整个选择加工的工件价值最大。 问题分析 问题最后的要求是要计算生产产品的价值总和的最大化，是一个优化的 问题。 问题的关键就在于每一个工件的加工都有一个完成时间的限制，如何在 限制的时间内完成最大的产品价值。经过最初的分析，由于对于每个工件只 有加工或不加工两种选择，我们可以确定这是一个 0-1规划问题，但是同时 我们又发现以上

4、的要求使用我们模型的约束建立的过程非常的困难。显然如 果按照工件价值从大到小的顺序进行加工就很有可能使完成时间较早的工件 不能加工而又有许多的剩的时间，从而得不到最大的价值。 所以我们不但要考虑工件的价值，而且要考虑工件的加工顺序。正是因 为这一点使我们无法通过数学的形式将这种加工顺序在总价值最大化要求下 体现出来。于是我们考虑了人为的先给出这样的加工顺序，既完成限制时间 较早的工件较早加工（即如下表的加工顺序），而正是这种顺序解决了我们的 问题。这样就可以对每个工件都有考虑。如果我们再加以适当的约束就使问 题简单的解决了 Importa nt & Selected Docume nts 工件

5、 加工时间（h） 完工时间（h） 工件价值 9 1.7 7 7 2 3.2 7.5 4 1 2.8 9 8 5 2.7 10 7 12 4.7 11 18 3 1.2 15 16 7 2.5 17 17 10 2.5 18 12 6 0.9 22 20 4 4 23 3 11 3.6 25 5 8 3.3 33 11 假设及符号设定 假设一个工件加工完成后到另一个工件加工的开始之间的时间不计 :加工工件的总价值 :第n个工件是不是要加工（要加工取“ 1”，不加工取“ 0 ”） 模型建立 模型求解 经过编程求解得：（程序见附表） Thebestchoiceis: 101011111111 Imp

6、ortant & Selected Documents Thelargestvalueis117.000000. 即选择加工的工件既加工顺序为 9，1，12，3，7，10，6，4，11，8 号工件。 按照这样的选择和加工顺序就可以得到最大的生产价值117 。 结果分析与发展 1满足模型约束的像 :101011111111 的序列有多种，每一种可能的方案， 都对应一总价值：Y,和总的加工时间：T。我们可以人为的按照自己的要求给 总价值 Y 和总时间 T 分别赋于不同的权值： p1,p2 。通过计算： P1GY+p2GT （p1+p2=1 ）可以得到满足自己需求的方案,比如加工的时间短,但是价值也 不 怎 么 少 。 我 们 如 果 使 ：p1=2/3,p2=1/3。 此 时 的 目 标 。 maGp1GY+p2GT=94.32 。 2我们只考虑了每个工件