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

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

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

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