单机排序问题的研究.docx

《单机排序问题的研究.docx》由会员分享，可在线阅读，更多相关《单机排序问题的研究.docx（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、单机排序问题的研究 【摘要】本文首先介绍单机排序问题的背景和相关概念，而后着重介绍最小带权延误时间、最小化工件平均完工时间和延误工件数最少的单机排序问题，给出了相应的解法及证明方法. 【关键词】单机排序问题；带权延迟时间；延误工件数 单机排序问题是现代运筹学的重要组成部分，也是经济学所探讨的重要课题之一，单机排序问题及其应用的重要性越来越多地被人们所相识.随着科学技术和生产的发展，单机排序运用的范围越来越广，很多新面临的问题须要排序问题来求解.随着单机排序问题应用在现实生活中的日益广泛，在社会生产和实践中发挥着越来越重要的作用.单机排序问题的探讨理论和方法的发展源于实践也服务于实践.单机排序依

2、据问题的要求，合理设定约束条件，通过数学上的分析、运算，得出各种最优排列方案，优化布置方案，以求达到最好的效果. 我们有问题背景：设一个机修车间有n个损坏待修的机械零件J1，J2，Jn要在一台机器上修理，它们各自的修理时间已知，设为p1，p2，pn.若零件Ji在损坏期间每单位时间产生的损失为wi，试问如何将J1，J2，Jn支配一个修理依次，使得总的损失为最小？ 该问题的求解方法很简洁，我们只需将零件按p1w1，pnwn从小到大的次序排列，由此得到的依次就是最优修理依次. 下面我们加以证明，设Ji1，Jin是零件J1，J2，Jn的随意一个排列.若根据这一依次修理，修理零件Jij完毕的时间为Cj=

3、pi1+pi2+pin，则Jij产生的损失费为wijCj=wijjk=1pik，全部零件修理完成时总的损失为F=nj=1wijCj=nk=1piknj=kwij.解决本问题即找寻一种排序使得nk=1wrkCk=minnj=1wijCj|i1，in为1n的一种排列，假设在排列中有某一r，使得pirwirpir+1wir+1，则新的排列为， 此时有两个排列： ， . 对于排列假如按依次进行修理，总损失为 F=r-1k=1piknj=kwij+pir+1nk=rwik+pir+nk=r+2piknj=kwij. 因此，F-F=pir-pir+pir+1？-pir+1=pirwir+1-pir+1wi

4、r0， 故交换零件Jir和Jir+1后所得的新的排列比原来的排列损失费用少，可不断地进行这种交换，每次交换都是把较小的piwi换到左边，因此，满意条件p1w1p2w2pnwn所得到的維修依次就是最优排列. 【参考文献】 1唐国春，张峰，罗守成，等.现代排序论M.上海：上海科学普及出版社，2003. 2罗守成，唐国春.平行机误工件数最少排序问题A.运筹与决策M.成都：成都科技高校出版社，11012. 3中国科学院数学探讨所运筹室，编著.运筹学M.北京：科学出版社，11013. 4常庆龙.以延误时间为指标的一台设备上的排序问题J.数学的实践与相识，11018：47-48. 第3页 共3页第 3 页 共 3 页第 3 页 共 3 页第 3 页 共 3 页第 3 页 共 3 页第 3 页 共 3 页第 3 页 共 3 页第 3 页 共 3 页第 3 页 共 3 页第 3 页 共 3 页第 3 页 共 3 页