【摘要】：隨著社會的進步和科學技術的發(fā)展,排序問題在我們的生活和工作中得到了廣泛的應用.在經(jīng)典的排序文獻中,人們研究的往往是生產(chǎn)商獨自完成某個或某些客戶的訂單,而不會將部分訂單進行外包.在實際應用中,生產(chǎn)商常常把那些自己加工耗時且?guī)淼睦麧櫛容^少的訂單進行外包.在某種程度上,這會使生產(chǎn)商在一定的時間范圍內贏得更大的利潤.這就產(chǎn)生了可拒絕排序.本文從算法的角度對可拒絕排序進行研究.首先,我們考慮了機器有不能工作時間區(qū)間的可拒絕排序,然后又研究了極小化持貨成本的兩臺平行機排序問題,最后又討論了機器具有學習效應的單機排序問題.目標函數(shù)主要有極小化接收工件的總完工時間與拒絕工件的總拒絕費用之和,極小化總持貨成本與總運輸費用之和.本文主要考慮了以下問題.第一章,我們給出了有關排序問題的基本概念,基本知識和術語.簡要說明了一下排序問題的研究現(xiàn)狀以及本文的主要結果.第二章,研究了一種帶有學習效應,并且機器有不能工作時間區(qū)間的可拒絕排序問題.機器在一些給定的時間區(qū)間內不能加工工件.工件要么被拒絕加工,但要支付一定的拒絕費用要么被接收且安排在機器上加工.討論的目標為極小化接收工件的總完工時間與拒絕工件的總拒絕費用之和.此外,還研究了一種帶有學習和惡化效應的可拒絕排序問題.討論的目標為極小化接收工件的加權總完工時間與拒絕工件的總拒絕費用之和.針對以上問題分別給出了偽多項式時間動態(tài)規(guī)劃算法,并分析了算法的復雜性.第三章,考慮了工件具有相同加工時間的兩臺平行機排序問題.工件要么被接收,要么被外包,但要支付一定的外包費用.對于有限的外包預算問題,討論的目標為極小化總持貨成本與總運輸費用的和,給出了偽多項式時間算法和完全多項式時間近似方案.第四章,考慮了機器具有學習效應的單機排序問題.工件要么被接收,要么被外包,但要支付一定的外包費用.在有限的外包預算情況下,討論的目標為極小化總持貨成本與總運輸費用的和,給出了偽多項式時間算法.
【學位授予單位】：曲阜師范大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：O223

【參考文獻】

相關期刊論文 前1條

1 崔苗苗;趙玉芳;王松麗;;機器具有可用性限制的加權總完工時間問題[J];沈陽師范大學學報(自然科學版);2012年02期

，

本文編號：2576072