单机排序问题的研究

豆俊梅++孙彩贤

【摘要】本文首先介绍单机排序问题的背景和相关概念，而后着重介绍最小带权延误时间、最小化工件平均完工时间和延误工件数最少的单机排序问题，给出了相应的解法及证明方法.

【关键词】单机排序问题；带权延迟时间；延误工件数

单机排序问题是现代运筹学的重要组成部分，也是经济学所研究的重要课题之一，单机排序问题及其应用的重要性越来越多地被人们所认识.随着科学技术和生产的发展，单机排序使用的范围越来越广，许多新面临的问题需要排序问题来求解.随着单机排序问题应用在现实生活中的日益广泛，在社会生产和实践中发挥着越来越重要的作用.单机排序问题的研究理论和方法的发展源于实践也服务于实践.单机排序根据问题的要求，合理设定约束条件，通过数学上的分析、运算，得出各种最优排列方案，优化布置方案，以求达到最好的效果.

我们有问题背景：设一个机修车间有n个损坏待修的机械零件J1，J2，…，Jn要在一台机器上维修，它们各自的维修时间已知，设为p1，p2，…，pn.若零件Ji在损坏期间每单位时间产生的损失为wi，试问如何将J1，J2，…，Jn安排一个维修顺序，使得总的损失为最小？

该问题的求解方法很简单，我们只需将零件按p1w1，…，pnwn从小到大的次序排列，由此得到的顺序就是最优维修顺序.

下面我们加以证明，设Ji1，…，Jin是零件J1，J2，…，Jn的任意一个排列.若按照这一顺序维修，维修零件Jij完毕的时间为Cj=pi1+pi2+…+pin，则Jij产生的损失费为wijCj=wij∑jk=1pik，全部零件维修完成时总的损失为F=∑nj=1wijCj=∑nk=1pik∑nj=kwij.解决本问题即寻找一种排序使得∑nk=1wrkCk=min∑nj=1wijCj|i1，…，in为1～n的一种排列，假设在排列（Ji1，…，Jin）中有某一r，使得pirwir>pir+1wir+1，则新的排列为（Ji1，…，Jir+1，Jir，…，Jin），

此时有两个排列：

（Ji1，…，Jin），（1）

（Ji1，…，Jir+1，Jir，…，Jin）.（2）

对于排列如果按（2）顺序进行维修，总损失为

F′=∑r-1k=1pik∑nj=kwij+pir+1∑nk=rwik+pir（wir+wir+2+…+win）+∑nk=r+2pik∑nj=kwij.

因此，F-F′=pir（wir+…+win）-pir（wir+wir+2+…+win）+pir+1？？（wir+1+…+win）-pir+1（wir+…+win）=pirwir+1-pir+1wir>0，

故交换零件Jir和Jir+1后所得的新的排列（2）比原来的排列（1）损失费用少，可不断地进行这种交换，每次交换都是把较小的piwi换到左边，因此，满足条件p1w1≤p2w2≤…≤pnwn所得到的維修顺序就是最优排列.

【参考文献】

[1]唐国春，张峰，罗守成，等.现代排序论[M].上海：上海科学普及出版社，2003.

[2]罗守成，唐国春.平行机误工件数最少排序问题[A].运筹与决策（第二卷）[M].成都：成都科技大学出版社，1992.

[3]中国科学院数学研究所运筹室，编著.运筹学[M].北京：科学出版社，1973.

[4]常庆龙.以延误时间为指标的一台设备上的排序问题[J].数学的实践与认识，1978（2）：47-48.endprint