單機(jī)排序問題的研究

豆俊梅++孫彩賢

【摘要】本文首先介紹單機(jī)排序問題的背景和相關(guān)概念，而后著重介紹最小帶權(quán)延誤時(shí)間、最小化工件平均完工時(shí)間和延誤工件數(shù)最少的單機(jī)排序問題，給出了相應(yīng)的解法及證明方法.

【關(guān)鍵詞】單機(jī)排序問題；帶權(quán)延遲時(shí)間；延誤工件數(shù)

單機(jī)排序問題是現(xiàn)代運(yùn)籌學(xué)的重要組成部分，也是經(jīng)濟(jì)學(xué)所研究的重要課題之一，單機(jī)排序問題及其應(yīng)用的重要性越來越多地被人們所認(rèn)識(shí).隨著科學(xué)技術(shù)和生產(chǎn)的發(fā)展，單機(jī)排序使用的范圍越來越廣，許多新面臨的問題需要排序問題來求解.隨著單機(jī)排序問題應(yīng)用在現(xiàn)實(shí)生活中的日益廣泛，在社會(huì)生產(chǎn)和實(shí)踐中發(fā)揮著越來越重要的作用.單機(jī)排序問題的研究理論和方法的發(fā)展源于實(shí)踐也服務(wù)于實(shí)踐.單機(jī)排序根據(jù)問題的要求，合理設(shè)定約束條件，通過數(shù)學(xué)上的分析、運(yùn)算，得出各種最優(yōu)排列方案，優(yōu)化布置方案，以求達(dá)到最好的效果.

我們有問題背景：設(shè)一個(gè)機(jī)修車間有n個(gè)損壞待修的機(jī)械零件J1，J2，…，Jn要在一臺(tái)機(jī)器上維修，它們各自的維修時(shí)間已知，設(shè)為p1，p2，…，pn.若零件Ji在損壞期間每單位時(shí)間產(chǎn)生的損失為wi，試問如何將J1，J2，…，Jn安排一個(gè)維修順序，使得總的損失為最小？

該問題的求解方法很簡(jiǎn)單，我們只需將零件按p1w1，…，pnwn從小到大的次序排列，由此得到的順序就是最優(yōu)維修順序.

下面我們加以證明，設(shè)Ji1，…，Jin是零件J1，J2，…，Jn的任意一個(gè)排列.若按照這一順序維修，維修零件Jij完畢的時(shí)間為Cj=pi1+pi2+…+pin，則Jij產(chǎn)生的損失費(fèi)為wijCj=wij∑jk=1pik，全部零件維修完成時(shí)總的損失為F=∑nj=1wijCj=∑nk=1pik∑nj=kwij.解決本問題即尋找一種排序使得∑nk=1wrkCk=min∑nj=1wijCj|i1，…，in為1～n的一種排列，假設(shè)在排列（Ji1，…，Jin）中有某一r，使得pirwir>pir+1wir+1，則新的排列為（Ji1，…，Jir+1，Jir，…，Jin），

此時(shí)有兩個(gè)排列：

（Ji1，…，Jin），（1）

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

對(duì)于排列如果按（2）順序進(jìn)行維修，總損失為

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

因此，F(xiàn)-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）損失費(fèi)用少，可不斷地進(jìn)行這種交換，每次交換都是把較小的piwi換到左邊，因此，滿足條件p1w1≤p2w2≤…≤pnwn所得到的維修順序就是最優(yōu)排列.

【參考文獻(xiàn)】

[1]唐國(guó)春，張峰，羅守成，等.現(xiàn)代排序論[M].上海：上?？茖W(xué)普及出版社，2003.

[2]羅守成，唐國(guó)春.平行機(jī)誤工件數(shù)最少排序問題[A].運(yùn)籌與決策（第二卷）[M].成都：成都科技大學(xué)出版社，1992.

[3]中國(guó)科學(xué)院數(shù)學(xué)研究所運(yùn)籌室，編著.運(yùn)籌學(xué)[M].北京：科學(xué)出版社，1973.

[4]常慶龍.以延誤時(shí)間為指標(biāo)的一臺(tái)設(shè)備上的排序問題[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，1978（2）：47-48.endprint