豆俊梅++孫彩賢
【摘要】本文首先介紹單機(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è)維修順序,使得總的損失為最?。?/p>
該問題的求解方法很簡(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