工件排序问题
摘要
本文对于实际生产中工件的优化排序问题进行了探讨。
问题一要求给n种零件在两台设备上加工进行最佳的排序，并且使得加工顺序相同。我们采用了较为成熟的约翰逊算法，得到对20个工件排序的结果：
总的加工延续时间为206s，工件加工顺序为：
17?19?18?8?15?6?7?3?5?1?16?12
?11?20?13?2?10?9?14?4
?D问题二针对三台机器的情况，我们使用了Palmer法以及C法两种启发式
算法，计算复杂度较小的情况下得到了近优解。然后，我们又采用优化模型，找到各工件在加工过程中加工时间和总时间之间的联系，求得各工件的加工总时间。最后建立目标函数，得到最优解： 当n?15时，总的加工时间为
184s，工件加工顺序为：
2?3?1?4?5?6?12?7?8?9?10?11?15?13?14 当n?20时，总的加工时间为197s，工件加工顺序为：
5?8?11?1?2?6?12?3?14?16?15
?17?4?18?19?10?20?13?9?7
关键词：工件排序 约翰逊法 Palmer法 C-D法
优化模型
1
一、 问题重述（略）
二、 问题分析
针对问题一，给n种加工顺序相同的零件在两台设备上加工进行排序。我们找到了一种解决相应问题的约翰逊算法，可以得到最优的排序方案以及总加工时间的最小值。
问题二中，我们针对实际生产中的工件排序问题，并且考虑到经济效益，即使不能给出最优解，得出算法小、效果较好的近优解也是不错的选择。于是我们采用了多种启发式算法，分析比较其优缺点。同时，考虑到此题完全可以转化为优化问题来解决，因此我们希望根据各工件在加工过程中加工时间和总时间之间的联系，寻求各工件加工总时间的具体算法。再利用Lingo软件进行求解模型，得出工件的最优排序。
三、符号说明
(i)Mn 第i台机器
工件数
第i个工件在第j台机器上的加工时间：
(j)itijXM i工件在M(j)上加工所需时间
(j)ji i工件从任务开始时刻起到完成M为止所需要的总时间
道工序
四、模型建立及求解
问题一
2
4．1 约翰逊（Johnson）算法
如何安排工件的加工顺序，使总的加工延续时间最短，解决这类优化排序问题的方法，是首先在全部额定工时中找出额定工时最小者。如果找到的最小额定工时是在A序（即前工序），那么该最小工时所对应的零件在安排加工顺序时，应尽量往前排；如果找到的最小工时是在B序（即后续工序），这时应将最小工时所对应的零件在安排加工顺序时，尽量往后排。除去已排的零件，对余下零件继续按上述方法，直至加工顺序全部排出为止。
[注]：在找最小工时时，若前序、后序工时相同，且是最小，这时所对应的零件
排前排后都可以，说明这时最优排序不是唯一的。
于是，零件加工优化排序算法归纳如下： 步骤1：在全部额定工时中找出tmin。
步骤2：若tmin在前工序，则该tmin对应的零件尽量往前排；若tmin在后续工序，
则对应的零件往后排。
步骤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启发式算法、C优化模型，并对各方的优缺点进行了比较。
4．2．1 算法一：Palmer启发式算法
?D算法以及建立
Palmer算法提出按斜度指标排列工件，工件的斜度指标可按下式计算：
m?i??j?1[j?(m?1)/2]tij3
,i?1,2,...n
按照各工件?i不增的顺序排列工件，可得出近优解。 对于问题二中3台机器的情况，则有：
3?i??j?1[k?(3?1)/2]tij??ti1?ti3,i?1,2,...,n
当n?15时，如附表
2取值，按?i不增的顺序排列工件，得到加工顺序为：
?13?2?7?3?12?1?10?9?15 此时总加工时间为197s。 当n?2011?6?4?8?14?5
时，如附表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 算法二：C?D算法
针对问题二，三台机器
A?B?C(A,B,C)的情况，不妨假设工件加工流程为
。算法步骤如下：
步骤1：对首末二工序（即A,C两工序）应用约翰逊法，并由此得到零件的加工
顺序及相应的加工延续时间T1；
步骤2：将各零件前两道工序的定额工时（即
2A,B两工序）对应相加：
?j?1tij(i?1,2,...,n)，得到一组假想的定额工时。同时，也将各零件最后
3两道工序的定额工时（即B,C两工序）相应地相加：?j?2tij(i?1,2,...,n)，
得到一组假想的额定工时。对这新组成的首末二假想工序应用约翰逊法，可得到零件的另一加工顺序及相应的加工总延续时间T2；
步骤3：最后取T值较小者对应的加工顺序，并以此为序计算总加工时间，即为
C?D算法所能排出的近优解。
当n
?15时，得到加工顺序为：
4
2?3?1?4?5?6?12?7?8?9?10?11?15?13?14
总的加工延续时间为184s。 当n?20时，得到加工顺序为：
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).当M(1)i?M(2)i?1时，此时i工件不需要等待（i?1）工件而立即就进入B工
?M(1)i序，因此i工件完成的总时间表达式为Mi(2) 2).当Mi(1)?M(2)i?1+Xi(2)；
时，此时i工件需要等待（i?1）工件完成钻床工序才能进
?M(2)i?1入B工序。因此i工件完成的总时间表达式为Mi(2)+Xi(2)。
综合以上两种情况，得到i工件完成B工序的总时间计算公式为：
M(2)i?Ma(xM,i(1)?1iM)?(2)iX(?i 1)2 于是，对于三台机器的问题，我们也可以得到类似的计算公式： 要求的完成加工任务的最省总时间即为在最优排序下各工件完成铣床加工工序的总时间之和。因此：
优化模型为：
n目标函数：Min?M(3)1+?{Max(Mi(2),Mi(?31))?i?2X(3)i}
其中，M1(3)?M(1)1?X1(2)?X1(3)
5