帶有惡化效應(yīng)的單機(jī)供應(yīng)鏈排序問(wèn)題.pdf

1、排序論是運(yùn)籌學(xué)中最重要的分支之一。供應(yīng)鏈排序是供應(yīng)鏈管理與排序理論相結(jié)合產(chǎn)生的新領(lǐng)域,它將排序理論應(yīng)用于供應(yīng)鏈管理,集成研究生產(chǎn)調(diào)度和分批配送這兩個(gè)問(wèn)題。工件帶有惡化效應(yīng)的排序和工件可拒絕的排序是兩種新興起的現(xiàn)代排序模型,它們更接近現(xiàn)實(shí)生活,因而具有很好的研究?jī)r(jià)值。本文將上述三類(lèi)排序問(wèn)題相結(jié)合,討論了幾個(gè)相關(guān)的排序問(wèn)題。論文主要結(jié)構(gòu)安排如下：
　　第一章緒論部分主要介紹了供應(yīng)鏈排序問(wèn)題、帶有惡化效應(yīng)的排序問(wèn)題、可拒絕排序,算法的復(fù)

2、雜性以及本文所需要的基礎(chǔ)知識(shí),并對(duì)本文的主要工作進(jìn)行了簡(jiǎn)要描述。
　　第二章主要研究了帶有惡化效應(yīng)的單機(jī)供應(yīng)鏈排序問(wèn)題：一個(gè)制造商為一個(gè)客戶(hù)加工工件,每個(gè)工件的加工時(shí)間是其開(kāi)工時(shí)間的簡(jiǎn)單線(xiàn)性增函數(shù),工件加工完之后要安排車(chē)輛配送給客戶(hù),完工時(shí)間為工件送達(dá)客戶(hù)的時(shí)刻。在同一輛車(chē)配送的工件為一批,每一批可同時(shí)配送至多n個(gè)工件,每配送一批要支付一定的配送費(fèi)用。我們分析了加工時(shí)間為其開(kāi)工時(shí)間的不同函數(shù),目標(biāo)函數(shù)分別為極小化總完工時(shí)間與總配送

3、費(fèi)用之和、極小化最大延誤時(shí)間與總配送費(fèi)用之和的情形,并分別給出了多項(xiàng)式時(shí)間的最優(yōu)算法。
　　第三章在第二章的基礎(chǔ)上研究了工件可拒絕的情形。一個(gè)制造商為一個(gè)客戶(hù)加工工件,每個(gè)工件既可以被接受加工,也可以被拒絕加工。若工件被拒絕,則要支付一定的拒絕費(fèi)用。若工件被接受,則其加工時(shí)間是其開(kāi)工時(shí)間的簡(jiǎn)單線(xiàn)性增函數(shù),且加工完之后要被安排在車(chē)輛運(yùn)送給客戶(hù),完工時(shí)間為工件送達(dá)客戶(hù)的時(shí)間。在同一輛車(chē)配送的工件為一批,每配送一批要支付一定的配送費(fèi)用,