1、 編 號(hào)： 碩士學(xué)位論文 碩士學(xué)位論文 題 目：帶到達(dá)時(shí)間和不可用區(qū)間以及拒絕工件的排序問(wèn)題 培 養(yǎng) 單 位： 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院 專 業(yè) 名 稱： 應(yīng)用數(shù)學(xué) 指 導(dǎo) 教 師： 羅成新 教授 研 究 生： 劉澈 完 成 時(shí) 間： 2013 年 5 月 18 日 沈陽(yáng)師范大學(xué)研究生處制 類 別 全日制研究生 √ 教育碩士 同等學(xué)力 帶到達(dá)時(shí)間和不可用區(qū)間以及拒絕工件的排序問(wèn)題 摘要 排序問(wèn)題

2、是一類重要的組合最優(yōu)化問(wèn)題。在經(jīng)典排序里，研究者通常假定工件加工商必須接受加工買家要求的全部工件，也就是說(shuō)，不能拒絕加工任意一個(gè)工件。但是，這并不符合生產(chǎn)者的利益要求，工件加工商為了使利益最大化，或者更為通俗地說(shuō)，為了創(chuàng)造更大的生產(chǎn)效益，就不會(huì)去加工那些加工時(shí)間很長(zhǎng)，但是獲取利益卻很小的工件，同時(shí)也會(huì)因此而賠款。此種情況放在排序問(wèn)題里，稱為帶有拒絕工件。在加工生產(chǎn)時(shí)，機(jī)器可能因?yàn)榘l(fā)生故障或者其他意外，使得機(jī)器在一段時(shí)間里不能進(jìn)行工作。此

3、種情況放在排序問(wèn)題里，稱為機(jī)器帶有不可用區(qū)間。由于這些問(wèn)題很可能在現(xiàn)實(shí)生產(chǎn)中發(fā)生，所以，越來(lái)越多的學(xué)者對(duì)既有不可用區(qū)間又有拒絕工件的排序問(wèn)題進(jìn)行了大量的研究。 本文對(duì)帶到達(dá)時(shí)間和不可用區(qū)間以及拒絕工件的排序問(wèn)題進(jìn)行了研究，主要內(nèi)容如下： 第一章介紹排序問(wèn)題的定義及三參數(shù)表示法， 并介紹帶有不可用區(qū)間和拒絕工件的排序問(wèn)題的一些研究現(xiàn)狀以及本文工作。 第二章我們采用構(gòu)造輸入數(shù)據(jù)的方法處理帶到達(dá)時(shí)間和不可用區(qū)間以及拒絕工件的單機(jī)排序問(wèn)題，我們

4、的目標(biāo)是最小化加工工件的時(shí)間表長(zhǎng)和拒絕工件的懲罰的和，設(shè)計(jì)了一個(gè)全多項(xiàng)式時(shí)間近似方案。 第三章我們通過(guò)改變動(dòng)態(tài)規(guī)劃算法的執(zhí)行過(guò)程來(lái)處理帶到達(dá)時(shí)間和不可用區(qū)間以及拒絕工件的單機(jī)排序問(wèn)題， 最小化的函數(shù)是所有放在機(jī)器上加工的工件的時(shí)間表長(zhǎng)與所有被拒絕的工件的懲罰的和，給出了一個(gè)全多項(xiàng)式時(shí)間近似方案。 第四章研究的是帶到達(dá)時(shí)間和不可用區(qū)間以及拒絕工件的兩臺(tái)平行機(jī)排序問(wèn)題。關(guān)鍵詞：到達(dá)時(shí)間，拒絕工件，不可用區(qū)間，時(shí)間表長(zhǎng)，全多項(xiàng)式時(shí)間近似方案