n个零件在m台机床上的加工顺序问题(Ⅰ)

在工厂的零件加工车间,设有n个零件要在m台机床上加工,各零件根据工艺上的要求,按一定顺序通过这些机床,如何安排这些零件顺序使预先给定的指标达到最优,这就是运筹学中所谓的排序问题。本文所考虑的排序问题:假设1)各零件皆依同一顺序通过这些机床;2)每个零件的加工时间为已知;3)每个机床在同一时间。只能加工一个零件。目的是要寻求一个顺序,使总的加工时间为最短。我们所得到的主要结果如下:1.设ω为(1…n)的某一排列,ω’为从ω经交换相邻两数字i和′的位置后的排列,T(ω)和T(ω′)分别表示在ω和ω’之下总加工时间,则当时,有T(ω)≤T(ω′)。2.我们所给出的条件比Nabeshima所给出的条件要弱。3.从推广Johnson法则这一角度看,本文定理4的结果已是最好的结果。