28862.一類帶有交貨期窗口和工件可拒絕的單機排序問題

1、編號：碩士學(xué)位論文碩士學(xué)位論文題目：一類帶有交貨期窗口和工件可拒絕的單機排序問題培養(yǎng)單位：數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院專業(yè)名稱：運籌學(xué)與控制論指導(dǎo)教師：趙傳立教授研究生：陳東完成時間：2014年5月22日沈陽師范大學(xué)研究生處制類別全日制研究生√教育碩士同等學(xué)力一類帶有交貨期窗口和工件可拒絕的單機排序問題摘要排序問題是一類研究比較活躍的組合最優(yōu)化問題。本文討論了一類帶有交貨期窗口和工件可拒絕的單機排序問題，主要研究內(nèi)容如下：第一章介紹了一些關(guān)于排序

2、問題的背景知識和本文所討論的工作。第二章討論了帶有交貨期窗口和工件可拒絕的單機排序問題，該問題是將所有的工件分成兩個工件集，一個是被接受的工件集，另一個是被拒絕的工件集。對于被接受的工件集：每個工件都有一個固定的交貨期窗口，且交貨期窗口大小相同。如果某個工件的完成時間在交貨期窗口的準(zhǔn)許范圍之內(nèi)，則對于該工件來說，不產(chǎn)生任何其它懲罰費用；否則會產(chǎn)生提前或延誤的費用。而對于拒絕工件而言，它的費用只與工件自身有關(guān)。問題的目標(biāo)是確定被接受工件的

3、最優(yōu)排序，極小化這兩個工件集產(chǎn)生的總費用。首先，在本章提出了一些重要的性質(zhì)及相關(guān)的主要結(jié)論，并進(jìn)行了一些最優(yōu)解的討論；其次證明了該問題是多項式時間可解的，同時針對該問題給出了一個動態(tài)規(guī)劃算法，并給出數(shù)值例子加以驗證。最后本文又將問題擴(kuò)展到加工時間與位置相關(guān)的排序問題。通過將問題轉(zhuǎn)化為一系列的指派問題，證明了該問題是多項式時間可解的。第三章是把第二章問題推廣到帶有維修活動的情況。考慮了帶有交貨期窗口、機器可維修和工件可拒絕的單機排序問題。

4、其中維修活動分兩種情況：維修活動從0t?時刻開始；維修活動的開始時間等于某個工件的完工時間。維修活動持續(xù)時間是一個固定值，排在維修活動之后的工件的加工時間將會減少。問題的目標(biāo)是確定維修活動的位置和被接受工件的最優(yōu)排序，極小化接受工件集和拒絕工件集產(chǎn)生的總費用。通過將該問題的兩種情況都轉(zhuǎn)化為指派問題，證明了該問題是多項式時間可解的，并給出數(shù)值例子加以驗證。最后，總結(jié)了全文并提出了今后工作的研究方向。關(guān)鍵詞：單機，排序，交貨期窗口，拒絕，維