（運(yùn)籌學(xué)與控制論專業(yè)論文）供應(yīng)鏈管理中的若干排序問題研究(1).pdf

摘要 摘要 排序問題是一類經(jīng)典的組合優(yōu)化問題 從上世紀(jì)5 0 年代至今受到了許多行 業(yè)的從業(yè)人員與理論研究者的密切關(guān)注 本文主要研究排序問題在供應(yīng)鏈管理 中的應(yīng)用 眾所周知 供應(yīng)鏈?zhǔn)怯啥鄠€環(huán)節(jié)構(gòu)成的 因此我們不能孤立地研究 排序問題 而要把排序問題與其它過程綜合考慮 全文共分四章 第一章主要介紹了供應(yīng)鏈與排序問題的一些知識和概念 并且總結(jié)了近些 年來在綜合考慮排序與運(yùn)輸?shù)膯栴}研究方面取得的一些成果 第二章研究工件占用運(yùn)輸工具空間不同的綜合考慮運(yùn)輸和排序的問題 在 這類問題中 工件在機(jī)器上完成加工后 需要由唯一的一輛運(yùn)輸工具運(yùn)送到相 應(yīng)的顧客處 運(yùn)輸工具的空間是有限的 每個工件占用運(yùn)輸工具的空間各不相 同 目標(biāo)函數(shù)是極小化最后一個到達(dá)顧客的工件的到達(dá)時間 當(dāng)機(jī)器環(huán)境是單 臺機(jī) 所有工件的顧客相同時 我們設(shè)計了最壞情況界為3 2 e e 是任意正 常數(shù) 的漸近最優(yōu)算法 當(dāng)機(jī)器環(huán)境是兩臺平行機(jī) 所有工件的顧客相同時 我們給出了了最壞情況界為5 3 的近似算法 第三章討論了允許在兩個加工工廠之間運(yùn)送原材料或成品的排序問題 每 個工廠可以加工所有屬于本身的工件 也可以把一些工件運(yùn)送到另一個工廠去 加工 這樣的運(yùn)送需要一定的時間 若某個工廠需要另一家工廠加工一些工 件 根據(jù)工廠和工件的不同要求 有以下三種情形 1 在工件加工之前 原 材料不需要運(yùn)送 工件完成加工后 需要被運(yùn)送回有需求的工廠 2 在工件 加工之前 需要先運(yùn)送原材料 工件完成加工后不需要被送回有需求的工廠 3 在工件加工之前 需要先運(yùn)送原材料 工件完成加工后 需要被運(yùn)送回 有需求的工廠 問題的目標(biāo)函數(shù)都是極小化最后一個完工工件的完工時間 對 這三個問題 我們分別設(shè)計了最壞情況界為4 3 4 3 和3 2 的線性時間近似算 法 并且給出了動態(tài)規(guī)劃算法 第四章研究了帶承諾到貨時間的排序問題 在該問題中 企業(yè)根據(jù)顧客的 訂單來加工產(chǎn)品 并把完成的訂單交由第三方物流公司運(yùn)送給顧客 每個訂單 包含不同的產(chǎn)品數(shù)量 而且必須在顧客要求的時問之前送達(dá) 訂單產(chǎn)生的運(yùn)輸 費(fèi)用與其中的產(chǎn)品數(shù)量以及運(yùn)輸需要的時間有關(guān) 我們的目標(biāo)是安排一個加工 訂單的持序并為每個訂單選擇運(yùn)輸時間 使得所有訂單都能在承諾的最遲到貨 時間之前到達(dá)其顧客處 并且產(chǎn)生的總運(yùn)輸費(fèi)用盡量地少 我們給出了此問題 摘要 的最壞情況界為2 的近似算法 并且證明了這個界是緊的 關(guān)鍵詞 排序問題 供應(yīng)鏈管理 近似算法 最壞情況界 動態(tài)規(guī)劃 a b s t m c t a b s t r a c t s c h e d u l i n gp r o b l e m o n eo ft h ec l a s s i c a lc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s h a sg a i n e dg r e a ta t t e n t i o nf r o mb o t hm a n u f a c t u r e r sa n da c a d e m i cr e s e a r c h e r s t h i s t h e s i sm a i n l yc o n c e r n ss o m es c h e d u l i n gp r o b l e m si ns u p p l yc h a i nm a n a g e m e n t a s w ea l lk n o w s u p p l yc h a i ni sc o m p o s e do fs e v e r a ls t e p s t h u st h ei n t e g r a t e di n v e s t i g a t i o no fs c h e d u l i n ga n do t h e rs t e p so fs u p p l yc h a i ni sn e c e s s a r y w ec o n s i d e r e ds o m e s c h e d u l i n gp r o b l e m sw i t ht r a n s p o r t a t i o n t h et h e s i si ss p l i ti n t of o u rc h a p t e r s w ef i r s ti n t r o d u c es o m er e l a t e dp r e l i m i n a r yc o n c e p t so fs u p p l yc h a i na n ds c h e d u l i n ga n dt h e ns u m m a r i z er e c e n tr e s e a r c hr e s u l t so fs c h e d u l i n gp r o b l e m sw i t ht r a n s p o r t a t i o ni nc h a p t e r1 i nc h a p t e r2 w ei n v e s t i g a t es c h e d u l i n gp r o b l e m sw i t ht r a n s p o r t a t i o n i nw h i c he v c r yj o bn e e d st ob ed e l i v e r e dt oi t sc u s t o m e ra f t e rp r o d u c t i o na n dt h ec o m p l e t i o nt i m e i sd e f i n e da st h et i m ew h e nt h ei o ba r r i v e sa ti t sc u s t o m e r t h e r ei so n ev e h i c l e 嘶t l l l i m i t e dc a p a c i t y a n de a c hj o bo c c u p i e sd i f f e r e n ts i z ei nt h ev e h i c l ed u r i n gt r a n s p o r t a t i o n t h eg o a li st om i n i m i z et h em a x i m u mj o bc o m p l e t i o nt i m e w h e nt h e r ei sa s i n g l em a c h i n ef o rp r o c e s s i n gj o b sa n do n l yo n ec u s t o m e r w ep r e s e n taa s y m p t o t i c a l b e s tp o s s i b l ep o l y n o m i a l t i m ea p p r o x i m a t i o na l g o r i t h mw i t hw o r s tc a s er a t i oo f3 2 e e 0 w h e n t h e r ea r et w op a r a l l e lm a c h i n e sf o rp r o c e s s i n gj o b sa n do n l yo n ec u s t o m e r w ep r o p o s eap o l y n o m i a l t i m ea p p r o x i m a t i o na l g o r i t h mw i t hw o r s t c a s er a t i oo f 5 3 i nc h a p t e r3 w ec o n s i d e rs c h e d u l i n gp r o b l e m sw i t hr a wm a t e r i a la n dc o m p l e t e d p r o d u c td e l i v e r yb e t w e e nt w od i f f e r e n tp r o c e s s i n gc e n t e r s e a c hp r o c e s s i n gc e n t e ri s a l l o w e dt op r o c e s s j o b sb e l o n g i n gt ot h eo t h e ro n e a n di nd o i n gt h i s t r a n s p o r t a t i o nc o s t o c c u r s i fap r o c e s s i n gc e n t e rp r o c e s s e sj o b sb e l o n g i n gt ot h eo t h e ro n e a c c o r d i n gt o d i f f e r e n tc h a r a c t e r i s t i c so ft h ep r o c e s s i n gc e n t e r sa n dj o b s t h r e ec a s e sa l es t u d i e d 1 b e f o r ep r o c e s s i n g l a wm a t e r i a ld on o tn e e dt ob et r a n s p o r t e dt ot h eo t h e rm a c h i n ea n d a f t e rp r o c e s s i n g t h ec o m p l e t e dj o b sm u s tb et r a n s p o r t e db a c kt ot h eo r i g i n a lm a c h i n e 2 b e f o r ep r o c e s s i n g r a wm a t e r i a lm u s tb et r a n s p o r t e d t ot h eo t h e rm a c h i n ea n da f t e r p r o c e s s i n g t h ec o m p l e t e dj o b sd on o tn e e dt ob et r a n s p o r t e d b a c kt ot h eo r i g i n a lm a c h i n e 3 b e f o r ep r o c e s s i n g l a wm a t e r i a lm u s tb et r a n s p o r t e dt ot h eo t h e r m a c h i n e a n da f t e rp r o c e s s i n g t h ec o m p l e t e dj o b sm u s tb et r a n s p o r t e db a c kt ot h eo r i g i n a lm a 一i l l a b s t r a c t c h i n e t h e g o a li st om i n i m i z et h em a x i m u mj o bc o m p l e t i o nt i m e f o rt h ea b o v et h r e e p r o b l e m s w ep r e s e n tl i n e a rt i m ea p p r o x i m a t i o na l g o r i t h m sw i t hw o r s tc a s er a t i oo f 4 3 4 3 a n d3 2 r e s p e c t i v e l y b e s i d e s a nd y n a m i cp r o g r a m m i n ga l g o r i t h mi sg i v e n f o re a c hp r o b l e m i nc h a p t e r4 w em u d ya ni n t e g r a t e dp r o d u c t i o na n dd i s t r i b u t i o ns c h e d u l i n gp r o b l e mw i t hc o m m i t t e dd e l i v e r yd a t e s i nt h i sp r o b l e m t h em a n u f a c t u r i n gc o m p a n yu s e s at h i r d p a r t yl o g i s t i c ss e r v i c ep r o v i d e rf o rs h i p p i n gt h ec o m p l e t e do r d e rw i t hd i f f e r e n t c o m m i t t e dd e l i v e r yd a t e st oc u s t o m e r s t h es h i p p i n gc o s to fa no r d e ri sr e l a t i v et ot h e o r d e rs i z ea n dt h e d e l i v e r yt i m er e q u e s t e d t h eg o a li st od e t e r m i n eap r o d u c t i o ns c h e d u l ef o ra c c e p t e do r d e r sa n das h i p p i n gt i m ef o rd e l i v e r i n ge a c hc o m p l e t e do r d e rs ot h a t t h et o t a ls h i p p i n gc o s ti sm i n i m u ms u b j e c tt ot h ec o n s t r a i n tt h a ta l lt h eo r d e r sa r ec o m p l e t e da n dd e l i v e r e dt ot h e i rc u s t o m e r so no rb e f o r et h er e s p e c t i v ec o m m i t t e dd e l i v e r y d a t e s f o rt h i ss t r o n g l yn p h a r dp r o b l e m w e p r o p o s eap o l y n o m i a l t i m eh e u r i s t i ca l g o r i t h ma n ds h o wt h a tt h ew o r s t c a s ep e r f o r m a n c er a t i oi sb o u n db y2a n dt h i sb o u n d i st i g h t k e yw o r d s s c h e d u l i n g s u p p l yc h a i nm a n a g e m e n t a p p r o x i m a t i o na l g o r i t h m w o r s t c a s ea n a l y s i s d y n a m i cp r o g r a m m i n g 一l v 第一章緒論 第一章緒論 1 1 排序問題與供應(yīng)鏈管理 排序 s c h e d u l i n g 問題是組合優(yōu)化中一類有著重要理論意義和廣泛實際背 景的問題 其實質(zhì)是研究如何在滿足一定要求下 對需求完成任務(wù)的合理安排 以得到某種意義下的最優(yōu)結(jié)果 排序理論與理論計算機(jī)科學(xué)和離散組合數(shù)學(xué)存 在著密切的聯(lián)系 并廣泛應(yīng)用到生產(chǎn)計劃調(diào)度 信息處理 物流管理 服務(wù)行 業(yè)等領(lǐng)域 近幾十年來 排序問題得到了運(yùn)籌學(xué) 工程學(xué) 管理學(xué)和計算機(jī)科 學(xué)界的極大關(guān)注 并且隨著對經(jīng)典問題研究的日趨深入 大量具有實際背景的 新問題不斷涌現(xiàn) 自上世紀(jì)5 0 年代人們開始研究排序問題至今 已有大量的排 序文獻(xiàn)發(fā)表在國內(nèi)外的學(xué)術(shù)期刊上 可以這樣說 排序研究已經(jīng)成為組合優(yōu)化 領(lǐng)域最活躍的分支之一 按照學(xué)術(shù)界多年來形成的慣例 我們把需要完成的任務(wù)稱為工件 j o b 把完成任務(wù)需要的資源稱為機(jī)器 m a c h i n e 我們希望找到一個可行的排序 f e a s i b l es c h e d u l e 使得某個給定的目標(biāo)函數(shù)達(dá)到最小 大 這里可行一 般指在同一時刻 一臺機(jī)器至多加工一個工件 一個工件也只在一臺機(jī)器上加 工 并且該排序滿足問題特定的約束要求 描述一個排序問題可以用一種所謂 三參數(shù)表示法 t h r e e f i e l dr e p r e s e n t a t i o n o p 7 1 8 其中0 1 p 7 分別 代表特定的機(jī)器環(huán)境 工件特征和最優(yōu)準(zhǔn)則 它們是排序問題的三個組成部 分 機(jī)器環(huán)境用來描述機(jī)器的數(shù)量 不同機(jī)器之間的關(guān)系等與機(jī)器有關(guān)的 性質(zhì) 常見的機(jī)器系統(tǒng)包括單臺機(jī) s i n g l em a c h i n e 平行機(jī) p a r a l l e lm a c h i n e s 流水作業(yè) f l o ws h o p 有序作業(yè) i o bs h o p 和自由作業(yè) o p e n s h o p 等 其中 平行機(jī)根據(jù)其性能的不同還可分為三類 同型平行機(jī) i d e n t i c a lp a r a l l e lm a c h i n e s 系統(tǒng)中所有機(jī)器的功能 效率完全一樣 同 類平行機(jī) u n i f o r mp a r a l l e lm a c h i n e s 系統(tǒng)中機(jī)器有各自不同的加工速度 但任意工件在不同機(jī)器上的加工時間有相同的比例關(guān)系 不同類平行機(jī) u n r e l a t e dp a r a l l e lm a c h i n e s 系統(tǒng)中機(jī)器各不相同 工件在不同機(jī)器上的加 工時間比不全相同 在三參數(shù)表示法中 它們分別用p q j r 表示 工件特征一般包括工件的加工時間 通常也稱為工件長度 工件的釋放 第一章緒論 時間 工件相互之間的依賴關(guān)系 工件加工時是否允許中斷以及中斷恢復(fù)后再 加工時是否要受懲罰等等 根據(jù)排序者對工件信息的了解程度 又可將排序問 題分為離線 o f f l i n e 在線 o n l i n e 和半在線 s e m i o n l i n e 等 如果排序 者在排序開始前就已經(jīng)知道工件的全部信息 例如工件數(shù) 每個工件的加工時 間等 則稱該問題是離線的 而如果工件的信息是隨著排序過程逐個釋放的 即只有在位于某個工件前的全部工件均被安排完畢后 排序者才能知道該工件 的有關(guān)信息 而且工件一旦被安排就不能改變 這樣的排序問題稱為在線的 但在實際問題中 大量的問題是介于兩者之間的 即我們或者知道該問題的一 些整體信息 或者知道后續(xù)工件的部分信息 我們把這樣的問題稱為是半在線 的 所謂最優(yōu)準(zhǔn)則 通俗地講 也就是以什么為目標(biāo)函數(shù) 如果記g 為某個排 序問題的可行排序中工件以的完工時間 則稱 戕 m a x q 為該排序的工 件最大完工時間 m a k e s p a n 它即為某種最優(yōu)準(zhǔn)則下的目標(biāo)函數(shù) 其最優(yōu)準(zhǔn) 則為 找一個可行排序 使得工件的最大完工時間 旺在所有的可行排序中取 得最小值 即最小化目標(biāo)函數(shù) 文獻(xiàn)中常見的其他目標(biāo)函數(shù)還有 賦權(quán) 總完 工時間 最大延誤時間 最大誤工時間 最小誤工個數(shù)等 有關(guān)排序問題的綜 述 可參看 3 4 1 1 企業(yè)從原材料和零部件采購 運(yùn)輸 加工制造 分銷直至最終送到顧客手 中的這一過程被看成是一個環(huán)環(huán)相扣的鏈條 這就是供應(yīng)鏈 供應(yīng)鏈的概念是 從擴(kuò)大的生產(chǎn) e x t e n d e dp r o d u c t i o n 概念發(fā)展來的 它將企業(yè)的生產(chǎn)活動進(jìn)行 了前伸和后延 譬如日本豐田公司的精益協(xié)作方式就將供應(yīng)商的活動視為生產(chǎn) 活動的有機(jī)組成部分而加以控制和協(xié)調(diào) 這就是向前延伸 后延是指將生產(chǎn)活 動延伸至產(chǎn)品的銷售和服務(wù)階段 因此 供應(yīng)鏈就是通過計劃 獲得 存儲 分銷 服務(wù)等這樣一些活動而在顧客和供應(yīng)商之間形成的一種銜接 從而使企 業(yè)能滿足內(nèi)外部顧客的要求 供應(yīng)鏈對上游的供應(yīng)者 供應(yīng)活動 中間的生 產(chǎn)者 制造活動 和運(yùn)輸商 儲存活動 以及下游的消費(fèi)者 分銷活動 同 樣重視 因此 供應(yīng)鏈管理就是對整個供應(yīng)鏈系統(tǒng)進(jìn)行計劃 協(xié)調(diào) 操作 控制和優(yōu)化的各種活動和過程 其目標(biāo)是要將顧客所需要的正確的產(chǎn)品 r i g h t p r o d u c t 能夠在正確的時間 r i g h tt i m e 按照正確的數(shù)量 r i g h tq u a n t i t y 正 確的質(zhì)量 r i g h tq u a l i t y 和正確的狀態(tài) r i g h ts t a t u s 送到正確的地點 r i g h tp l a c e 即 6 r 并使總成本最小 在世界經(jīng)濟(jì)全球化的今天 供應(yīng)鏈管理能力已經(jīng)列為企業(yè)一類重要的戰(zhàn)略 一2 一 第一章緒論 競爭資源 尤其我國是個制造大國 從供應(yīng)鏈管理的角度來考慮企業(yè)的經(jīng)營活 動 形成這方面的核心能力 將對經(jīng)濟(jì)發(fā)展變得越來越重要 產(chǎn)品的加工與運(yùn)輸是供應(yīng)鏈中的關(guān)鍵兩步 把這兩步工作有機(jī)結(jié)合 綜 合考慮將對節(jié)約成本 提高工作效率與客戶滿意度有明顯的促進(jìn)作用 已 經(jīng)有許多學(xué)者從整體構(gòu)建供應(yīng)鏈架構(gòu)的角度對綜合考慮加工與運(yùn)輸過程作 了大量研究 這方面的文獻(xiàn)綜述有b i l g e n 和o z k a r a h a n 1 c h e n 5 e r e n g u c 等 1 0 g o e t s c h a l c k x 等 1 5 s a r m i e n t o 和n a g i 4 5 以及t h o m a s 和g r i f f i n 4 8 另外 最近幾年來 有許多學(xué)者從具體的排序角度來綜合研究產(chǎn)品的加 工和運(yùn)輸問題 目標(biāo)是在考慮相關(guān)的效益 費(fèi)用和顧客滿意度的基礎(chǔ)上 找到 關(guān)于加工與運(yùn)輸產(chǎn)品的最優(yōu)排序 這類問題是對研究整體供應(yīng)鏈構(gòu)建的深入 這類問題根據(jù)運(yùn)輸之后是否有后續(xù)加工可以分為兩類 一類是成品的運(yùn)輸 i n t e g r a t e dp r o d u c t i o na n do u t b o u n dd i s t r i b u t i o ns c h e d u l i n g i p o d s 4 也就是 把產(chǎn)品運(yùn)送到相應(yīng)的顧客處 排序任務(wù)就結(jié)束了 另一類是原材料或半成品 的運(yùn)輸 i n t e g r a t e dp r o d u c t i o na n di n b o u n d d i s t r i b u t i o ns c h e d u l i n g i p i d s 4 也 就是在運(yùn)輸之后還需要加工工件 在關(guān)于i p o d s 的文獻(xiàn)中 h a l l 和p o t t s 1 9 2 0 c h e n 和v a i r a k t a r a k i s 8 w a n g 和l e e 4 9 p u n d o o r 和c h e n 4 2 c h e n 和 p u n d o o r 7 l i 和o u 3 5 l i 和v a i r a k t a r a k i s 3 6 等人研究了綜合考慮運(yùn)輸費(fèi)用 與顧客滿意程度的問題 h e r r m a n n 和l e e 2 2 c h e n g 等 9 j i 等 2 4 考慮了 總庫存成本與總運(yùn)輸費(fèi)用相結(jié)合的問題 l e e 和c h e n 3 0 g e i s m a r 等 1 4 l i 等 3 7 l i 和o u 3 4 w a n g 和c h e n g 5 0 p a n 等 4 0 研究了運(yùn)輸工具數(shù)量有 限的情形下最大化客戶滿意度的問題 c h e n 和p u n d o o r 6 考慮了工件帶約束 的條件下 如何最小化運(yùn)輸費(fèi)用 g a r c i a 等 1 2 g a r c i a 和l o z a n o 1l s t e c k e 和z h a o 4 7 則研究了在保證運(yùn)輸及時性的基礎(chǔ)上 最大化總效益的問題 q i 4 3 和 4 4 研究的問題中 一個工廠可以把顧客要求的工件交由另一家工 廠加工 在不同的工廠之間需要時間來運(yùn)送工件 c h a n g 和l e e 2 p a n 等 4 0 研究了工件占用運(yùn)輸工具空間大小不同的問題 目標(biāo)是最大化顧客的滿 意度 關(guān)于i p i d s 類問題的文獻(xiàn)有l(wèi) a n g s t o n 2 7 h u r i n k 和k n u s t 2 3 l e e 和 c h e n 3 0 l e e 和s t r u s e v i c h 31 下面我們對以上提到的部分研究作更具體的介紹 還有一些文獻(xiàn)研究的問 題在后面的章節(jié)中會涉及到 文獻(xiàn) 8 研究了下面的問題 工件在機(jī)器上完成加 工后 要由開始位于機(jī)器處的容量限制相同的運(yùn)輸工具運(yùn)送到各自的顧客處 在這里 有足夠多的運(yùn)輸工具可以在機(jī)器與顧客間以及不同的顧客間運(yùn)送工 一3 一 第一章緒論 件 所需的時間各不相同 運(yùn)輸工具每運(yùn)送一趟 都會產(chǎn)生與該趟運(yùn)送路線相 關(guān)的運(yùn)輸費(fèi)用 問題的目標(biāo)是極小化最后一個到達(dá)顧客的工件的到達(dá)時間與總 運(yùn)輸費(fèi)用的凸和或者所有工件到達(dá)相應(yīng)顧客的時間之和與總運(yùn)輸費(fèi)用的凸和 針對機(jī)器環(huán)境 顧客的數(shù)目以及目標(biāo)函數(shù)不同的情形 作者討論了計算復(fù)雜 性 給出了最優(yōu)算法或者近似算法 并且進(jìn)行了數(shù)值模擬 在文獻(xiàn) 1 9 研究的 問題中 工件在供應(yīng)商處完成第一步加工后 被送到工廠處進(jìn)行第二步加工 然后被運(yùn)送到相應(yīng)的顧客處 只有一個供應(yīng)商 有多個工廠 機(jī)器加工環(huán)境都 是單臺機(jī)器 運(yùn)輸工具的數(shù)目與容量沒有限制 目標(biāo)是極小化總完工時間 最 大延誤時間或者 加權(quán) 總誤工工件個數(shù) 作者討論了問題的計算復(fù)雜性 給 出了動態(tài)規(guī)劃算法 文獻(xiàn) 2 4 的問題中 工件在單臺機(jī)上完成加工后 被分批 送往顧客處 運(yùn)輸工具的數(shù)目與容量沒有限制 每運(yùn)送一批工件就會產(chǎn)生一筆 運(yùn)輸費(fèi)用 工件完工時間定義為在機(jī)器上的完工時間 目標(biāo)是極小化賦權(quán)工件 完工時間之和與總運(yùn)輸費(fèi)用之和 作者討論了問題的計算復(fù)雜性 對一些特殊 情形給出了動態(tài)規(guī)劃算法或多項式時間最優(yōu)算法 文獻(xiàn) 3 0 研究了兩類帶運(yùn)輸 的排序問題 第一類問題 t y p e1 中 機(jī)器系統(tǒng)是流水作業(yè) 所有工件必須 按相同序從在第一臺機(jī)器到最后一臺機(jī)器上完成每道工序 工件從一臺機(jī)器到 下一臺機(jī)器的運(yùn)輸工作由有限個有容量限制 開始時在第一臺機(jī)器處的運(yùn)輸工 具來完成 不同的工件可以在同一批被運(yùn)送 而運(yùn)輸工具在不同的機(jī)器間運(yùn)送 需要的時間各不相同 目標(biāo)是極小化在最后一臺機(jī)器上的最大工件完工時間 當(dāng)運(yùn)輸工具數(shù)目 運(yùn)輸工具容量以及工件的一些性質(zhì)各不相同時 作者討論了 問題的計算復(fù)雜性 給出了動態(tài)規(guī)劃算法 在第二類問題 t y p c2 中 工件 在機(jī)器上完成加工后 需要由有限個有容量限制 開始時在機(jī)器處的運(yùn)輸工具 運(yùn)送到同一個顧客處 運(yùn)輸工具從機(jī)器到顧客與從顧客回到機(jī)器的時間不同 目標(biāo)是極小化最后一個到達(dá)顧客的工件的到達(dá)時間 當(dāng)機(jī)器環(huán)境 運(yùn)輸工具數(shù) 目 運(yùn)輸工具容量各不相同時 作者討論了問題的計算復(fù)雜性 給出了動態(tài)規(guī) 劃算法 文獻(xiàn) 3 4 研究了原材料與完工工件都需要運(yùn)輸?shù)膯栴} 在開工之初 僅有的一個有容量限制的運(yùn)輸工具要把未加工的工件從倉庫運(yùn)送到一臺單臺機(jī) 上去加工 這輛運(yùn)輸工具還要把完成加工的工件運(yùn)送回這個倉庫 運(yùn)輸工具從 倉庫到機(jī)器與從機(jī)器回到倉庫的容量限制不同 而所需時間相同 問題的目標(biāo) 是極小化最后一個到達(dá)倉庫的完工工件的到達(dá)時間 作者討論了問題的計算復(fù) 雜性 提出了一個多項式時間近似算法 并且進(jìn)行了數(shù)值模擬 文獻(xiàn) 3 7 研究 了如下的帶運(yùn)輸排序問題 工件在單臺機(jī)上完成加工后 需要由僅有的一臺有 一4 一 第一章緒論 容量限制的運(yùn)輸工具運(yùn)送到各自的顧客處 機(jī)器與不同的顧客之間的運(yùn)輸時間 以及不同的顧客間的運(yùn)輸時間各不相同 工件的完工時間定義為其到達(dá)相應(yīng)顧 客的時間 問題的目標(biāo)是極小化工件總完工時間 進(jìn)一步的 作者還討論了運(yùn) 輸工具在顧客內(nèi)部不能運(yùn)輸 即同一批的工件只能屬于同一個顧客的情形 作 者討論了問題的計算復(fù)雜性 給出了問題的動態(tài)規(guī)劃算法 并對一些特殊情形 給出了最優(yōu)算法 文獻(xiàn) 3 9 考慮了帶工件釋放時間的問題 在每個工件的釋放 時間之前 不能加工該工件 工件在單臺機(jī)上完成加工后 要由唯一的一個運(yùn) 輸工具送到同一顧客處 每個工件占用運(yùn)輸工具的空間相同 目標(biāo)是極小化最 后一個到達(dá)顧客的工件的到達(dá)時間 當(dāng)工件的加工是可中斷時 問題是多項式 時間可解的 當(dāng)工件加工不可中斷時 作者提出了一個近似算法 分析了最壞 情況界 文獻(xiàn) 4 0 中 工件在兩臺流水作業(yè)機(jī)器上完成加工后 由僅有的一臺 有容量限制的運(yùn)輸工具送到同一個顧客處 每個工件占用運(yùn)輸工具空間大小不 同 工件的完工時間定義為到達(dá)顧客的時間 目標(biāo)是極小化工件總完工時間或 最大工件完工時間 作者討論了問題的計算復(fù)雜性 對一些問題給出了多項式 時間的近似算法 文獻(xiàn) 4 3 研究了這樣一類問題 一個加工工廠可以自己加 工接收的訂單中的工件 也可以把一些工件交由另一個工廠加工 并把完成的 工件送回原來的工廠 針對目的地相同的工件只可以一批運(yùn)送或者一個一個地 運(yùn)送以及目標(biāo)函數(shù)不同的情形 作者給出了最優(yōu)算法或者動態(tài)規(guī)劃算法 文獻(xiàn) 5 0 研究了帶機(jī)器維護(hù)時段的問題 機(jī)器并不總是可運(yùn)作的 在某個需要維護(hù) 的時間段內(nèi)不能加工任何工件 工件在機(jī)器上完成加工后 需要由唯一的有容 量限制的運(yùn)輸工具送到同一個顧客處 運(yùn)輸工具在機(jī)器與顧客間往返的時間相 同 問題的目標(biāo)是極小化最后一個到達(dá)顧客的工件的到達(dá)時間 對機(jī)器環(huán)境是 單臺機(jī)器和兩臺平行機(jī)的情形 作者分別給出了問題的多項式時間最優(yōu)算法或 者近似算法 1 2 算法和計算復(fù)雜性 定義1 2 1 算法是指一步步求解問題的通用程序 它是解決問題的程序步驟的 一個清晰描述 確定性算法從前一步到后一步的運(yùn)行由當(dāng)前狀態(tài)唯一確定 定義1 2 2 對于一個排序問題7 r 如果給定任意一個實例 算法a 總能找到 一個可行解仃 并且仃的目標(biāo)值總等于最優(yōu)解值 則稱a 為最優(yōu)算法 o p t i m a l a l g o r i t h m 一5 一 第一章緒論 將實例通過某種規(guī)則編碼后輸入計算機(jī)所用的字節(jié)數(shù)稱為該實例的的輸入 長度 通常 算法所用的時間是指算法中所含的加 減 乘 除 比較等基本 運(yùn)算次數(shù) 而算法所用的時間與實例的輸入長度有關(guān) 定義1 2 3 算法的時間復(fù)雜性是指關(guān)于實例輸入長度n 的函數(shù) 廠 幾 用來表示 算法的時間需求 對每一個可能的輸入長度 它是指在最壞情況下該算法解此 輸入長度的實例時所需時間 基本運(yùn)算步數(shù) 即對于輸入長度相同的所有實 例 把算法對這些實例的最壞情況作為時間復(fù)雜性的度量 如果存在一個多項式函數(shù)p 佗 使得算法的時間復(fù)雜性為d p 釓 那么 稱該算法為多項式時間算法 否則稱為指數(shù)時間算法 還有一類算法叫偽多項 式時間算法 它的時間復(fù)雜性是關(guān)于實例輸入長度n 和實例中最大數(shù)的二元多 項式函數(shù) 在二進(jìn)制編碼下 偽多項式時間算法并不是多項式時間算法 而是 指數(shù)時間算法 由此出發(fā) 可以導(dǎo)出計算復(fù)雜性理論的一系列重要概念和結(jié)論 1 3 1 計算復(fù)雜性理論興起于二十世紀(jì)六十年代 和算法的設(shè)計與分析密切相 關(guān) 通過幾十年來人們在計算復(fù)雜性方面的研究 現(xiàn)今p p 的猜想己被基 本接受 在此前提下 所謂的n p h a r d 問題就不可能在多項式時間內(nèi)找到最 優(yōu)解 同時 尸一h a r d 問題中有一類更難的問題 稱為強(qiáng) p h a r d s t r o n g l y n p h a r d 問題 這類問題甚至都不存在偽多項式時間最優(yōu)算法 1 3 從而 人 們在解決方法的有效性 精確性和時間可行性上尋求平衡 這樣 一個自然的 想法就是放棄對最優(yōu)解的尋找 而把研究的重點轉(zhuǎn)向?qū)ふ夷茉谳^短時間 多項 式時間 內(nèi)得到接近于最優(yōu)解的可行解 稱為近似解 定義1 2 4 對于一個排序問題丌 如果給定任意一個實例 算法4 總能找到 一個可行解仃 那么就稱a 為7 r 的近似算法 a p p r o x i m a t i o na l g o r i t h m l s l i s ts c h e d u l i n g 算法 1 6 和l p t l a r g e s tp r o c e s s i n gt i m e 算法 1 7 是經(jīng)典平行機(jī)排序問題的近似算法 l s 算法將工件按序安排在能使其最早 完工的機(jī)器上加工 三p t 算法先把所有工件按加工時間的非增序排列 然后依 次將它們安排在能使其最早完工的機(jī)器上加工 我們衡量近似算法的優(yōu)劣可從兩個方面來看 一是算法的時間復(fù)雜性 二 是算法得到的解值與最優(yōu)解值的接近程度 一6 一 第一章緒論 定義1 2 5 如果7 r 是一個極小 大 化i j 題 是任意實例 設(shè)a 是丌的一個 近似算法 用 j 和c 分別表示算法a 解實例 所得的目標(biāo)函數(shù)值和實 例j 的最優(yōu)目標(biāo)函數(shù)值 記肌 黜 以 拱 則近似算法a 的 最壞情況界 w o r s t c a s er a t i o 定義為 p a t r i n f p 1l 以 p v i 如果對問題丌 任何近似算法的最壞情況界都比 大 則稱 是問題7 r 的 下界 在不引起混淆的前提下 我們通常將上述定義中的o c 和以 丌 分別簡記為以 c 和阢 定義1 2 6 如果某問題有一系列近似算法 a e 對于任意給定的e 0 a 是一個多項式時間算法 而且朋 1 e 則稱它為多項式時間近似方案 p o l y n o m i a lt i m ea p p r o x i m a t i o ns c h e m e 簡記為p t a s 進(jìn)一步的 如果 a 的時間復(fù)雜性是關(guān)于輸入長度以及 1 的某個二元多項式 則稱它為完全 多項式時間近似方案 f u l l yp o l y n o m i a lt i m ea p p r o x i m a t i o ns c h e m e 簡記為 f p r 肖s 對一個強(qiáng) p 一難的問題7 r 若存在兩個變量的多項式g 使得對于任何7 r 的實例 有 d p 丁 s f 試問應(yīng)該如何 把物品放到箱子中 使得各個箱子中所裝物品的尺寸總和不超過c 并且所用的 箱子數(shù)盡可能的少 關(guān)于裝箱問題 已經(jīng)能夠證明 除非p p 否則不存在最壞情況界 s j 試問應(yīng)該選取哪 些物品放入背包中 使得背包中所裝物品的尺寸總和不超過c 并且背包中物品 的價值總和盡可能的大 下面我們列出背包問題的 個近似算法 其最壞情況界為2 2 6 1 算法e x t g r e e d y 1 j 1 s 0 s 表示當(dāng)前背包中物品序g 尺寸之和 穢 0 秒表示當(dāng)前背包中物品的價值之和 2 若歹 禮 s s 3 c 則巧 1 把乃 放入背包中 否則 z j 0 一l o 第一章緒論 3 若j n 輸出m a x 器 巧 m 啦 吻 停止 否則 j 歹 1 進(jìn)入第2 步 l a w l e r 2 8 給出了背包問題的f 刀a s 其時間復(fù)雜性為d n l o g 吉 另外 k e l l e r e r 和p f e r s c h y 2 5 也提出了背包問題的f p t a s 其時間復(fù)雜性是 o n r a i n l o g n l o g 壺m i n n 1l o g 下面我們給出一個較為簡單的背包 問題的f p t a s 2 6 它的時間計算復(fù)雜性為o n 2 算法b a s i c f p t a s 1 運(yùn)行算法e x t g r e e d y 記得到的解值為z 2 將 j 2 厶 分成n e 個子集合m i 1 2 譬一1 使得 批一 1 1 i z n e 功 蘭竽 3 對任意物品乃 歹 1 2 n 若歹 m 則 i z e 功2i 啦2 2 4 y o o y q c 1 g 1 2 警 j 1 5 q 2 n 5 1 若可 口一 勺 p t 則p 1 p t 引理2 2 4 如果在最優(yōu)解中工件被分成兩批 則p u p 證明 每一批中的工件對應(yīng)的物品的集合都構(gòu)成背包問題實例的可行解 而 p 一 是最優(yōu)解中第二批工件的加工時間之和 因此p 一讓 p 引理2 2 5 砭 1 4 e p 其中砭是盯2 如果存在 中最后一批工件的總 加工時間 證明 由注記2 2 1 我們知道存在k 1 k 5 2 使得砭 1 4 e p 因為 巧 巧 砭 所以心 砭 1 4 e p 引理2 2 6 如果b 1 3 則 c m 萬h i 一 o 互3 證明 若b 1 3 則算法m h i e 只運(yùn)行算法h 1 因此c m m c 1 并且根 據(jù)前面的假設(shè)我們只需要考慮c 1 p 1 b l t 的情形 注意到此時有1 1 t 若擴(kuò) 1 即所有工件尺寸之和不超過z 則b 1 1 以及c 1 c p 丁 因此 我們下面只考慮b 2 的情形 若b l b 由引理2 2 3 可知 萬c 1 籌 嚳 1 爭吉 3 擴(kuò)的情形 情形l c 亂 6 t 由引理2 2 3 我們可知 u 6 事t p 十丁 即p u b 一1 t 注意到有 p l 島 冬r 因此bs 善 蘭 業(yè) 進(jìn)一步的我們可以得到 1 7 一 第二章工件占運(yùn)輸工具不同空間的帶運(yùn)輸排序問題 c 1 一 p 1 b l 丁 半 6 1 t c u 6 卓t t 正 滬t 1 亂 擴(kuò)t 晴一1 t b l 锃 滬t 11 6 2 1 t j 6 1 b l u 6 t 11b 2 1 擴(kuò)t 所以 p u b 一1 t b 一1 z 由于p l 等 我們可以推出 c 1 p 1 6 1 丁 魯 6 i 丁 一 一 一 c 尸 丁一p 十t 1 p t 6 一1 t 6 1 1 b 1 1 b i 1 6 1 p 七t 6 2 1t b 1p t 6 2 1t b 滬t 6 2 1l b 6 綜合以上兩種情形 我們可以得到 岳 面 i 1 i 1 字 2 t 注意到在算法h 1 中 算法f f d 把工件分成了b 1 批 由引理1 4 1 可知 6 l b 可知b l 3 這與假設(shè)b l 3 矛盾 若擴(kuò) 3 由式 2 2 可知b l 警 礦 因此b 1 4 結(jié)合式 2 i 可以得到象 類似的 若b 4 則b 1 5 并且籍 若b 5 由式 2 2 和引理 1 4 2 可知b l 6 因此孓 若擴(kuò) 6 則b l 7 或8 因此孓 若 b l 7 或者岳 囂 若b l 8 若b 4 7 由式 2 2 p a 得到b 坐鏟 把其代入式 2 1 我i f i 以推出 萬e l 瓦1 1 掣 苦 署 1 12 013 百 6 否2 互 引理2 2 7 若b l 3 則c m 伊h i p t 并且q p t 由引理2 2 2 可知r t 且爿 t 若b 1 b 在引理2 2 5 中我們已經(jīng)證明了似c a 擴(kuò) 因此有b 2 由引理1 4 1 可以得到5 2 幸2 蠆7 也就是 b 2 3 進(jìn)一步的 如果b 2 b 與引理2 2 6 中類似的證明 我們可以得到 岳 i 因此 下面我們假設(shè)b 2 礦 注意到有b 2 3 且礦 2 我們可以得 出b 2 3 由引理2 2 3 可以知道c m a x 亂 2 t p t 下面分兩種情形討論 情形lc u 2 t 此時有p 缸 t 由引理2 2 4 和2 2 5 我們知道彰芝 1 4 e p 一讓 注意到有爿 砭s 巧以及p 爿4 巧 砭 我們可以推出 爿 生蔓 二 二型竺二墮 4 p 1 4 e u 1 2 22 4 e u t 1 4 e u 4 e t u 2 1 9 第二章工件占運(yùn)輸工具不同空間的帶運(yùn)輸排序問題 因此 g c 爿 3 t 塹弩坐 3 t 一塑筍 2 2 e t 亂 2 t 二u 2 tu 2 t 三 蘭 三 缸 r 由引理2 2 4 和2 2 5 我們知道巧 1 4 e p u 1 4 e t 注意到有q 爿 以及p 爿 巧 巧 我們可以推出 因此 爿 去 尸一巧 三 p 1 4 妒 q 一 c 一雨p 3 t 迎 掣 丟 尸 t 2 2 c t p t 丟 而 2 2 e t 一3 2 e 罷 記b 8 正 厶川 正 為跏 的一個子批 2 采用與仃h 2 中一樣的方式加工和運(yùn)輸玩h z 之前的各個批中的工件 把 b b z b 8 中的工件分配給仃h 2 中b b h z 所在的機(jī)器 把j e 7 8 中的工件分配 給另一臺機(jī)器 仍然把b b u z 伊與伊中的工件一起運(yùn)送 記排序孑的目標(biāo)函數(shù)值為否 機(jī)器的完工時間為石兩 下面我們列出對問題p 2 一d k 1 v 1 c z l c m 缸的改進(jìn)算法m h 2 算法m h 2 1 運(yùn)行算法h 2 2 若b m 3 且c h 2 c m t 輸出c m 停止 一2 2 第二章工件占運(yùn)輸工具不同空間的帶運(yùn)輸排序問題 3 若c 日2 c m t 運(yùn)行算法1 3 輸出c 停止 4 若b h 2 3 且c 2 c m t 運(yùn)行算法a 輸出m i n c h 2 蠆 停止 在給出一些實例之前 我們先列出本節(jié)以下部分用到的一些記號 算法 日24b最優(yōu) 得到的捧序 o h 2仃盯 算法 一 工件被分成的批數(shù) b h b b s 2b 目標(biāo)函數(shù)值c h 2cc c 事 機(jī)器完工時間 c m c m c m c m 開始運(yùn)送第一批工件的時問 zzu 第二批工件的總加工時間 秒 可 口 另外 記由算法m h 2 得到的排序的目標(biāo)函數(shù)值為c m m p t 6 2 以及 p 的定義與上一節(jié)中的相同 把第一臺機(jī)器記為m 1 第二臺機(jī)器記為m 2 例2 3 1 我們考慮文獻(xiàn) 2 中的一個例子 令t 6 z 2 8 1 8 2 8 3 8 4 1 p l p 2 6 以及p 3 p 4 1 算法m h 2 首先運(yùn)行算法日2 得到 2 2 b 1 以 以 b 2 j 3 以 最 2 6 以及b 2 工件的加工和運(yùn) 輸安排如下 i p a f 4 nc m 2 c h 2 c m t 2 6 因為c 日2 c m t 算法 m h 2 進(jìn)入第3 步 運(yùn)行算法召 我們得到b 8 五 在排序孑中 工件的加 工和運(yùn)輸安排如下 m 1 m 2 一 因此c m 1 2 6 c c m t 1 3 6 一2 3 第二章工件占運(yùn)輸工具不同空間的帶運(yùn)輸排序問題 不難看出 c 1 2 6 弋c m 廠h 2 岳 i 而警一2 6 o 這是因為在 h 2 中 算法將島中的工件都由m 2 加工 而