11658.幾類資源約束下加工時(shí)間可變的排序問(wèn)題

1、碩士學(xué)位論文論文作者：學(xué)科專業(yè)：指導(dǎo)教師：培養(yǎng)單位：培養(yǎng)類別：完成時(shí)間：沈陽(yáng)師范大學(xué)學(xué)位評(píng)定委員會(huì)單位代碼：?jiǎn)挝淮a：10166幾類資源約束下加工時(shí)間可變的排序問(wèn)題王洪芳數(shù)學(xué)、應(yīng)用數(shù)學(xué)羅成新數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院全日制2016年05月25日作者簽名：日期：幾類資源約束下加工時(shí)間可變的排序問(wèn)題摘要排序問(wèn)題是運(yùn)籌學(xué)和組合最優(yōu)化領(lǐng)域的一個(gè)重要分支現(xiàn)已廣泛應(yīng)用于機(jī)器制造、生產(chǎn)管理、運(yùn)輸調(diào)度等方面。經(jīng)典排序中工件的加工時(shí)間是固定的常數(shù)，但在實(shí)際生產(chǎn)中

2、，任務(wù)的加工時(shí)間往往與其開(kāi)始加工時(shí)間，加工所在位置或資源的分配量等因素有關(guān)。第一章，主要介紹了排序問(wèn)題的研究背景、發(fā)展現(xiàn)狀以及本文所做的工作。第二章，我們同時(shí)考慮了學(xué)習(xí)和退化效應(yīng)雙重因素以及資源分配量對(duì)任務(wù)加工時(shí)間的影響，并結(jié)合兩種工期指派方法（工期窗口指派方法和不同工期指派方法）進(jìn)行分類研究。對(duì)于工期窗口指派問(wèn)題，目標(biāo)是確定最優(yōu)的工期窗口開(kāi)始時(shí)間，工期窗口寬度、最優(yōu)的資源分配量以及最優(yōu)的任務(wù)排序最小化目標(biāo)函數(shù)。對(duì)于不同工期指派方法，目

3、標(biāo)是確定任務(wù)的最優(yōu)排序，每個(gè)工件的最優(yōu)工期，以及分配到每個(gè)任務(wù)的資源量最小化目標(biāo)函數(shù)。證明了這兩個(gè)問(wèn)題均是多項(xiàng)式時(shí)間??4nO內(nèi)可解，并給出了最優(yōu)算法。第三章，本文將目標(biāo)函數(shù)為最小化加工時(shí)間和拒絕費(fèi)用之和的單機(jī)可拒絕排序問(wèn)題進(jìn)一步拓展到平行機(jī)環(huán)境下，加工時(shí)間變?yōu)殛P(guān)于開(kāi)始加工時(shí)間的線性退化函數(shù)，目標(biāo)函數(shù)修改為工期，誤工工件懲罰，總完工時(shí)間以及拒絕工件的懲罰費(fèi)用之和。首先運(yùn)用動(dòng)態(tài)規(guī)劃方法證明偽多項(xiàng)式時(shí)間內(nèi)可求得問(wèn)題的最優(yōu)解，并運(yùn)用簡(jiǎn)化狀態(tài)空

4、間的方法給出一個(gè)全多項(xiàng)式近似策略。時(shí)間復(fù)雜度為????????225DnO?????baD??1lnlnmaxmax的全多項(xiàng)式近似策略（FPTAS）。第四章，研究帶有加工和運(yùn)輸兩個(gè)階段供應(yīng)鏈的系列批排序問(wèn)題，其中任務(wù)的加工時(shí)間是關(guān)于雙資源消耗的凸函數(shù)。在系列批中工件要求連續(xù)加工且每批工件的完工時(shí)間等于此批中最后一個(gè)被加工工件的完工時(shí)間，加工完成之后，每批工件通過(guò)容量有限的單車輛運(yùn)輸?shù)娇蛻?，而且每輛車一次只能運(yùn)輸一批工件。我們給出了復(fù)雜度