1、一：If餑1成組加工排序和供應(yīng)鏈在線排序問(wèn)題研究生姓名：學(xué)科、專(zhuān)業(yè)：研究方向。指導(dǎo)教師：完成時(shí)間：王迅娣數(shù)學(xué)、運(yùn)籌學(xué)與控制論管理運(yùn)籌學(xué)張玉忠教授2010年4月享量豪機(jī)弋眵飛哺睫博隧憾懣邋疆l基勇妻叁‘副●曲阜師范大學(xué)碩士學(xué)位論文成組加工排序和供應(yīng)鏈在線排序問(wèn)題摘要排序問(wèn)題作為一類(lèi)重要的組合優(yōu)化問(wèn)題，有深刻的實(shí)際背景和廣闊的應(yīng)用前景它廣泛應(yīng)用于管理科學(xué)、計(jì)算機(jī)系統(tǒng)、工農(nóng)業(yè)生產(chǎn)、工程技術(shù)以及交通運(yùn)輸?shù)戎T多領(lǐng)域，成為目前運(yùn)籌學(xué)研究的一個(gè)十分活

2、躍的分支，因而一直受到國(guó)內(nèi)外學(xué)術(shù)界的重視而成組加工以及集合加工與配送的供應(yīng)鏈在線排序問(wèn)題，因其具有明顯的實(shí)際應(yīng)用背景，因此具有很高的研究?jī)r(jià)值本文就以上兩種模型為基礎(chǔ)展開(kāi)研究論文共分三章，結(jié)構(gòu)安排如下t第一章主要介紹排序問(wèn)題的由來(lái)及其應(yīng)用背景，概述了由排序問(wèn)題引申出的相關(guān)定義以及所涉及的預(yù)備知識(shí)，分析了所研究問(wèn)題的研究現(xiàn)狀，并簡(jiǎn)單介紹了文章的主要結(jié)果和創(chuàng)新點(diǎn)第二章主要討論了成組分批加工問(wèn)題，分別考慮其在線和離線情形對(duì)于在線的目標(biāo)函數(shù)為所有

3、工件總完工時(shí)間的成組加工問(wèn)題，我們給出相應(yīng)的在線算法而對(duì)于離線情形的目標(biāo)函數(shù)為超前有獎(jiǎng)延后受罰的成組加工排序問(wèn)題，目前由于該問(wèn)題的一般情況已被證明是NP難的，因此我們針對(duì)幾種特殊情況進(jìn)行討論，給出最優(yōu)算法，并分析了算法的計(jì)算復(fù)雜性第三章主要研究集成加工和配送的供應(yīng)鏈在線排序問(wèn)題，目標(biāo)函數(shù)為工件最大延誤時(shí)間與配送費(fèi)用之和該問(wèn)題是傳統(tǒng)的排序與當(dāng)代物流相結(jié)合而產(chǎn)生的一類(lèi)新的排序問(wèn)題本章在前人研究的基礎(chǔ)上，對(duì)某些條件加以限制，使其更符合實(shí)際情況