11658.幾類資源約束下加工時間可變的排序問題

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

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

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

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