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

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

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

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

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