20132.工件的加工和配送協(xié)作排序問題

1、分類號:O22學(xué)校單位代號:10446曲阜師范大學(xué)博士學(xué)位論文論文題目:工件的加工和配送協(xié)作排序問題SomeCoordinatedSchedulingProblemswithDelivery研究生姓名:學(xué)科、專業(yè):研究方向:導(dǎo)師姓名、職稱:谷存昌數(shù)學(xué)、應(yīng)用數(shù)學(xué)組合最優(yōu)化張玉忠教授論文完成時間:2015年3月______________________________曲阜師范大學(xué)博士學(xué)位論文________________________

2、______工件的加工和配送協(xié)作排序問題中文摘要排序論是組合最優(yōu)化領(lǐng)域的一個重要研宄方向.它有著廣泛的應(yīng)用背景和深刻的理論意義，常常應(yīng)用于軍事、經(jīng)濟、運輸、管理和計算機科學(xué)等諸多領(lǐng)域.工件的加工和配送協(xié)作排序問題起源于大型工業(yè)車床加工領(lǐng)域，在物流和供應(yīng)鏈管理領(lǐng)域都有著重要的實際背景，研宄成果也非常豐富.分批排序、工件加工時間具有學(xué)習(xí)效應(yīng)、工件屬于一些不相容的組（family)及工件的配送過程外包的排序問題都是比較新型的模型，也吸引了眾多

3、國內(nèi)外學(xué)者的關(guān)注.本文對這幾類排序問題進行了討論，做了如下工作.1.第一章介紹排序問題的一些基本概念、符號和相關(guān)知識.2.第二章討論了工件的運輸和繼列分批加工協(xié)作排序問題.目標分別是極小化工件的總完工時間與批的費用之和及極小化工件的最大完工時間與批的加工費用之和.在工件的加工時間都相等的情況下，如果車輛運輸工件的次序確定，分別給出了多項式時間的動態(tài)規(guī)劃算法；如果車輛運輸工件的次序不確定，證明了該問題是困難的，分別給出了車輛返回時間t=0

4、時最差性能比等于2m的近似算法.3.第三章討論了帶有多個工件組的平行批處理機排序問題，其中，共有F個不相容的組，且每一組中的工件都具有相同的加工時間和相同的權(quán).目標為極小化帶權(quán)誤工工件數(shù).當組的個數(shù)F為固定常數(shù)時，給出了運行時間為O(bF12Fn2FW)的偽多項式時間算法，得到了運行時間為O(6F12Fn2F2e)的完全多項式時間近似方案（FPTAS)其中，參數(shù)b為批的容量.如果每一組中工件的交貨期也相同，給出了運行時間為O(n(log

5、nWminPdmax))的偽多項式時間算法，其中，參數(shù)PW分別表示工件的總完工時間和總權(quán)，dmax為工件的最大交貨期.4.第四章討論了工件具有學(xué)習(xí)效應(yīng)的加工和配送協(xié)作排序問題.機器隨著加工工件的增多，相應(yīng)地具有一定的學(xué)習(xí)功能，機器上第r個位置上工件j的實際加工時間滿足=p(1EITi1ln糊廣，其中，剛為排序中第I個位置上工件的正常加工時間，a0為學(xué)習(xí)因子.對目標分別為極小化工件的總配送時間與批的費用之和及極小化工件的最大延遲時間與批的