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

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

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

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

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

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