可拒絕排序和兩臺(tái)同類機(jī)半在線排序問(wèn)題.pdf

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

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

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