数模工件排序问题

1工件排序问题摘要本文对于实际生产中工件的优化排序问题进行了探讨。问题一要求给n种零件在两台设备上加工进行最佳的排序，并且使得加工顺序相同。我们采用了较为成熟的约翰逊算法，得到对20个工件排序的结果：总的加工延续时间为206s，工件加工顺序为：1719188156735116121120132109144问题二针对三台机器的情况，我们使用了Palmer法以及CD法两种启发式算法，计算复杂度较小的情况下得到了近优解。然后，我们又采用优化模型，找到各工件在加工过程中加工时间和总时间之间的联系，求得各工件的加工总时间。最后建立目标函数，得到最优解：当15n时，总的加工时间为184s，工件加工顺序为：231456127891011151314当20n时，总的加工时间为197s，工件加工顺序为：5811126123141615174181910201397关键词：工件排序约翰逊法Palmer法C-D法优化模型2一、问题重述（略）二、问题分析针对问题一，给n种加工顺序相同的零件在两台设备上加工进行排序。我们找到了一种解决相应问题的约翰逊算法，可以得到最优的排序方案以及总加工时间的最小值。问题二中，我们针对实际生产中的工件排序问题，并且考虑到经济效益，即使不能给出最优解，得出算法小、效果较好的近优解也是不错的选择。于是我们采用了多种启发式算法，分析比较其优缺点。同时，考虑到此题完全可以转化为优化问题来解决，因此我们希望根据各工件在加工过程中加工时间和总时间之间的联系，寻求各工件加工总时间的具体算法。再利用Lingo软件进行求解模型，得出工件的最优排序。三、符号说明()iM第i台机器n工件数ijt第i个工件在第j台机器上的加工时间：()jiXi工件在()jM上加工所需时间jiMi工件从任务开始时刻起到完成()jM道工序为止所需要的总时间四、模型建立及求解问题一34．1约翰逊（Johnson）算法如何安排工件的加工顺序，使总的加工延续时间最短，解决这类优化排序问题的方法，是首先在全部额定工时中找出额定工时最小者。如果找到的最小额定工时是在A序（即前工序），那么该最小工时所对应的零件在安排加工顺序时，应尽量往前排；如果找到的最小工时是在B序（即后续工序），这时应将最小工时所对应的零件在安排加工顺序时，尽量往后排。除去已排的零件，对余下零件继续按上述方法，直至加工顺序全部排出为止。[注]：在找最小工时时，若前序、后序工时相同，且是最小，这时所对应的零件排前排后都可以，说明这时最优排序不是唯一的。于是，零件加工优化排序算法归纳如下：步骤1：在全部额定工时中找出mint。步骤2：若mint在前工序，则该mint对应的零件尽量往前排；若mint在后续工序，则对应的零件往后排。步骤3：除去已排的零件，对余下零件继续按步骤（1）（2）处理，直至全部排完为止。由此可得该批零件的最优加工排序为：1719188156735116121120132109144总的加工延续时间T206s。问题二针对此问，我们采用了三种方法：Palmer启发式算法、CD算法以及建立优化模型，并对各方的优缺点进行了比较。4．2．1算法一：Palmer启发式算法Palmer算法提出按斜度指标排列工件，工件的斜度指标可按下式计算：1[(1)/2],1,2,...mijijjmint4按照各工件i不增的顺序排列工件，可得出近优解。对于问题二中3台机器的情况，则有：3131[(31)/2],1,2,...,iiijijkttint当15n时，如附表2取值，按i不增的顺序排列工件，得到加工顺序为：132731211091511648145此时总加工时间为197s。当20n时，如附表3取值，按i不增的顺序排列工件，得到加工顺序为：1712111554138196141627181013920此时总加工时间为231s。4．2．2算法二：CD算法针对问题二，三台机器(,,)ABC的情况，不妨假设工件加工流程为ABC。算法步骤如下：步骤1：对首末二工序（即,AC两工序）应用约翰逊法，并由此得到零件的加工顺序及相应的加工延续时间1T；步骤2：将各零件前两道工序的定额工时（即,AB两工序）对应相加：21(1,2,...,)ijjtin，得到一组假想的定额工时。同时，也将各零件最后两道工序的定额工时（即,BC两工序）相应地相加：32(1,2,...,)ijjtin，得到一组假想的额定工时。对这新组成的首末二假想工序应用约翰逊法，可得到零件的另一加工顺序及相应的加工总延续时间2T；步骤3：最后取T值较小者对应的加工顺序，并以此为序计算总加工时间，即为CD算法所能排出的近优解。当15n时，得到加工顺序为：5231456127891011151314总的加工延续时间为184s。当20n时，得到加工顺序为：5811126123141615174181910201397总的加工延续时间为197s。4．2．3算法三：建立优化模型求解针对两台机器的问题，这n个工件都要求先在机器A上加工，然后再在机器B上加工，每种机器一次只能加工一种工件，求工件加工的最优排序，使得完成这批工件加工任务所需的总时间最省。根据总时间的定义，某工件从任务开始时刻起到完成钻床工序止所需要的总时间包括该工件完成A工序的时间，等待上一个工件加工完的时间，以及该工件在机器B上加工的时间。这里要分两种情况进行分析：1).当(1)iM(2)1iM时，此时i工件不需要等待（1i）工件而立即就进入B工序，因此i工件完成的总时间表达式为(2)iM(1)iM+(2)iX；2).当(1)iM(2)1iM时，此时i工件需要等待（1i）工件完成钻床工序才能进入B工序。因此i工件完成的总时间表达式为(2)iM(2)1iM+(2)iX。综合以上两种情况，得到i工件完成B工序的总时间计算公式为：(2)(1)(2)21(,)(1)iiiiMMaxMMXi于是，对于三台机器的问题，我们也可以得到类似的计算公式：要求的完成加工任务的最省总时间即为在最优排序下各工件完成铣床加工工序的总时间之和。因此：优化模型为：目标函数：(3)1MinM+(2)(3)(3)12{(,)}niiiiMaxMMX其中，(3)(1)(2)(3)1111MMXX6我们在寻求各工件加工总时间的具体算法基础上，围绕化整为零的数学思想，将整批工件的加工任务拆分为在最优的排序下每个工件的实际加工情况来分析。最后采用Lingo软件进行求解模型，计算得出：当15n时，工件加工顺序为：231456127891011151314总的加工延续时间为184s。当20n时，工件加工顺序为：5811126123141615174181910201397总的加工延续时间为197s。4．2．4算法比较由于建立优化模型求解得到的为最优解：184(15),197(20)TnTn对比前两种算法算法我们可知：Palmer启发式算法得到的是近优解，而CD算法获得了最优解。Palmer启发式算法虽然得到的是近优解，然而其以斜度指标排列工件的算法计算量很小，获得的结果比较好。因而在解决生产实际中的排序问题十分实用。此题中，虽然CD算法获得了最优解，但是以此算法要获得最优的加工顺序，必须满足：132{,}{},(,,1,2,...,)ijkMinttMaxtijkn的前提条件，而本题所给的数据显然是不符的，获得了最优解只是碰巧而已。即在数据不满足CD算法的上述前提下得到的解不能保证为最优解。建立优化模型求解，逻辑严谨，论证充分，算法简洁准确，有效地提高了软件求解效率。对于此题是一个很好的计算方法。五、模型评价及改进由于在模型求解中利用了Lingo软件，大大简化了编程工作，且模型本身结合软件的使用就具有很强的可移植性，便于模型的推广。例如在推广到m工件n部机床的情况，只需在程序中的工件，顺序集里加入相应的属性；在程序段中加7入对应的算法和约束条件就可以完全替换从而解决问题了。六、参考文献（略）