具有不可用區(qū)間的平行機(jī)排序問(wèn)題的近似算法

1、編 號(hào)： 碩士學(xué)位論文 碩士學(xué)位論文 題 目: 具有不可用區(qū)間的平行機(jī)排序問(wèn)題的近似算法 培 養(yǎng) 單 位：數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院 專 業(yè) 名 稱：應(yīng)用數(shù)學(xué) 指 導(dǎo) 教 師：羅成新 教授 研 究 生：?jiǎn)题?完 成 時(shí) 間：2012 年 5 月 24 日 沈陽(yáng)師范大學(xué)研究生處制 類 別 全日制研究生 √ 教育碩士 同等學(xué)力 具有不可用區(qū)間的平行機(jī)排序問(wèn)題的近似算法 摘 要 近幾年來(lái)， 排序問(wèn)題由

2、于其深刻的實(shí)際背景和廣泛的應(yīng)用前景而受到了極大關(guān)注。在經(jīng)典的排序模型中，機(jī)器是一直可用的。然而，在實(shí)際生活中機(jī)器也需要維修，工人也需要休息，這就導(dǎo)致了機(jī)器在使用過(guò)程中不可能是一直可用的。所以很多人研究了機(jī)器帶有不可用約束的排序問(wèn)題。 同時(shí)我們也考慮了工件帶有運(yùn)輸時(shí)間的問(wèn)題， 這是因?yàn)樵诰哂泻芏喙ぜ?shù)的大型排序問(wèn)題中， 往往在工件加工完之后還需要在一定的時(shí)間內(nèi)將其運(yùn)送到指定的生產(chǎn)地方。 這就使得我們不僅要單純考慮工件的完工時(shí)間也要把運(yùn)輸時(shí)

3、間計(jì)劃在內(nèi)，使其更符合實(shí)際意義。 本文主要討論在機(jī)器具有不可用約束的情形下的平行機(jī)排序問(wèn)題。 文章主要分為四個(gè)部分，第一章中介紹了排序問(wèn)題的背景，描述及表示方法，并對(duì)機(jī)器的不可用區(qū)間和工件的運(yùn)輸時(shí)間做了陳述。 第二章中主要討論了機(jī)器具有不可用區(qū)間的平行機(jī)排序問(wèn)題。 其中第一臺(tái)機(jī)器上有一段不可用區(qū)間， 第二臺(tái)機(jī)器是可以連續(xù)使用的，工件在加工過(guò)程中是不允許中斷的，目標(biāo)函數(shù)是極小化時(shí)間表長(zhǎng)。首先介紹了與之相關(guān)問(wèn)題的發(fā)展情況， 然后通過(guò)圖例解釋