排序问题课件.pptVIP

排序问题 数学规划建模案例之一 舒兴明 1、 工件排序问题（一台机器前的加工排序） 2、 工件排序（两台机器加工顺序） 4、面试问题 * 某车间只有一台高精度磨床，常常出现许多零件同时要求这台磨床加工的情况，现有6个零件同时要求加工，加工完即送到其它车间，这6个零件的加工时间如下表： 零 件 加工时间/小时 1 2 3 4 5 6 1.8 2.0 0.5 0.9 1.3 1.5 应该按照什么样的顺序加工这6个零件，才能使得这6个零件在车间停留的总时间（平均停留时间）为最少； 解 设这6个零件的从前往后的加工时间分别为p1,p2,…,p6，这6个零件分别逗留时间为t1,t2,…,t6. 根据题意，则 p1 p2 p3 p4 p5 p6 t1 t2 t3 t4 t5 t7 加工时间 逗留时间 显然有 则6个零件的逗留时间总和为 所以该问题的数学模型为 模型求解方法 要使得6p1+5p2+…+p6尽可能小，需要将p1,…,p6做如下排序：p1p2p3p4p5p6。 所以，这6个零件的加工顺序为 3， 4， 5 ，6， 1， 2 1.8 2.0 0.5 0.9 1.3 1.5 总逗留时间为T=6*0.5+5*0.9+4*1.3+3*1.5+2*1.8+2=22.8（h） 工厂根据合同定做一些零件，这些零件要求先在车床上车削，然后再在磨床上加工，每台机器上各零件的加工时间如下表 零 件 1 2 3 4 5 车 床 磨 床 1.5 2.0 1.0 1.25 0.75 0.5 0.25 1.75 2.5 1.25 问：如何安排这五个零件的先后加工顺序，才能使得完成这5个零件的总时间最少？ 解 等待时间发生如下三种情况：（1）工件按顺序在某台机器上加工时发生等待；（2）工件按照加工要求等待另一台机器先加工发生等待。 如果发生第一类等待，加工时间短的工件先安排；如果发生第二类等待，加工时间短的后安排。因此，从车床加工时间看，加工时间短的工件往前排，而从磨床加工时间看，需要等待车床加工，所以加工时间短的工件往后排，加工时间长的工件尽量前排，充分利用等待时间。 这类加工排序的安排方法如下： （1）在加工时间表上选择最短加工时间tij，这是第i个工序加工第j零件所需时间，当i=1时,将零件j的加工顺序尽量靠前，若i=2,将零件j的加工顺序尽量朝后排； （2）在表上划去零件j所在行，回到步骤（1），直到剩下最后一列为止。 零 件 1 2 3 4 5 车 床 磨 床 1.5 2.0 1.0 1.25 0.75 0.5 0.25 1.75 2.5 1.25 （1）首先选最小加工时间0.25，此时i=2，所以工件2朝后排，即 2 划去工件2所在列，得 零 件 1 3 4 5 车 床 磨 床 1.5 1.0 1.25 0.75 0.5 1.75 2.5 1.25 （2）再选最小加工时间0.5，i=1，将工件1朝后排，即 5 1 2 去掉工件1所在列，即 零 件 3 4 5 车 床 磨 床 1.0 1.25 0.75 1.75 2.5 1.25 （3）再选最小加工时间0.75，i=1，将工件5朝前排，即 1