22993.若干帶運輸排序問題研究

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

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

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

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