22993.若干帶運(yùn)輸排序問(wèn)題研究

1、浙江理工大學(xué)學(xué)位論文獨(dú)創(chuàng)性聲明本人聲明所呈交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。除了文中特別加以標(biāo)注和致謝的地方外，論文中不包含其他人已經(jīng)發(fā)表或撰寫過(guò)的研究成果，也不包含為獲得浙江理工大學(xué)或其他教育機(jī)構(gòu)的學(xué)位或證書(shū)而使用過(guò)的材料。與我一同工作的同志對(duì)本研究所做的任何貢獻(xiàn)均已在論文中作了明確的說(shuō)明并表示謝意：學(xué)位論文作者簽名：‘影軋簽字日期：)olS年J月)q日浙江理工大學(xué)碩士學(xué)位論文若干帶運(yùn)輸排序問(wèn)題研究摘要排序

2、問(wèn)題是一類經(jīng)典的組合優(yōu)化問(wèn)題，并從上世紀(jì)50年代開(kāi)始，伴隨著生產(chǎn)制造領(lǐng)域的規(guī)?；c自動(dòng)化而不斷發(fā)展和成熟。本文主要研究一類帶運(yùn)輸?shù)呐判騿?wèn)題，該類問(wèn)題在供應(yīng)鏈管理中具有廣泛的應(yīng)用前景，研究的核心是問(wèn)題的近似算法設(shè)計(jì)與分析。全文共分四章。第一章主要簡(jiǎn)要介紹了供應(yīng)鏈與排序問(wèn)題的一些相關(guān)知識(shí)和概念，并且綜述了帶運(yùn)輸排序問(wèn)題的國(guó)內(nèi)外研究現(xiàn)狀。第二章研究流水作業(yè)環(huán)境下機(jī)器間帶運(yùn)輸?shù)呐判騿?wèn)題。在這類問(wèn)題中，運(yùn)輸?shù)倪^(guò)程存在于兩臺(tái)機(jī)器之間，工件需要在第一

3、臺(tái)機(jī)器上加工完后通過(guò)一輛運(yùn)輸工具分批運(yùn)輸?shù)降诙_(tái)機(jī)器繼續(xù)進(jìn)行加工，每個(gè)工件具有不同的尺寸，運(yùn)輸工具具有容量限制，目標(biāo)是極小化最后一個(gè)工件完工的時(shí)間。針對(duì)該問(wèn)題，本文設(shè)計(jì)了最壞情況界為譬的近似算法。第三章討論多個(gè)客戶環(huán)境下的帶運(yùn)輸排序問(wèn)題。該問(wèn)題中，工件在機(jī)器上完成加工后，需要由唯一的一輛運(yùn)輸工具運(yùn)送到相應(yīng)的顧客處。不同客戶的工件不能在同一批中運(yùn)輸，從機(jī)器到不同客戶的運(yùn)輸時(shí)間也不同，并且運(yùn)輸工具的空間是有限的，每個(gè)工件占用運(yùn)輸工具的空間各

4、不相同。目標(biāo)是極小化最后一個(gè)工件到達(dá)顧客并返回機(jī)器的時(shí)間。本文給出了該問(wèn)題顧客數(shù)為2時(shí)的一個(gè)最壞情況界為；的近似算法。第四章研究同型機(jī)和同類機(jī)環(huán)境下工件具有不同尺寸的帶運(yùn)輸排序問(wèn)題。在該問(wèn)題中，工件完工后，同樣由唯一的一輛運(yùn)輸工具運(yùn)送到顧客處并且考慮工件的尺寸可以不相同且運(yùn)輸工具具有容量限制的情況。根據(jù)機(jī)器環(huán)境的不同，研究了如下兩種情形：1)機(jī)器環(huán)境為同型機(jī)，考慮機(jī)器數(shù)分別為3臺(tái)和任意m臺(tái)的情況；2)機(jī)器環(huán)境為同類機(jī)，考慮機(jī)器數(shù)目分別為