可拒絕排序和兩臺同類機(jī)半在線排序問題.pdf

1、排序論,也可被稱為時間表理論.它作為運(yùn)籌學(xué)的一個重要部分,是一門應(yīng)用性很強(qiáng)的科學(xué),它有著很深的現(xiàn)實背景和廣闊的應(yīng)用前景.本文主要研究了兩類可拒絕和一類半在線的排序問題.
　　 經(jīng)典的排序模型中,人們往往假定機(jī)器必須加工所有的工件且它們的加工時間都是給定的.然而在許多現(xiàn)實應(yīng)用中,如果某個工件加工時間或加工費(fèi)用很大,我們就會考慮是否要加工該工件.我們既可以選擇付出一定的費(fèi)用而拒絕加工該工件也可以選擇不付費(fèi)而加工它.目標(biāo)函數(shù)不再是傳統(tǒng)

2、的極小化最大完工時間,總完工時間,最大延遲等,而是同時考慮時間與費(fèi)用.我們稱這種排序為可拒絕排序.
　　 在大多經(jīng)典排序理論中,排序問題被劃分成離線和在線兩種.如果工件的所有信息被提前告知,我們稱它為離線的.相比之下,如果工件信息沒有被提前告知,而是逐個到達(dá),且要求該工件—旦到達(dá)便馬上排序,然后下一個工件的信息才被釋放,我們稱這種排序為在線排序.最近幾年,因為生產(chǎn)生活的需求,半在線(semi on-line)模型逐漸得到人們的重

3、視.半在線排序是指早已安排好的工件不準(zhǔn)再移動,但是在排序前早已經(jīng)知道后面工件的些許信息,例如已知工件的最大加工時間等等.
　　 論文共分為三章.
　　 第一章是本文的緒論部分,主要介紹排序問題的由來、研究現(xiàn)狀及一些必需的預(yù)備知識,并且介紹了本文的主要研究成果.
　　 第二章考慮的是兩種帶拒絕費(fèi)用的排序問題,目標(biāo)函數(shù)是在不超過總拒絕費(fèi)用閥值的前提下使總完工時間和最大完工時間最小.首先,我們證明了問題Pm|rej|∑