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

摘要 摘要 排序問題是一類經典的組合優(yōu)化問題 從上世紀5 0 年代至今受到了許多行 業(yè)的從業(yè)人員與理論研究者的密切關注 本文主要研究排序問題在供應鏈管理 中的應用 眾所周知 供應鏈是由多個環(huán)節(jié)構成的 因此我們不能孤立地研究 排序問題 而要把排序問題與其它過程綜合考慮 全文共分四章 第一章主要介紹了供應鏈與排序問題的一些知識和概念 并且總結了近些 年來在綜合考慮排序與運輸的問題研究方面取得的一些成果 第二章研究工件占用運輸工具空間不同的綜合考慮運輸和排序的問題 在 這類問題中 工件在機器上完成加工后 需要由唯一的一輛運輸工具運送到相 應的顧客處 運輸工具的空間是有限的 每個工件占用運輸工具的空間各不相 同 目標函數是極小化最后一個到達顧客的工件的到達時間 當機器環(huán)境是單 臺機 所有工件的顧客相同時 我們設計了最壞情況界為3 2 e e 是任意正 常數 的漸近最優(yōu)算法 當機器環(huán)境是兩臺平行機 所有工件的顧客相同時 我們給出了了最壞情況界為5 3 的近似算法 第三章討論了允許在兩個加工工廠之間運送原材料或成品的排序問題 每 個工廠可以加工所有屬于本身的工件 也可以把一些工件運送到另一個工廠去 加工 這樣的運送需要一定的時間 若某個工廠需要另一家工廠加工一些工 件 根據工廠和工件的不同要求 有以下三種情形 1 在工件加工之前 原 材料不需要運送 工件完成加工后 需要被運送回有需求的工廠 2 在工件 加工之前 需要先運送原材料 工件完成加工后不需要被送回有需求的工廠 3 在工件加工之前 需要先運送原材料 工件完成加工后 需要被運送回 有需求的工廠 問題的目標函數都是極小化最后一個完工工件的完工時間 對 這三個問題 我們分別設計了最壞情況界為4 3 4 3 和3 2 的線性時間近似算 法 并且給出了動態(tài)規(guī)劃算法 第四章研究了帶承諾到貨時間的排序問題 在該問題中 企業(yè)根據顧客的 訂單來加工產品 并把完成的訂單交由第三方物流公司運送給顧客 每個訂單 包含不同的產品數量 而且必須在顧客要求的時問之前送達 訂單產生的運輸 費用與其中的產品數量以及運輸需要的時間有關 我們的目標是安排一個加工 訂單的持序并為每個訂單選擇運輸時間 使得所有訂單都能在承諾的最遲到貨 時間之前到達其顧客處 并且產生的總運輸費用盡量地少 我們給出了此問題 摘要 的最壞情況界為2 的近似算法 并且證明了這個界是緊的 關鍵詞 排序問題 供應鏈管理 近似算法 最壞情況界 動態(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 排序問題與供應鏈管理 排序 s c h e d u l i n g 問題是組合優(yōu)化中一類有著重要理論意義和廣泛實際背 景的問題 其實質是研究如何在滿足一定要求下 對需求完成任務的合理安排 以得到某種意義下的最優(yōu)結果 排序理論與理論計算機科學和離散組合數學存 在著密切的聯(lián)系 并廣泛應用到生產計劃調度 信息處理 物流管理 服務行 業(yè)等領域 近幾十年來 排序問題得到了運籌學 工程學 管理學和計算機科 學界的極大關注 并且隨著對經典問題研究的日趨深入 大量具有實際背景的 新問題不斷涌現 自上世紀5 0 年代人們開始研究排序問題至今 已有大量的排 序文獻發(fā)表在國內外的學術期刊上 可以這樣說 排序研究已經成為組合優(yōu)化 領域最活躍的分支之一 按照學術界多年來形成的慣例 我們把需要完成的任務稱為工件 j o b 把完成任務需要的資源稱為機器 m a c h i n e 我們希望找到一個可行的排序 f e a s i b l es c h e d u l e 使得某個給定的目標函數達到最小 大 這里可行一 般指在同一時刻 一臺機器至多加工一個工件 一個工件也只在一臺機器上加 工 并且該排序滿足問題特定的約束要求 描述一個排序問題可以用一種所謂 三參數表示法 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 分別 代表特定的機器環(huán)境 工件特征和最優(yōu)準則 它們是排序問題的三個組成部 分 機器環(huán)境用來描述機器的數量 不同機器之間的關系等與機器有關的 性質 常見的機器系統(tǒng)包括單臺機 s i n g l em a c h i n e 平行機 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 等 其中 平行機根據其性能的不同還可分為三類 同型平行機 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)中所有機器的功能 效率完全一樣 同 類平行機 u n i f o r mp a r a l l e lm a c h i n e s 系統(tǒng)中機器有各自不同的加工速度 但任意工件在不同機器上的加工時間有相同的比例關系 不同類平行機 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)中機器各不相同 工件在不同機器上的加 工時間比不全相同 在三參數表示法中 它們分別用p q j r 表示 工件特征一般包括工件的加工時間 通常也稱為工件長度 工件的釋放 第一章緒論 時間 工件相互之間的依賴關系 工件加工時是否允許中斷以及中斷恢復后再 加工時是否要受懲罰等等 根據排序者對工件信息的了解程度 又可將排序問 題分為離線 o f f l i n e 在線 o n l i n e 和半在線 s e m i o n l i n e 等 如果排序 者在排序開始前就已經知道工件的全部信息 例如工件數 每個工件的加工時 間等 則稱該問題是離線的 而如果工件的信息是隨著排序過程逐個釋放的 即只有在位于某個工件前的全部工件均被安排完畢后 排序者才能知道該工件 的有關信息 而且工件一旦被安排就不能改變 這樣的排序問題稱為在線的 但在實際問題中 大量的問題是介于兩者之間的 即我們或者知道該問題的一 些整體信息 或者知道后續(xù)工件的部分信息 我們把這樣的問題稱為是半在線 的 所謂最優(yōu)準則 通俗地講 也就是以什么為目標函數 如果記g 為某個排 序問題的可行排序中工件以的完工時間 則稱 戕 m a x q 為該排序的工 件最大完工時間 m a k e s p a n 它即為某種最優(yōu)準則下的目標函數 其最優(yōu)準 則為 找一個可行排序 使得工件的最大完工時間 旺在所有的可行排序中取 得最小值 即最小化目標函數 文獻中常見的其他目標函數還有 賦權 總完 工時間 最大延誤時間 最大誤工時間 最小誤工個數等 有關排序問題的綜 述 可參看 3 4 1 1 企業(yè)從原材料和零部件采購 運輸 加工制造 分銷直至最終送到顧客手 中的這一過程被看成是一個環(huán)環(huán)相扣的鏈條 這就是供應鏈 供應鏈的概念是 從擴大的生產 e x t e n d e dp r o d u c t i o n 概念發(fā)展來的 它將企業(yè)的生產活動進行 了前伸和后延 譬如日本豐田公司的精益協(xié)作方式就將供應商的活動視為生產 活動的有機組成部分而加以控制和協(xié)調 這就是向前延伸 后延是指將生產活 動延伸至產品的銷售和服務階段 因此 供應鏈就是通過計劃 獲得 存儲 分銷 服務等這樣一些活動而在顧客和供應商之間形成的一種銜接 從而使企 業(yè)能滿足內外部顧客的要求 供應鏈對上游的供應者 供應活動 中間的生 產者 制造活動 和運輸商 儲存活動 以及下游的消費者 分銷活動 同 樣重視 因此 供應鏈管理就是對整個供應鏈系統(tǒng)進行計劃 協(xié)調 操作 控制和優(yōu)化的各種活動和過程 其目標是要將顧客所需要的正確的產品 r i g h t p r o d u c t 能夠在正確的時間 r i g h tt i m e 按照正確的數量 r i g h tq u a n t i t y 正 確的質量 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 并使總成本最小 在世界經濟全球化的今天 供應鏈管理能力已經列為企業(yè)一類重要的戰(zhàn)略 一2 一 第一章緒論 競爭資源 尤其我國是個制造大國 從供應鏈管理的角度來考慮企業(yè)的經營活 動 形成這方面的核心能力 將對經濟發(fā)展變得越來越重要 產品的加工與運輸是供應鏈中的關鍵兩步 把這兩步工作有機結合 綜 合考慮將對節(jié)約成本 提高工作效率與客戶滿意度有明顯的促進作用 已 經有許多學者從整體構建供應鏈架構的角度對綜合考慮加工與運輸過程作 了大量研究 這方面的文獻綜述有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 另外 最近幾年來 有許多學者從具體的排序角度來綜合研究產品的加 工和運輸問題 目標是在考慮相關的效益 費用和顧客滿意度的基礎上 找到 關于加工與運輸產品的最優(yōu)排序 這類問題是對研究整體供應鏈構建的深入 這類問題根據運輸之后是否有后續(xù)加工可以分為兩類 一類是成品的運輸 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 也就是 把產品運送到相應的顧客處 排序任務就結束了 另一類是原材料或半成品 的運輸 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 也 就是在運輸之后還需要加工工件 在關于i p o d s 的文獻中 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 等人研究了綜合考慮運輸費用 與顧客滿意程度的問題 h e r r m a n n 和l e e 2 2 c h e n g 等 9 j i 等 2 4 考慮了 總庫存成本與總運輸費用相結合的問題 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 研究了運輸工具數量有 限的情形下最大化客戶滿意度的問題 c h e n 和p u n d o o r 6 考慮了工件帶約束 的條件下 如何最小化運輸費用 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 則研究了在保證運輸及時性的基礎上 最大化總效益的問題 q i 4 3 和 4 4 研究的問題中 一個工廠可以把顧客要求的工件交由另一家工 廠加工 在不同的工廠之間需要時間來運送工件 c h a n g 和l e e 2 p a n 等 4 0 研究了工件占用運輸工具空間大小不同的問題 目標是最大化顧客的滿 意度 關于i p i d s 類問題的文獻有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 下面我們對以上提到的部分研究作更具體的介紹 還有一些文獻研究的問 題在后面的章節(jié)中會涉及到 文獻 8 研究了下面的問題 工件在機器上完成加 工后 要由開始位于機器處的容量限制相同的運輸工具運送到各自的顧客處 在這里 有足夠多的運輸工具可以在機器與顧客間以及不同的顧客間運送工 一3 一 第一章緒論 件 所需的時間各不相同 運輸工具每運送一趟 都會產生與該趟運送路線相 關的運輸費用 問題的目標是極小化最后一個到達顧客的工件的到達時間與總 運輸費用的凸和或者所有工件到達相應顧客的時間之和與總運輸費用的凸和 針對機器環(huán)境 顧客的數目以及目標函數不同的情形 作者討論了計算復雜 性 給出了最優(yōu)算法或者近似算法 并且進行了數值模擬 在文獻 1 9 研究的 問題中 工件在供應商處完成第一步加工后 被送到工廠處進行第二步加工 然后被運送到相應的顧客處 只有一個供應商 有多個工廠 機器加工環(huán)境都 是單臺機器 運輸工具的數目與容量沒有限制 目標是極小化總完工時間 最 大延誤時間或者 加權 總誤工工件個數 作者討論了問題的計算復雜性 給 出了動態(tài)規(guī)劃算法 文獻 2 4 的問題中 工件在單臺機上完成加工后 被分批 送往顧客處 運輸工具的數目與容量沒有限制 每運送一批工件就會產生一筆 運輸費用 工件完工時間定義為在機器上的完工時間 目標是極小化賦權工件 完工時間之和與總運輸費用之和 作者討論了問題的計算復雜性 對一些特殊 情形給出了動態(tài)規(guī)劃算法或多項式時間最優(yōu)算法 文獻 3 0 研究了兩類帶運輸 的排序問題 第一類問題 t y p e1 中 機器系統(tǒng)是流水作業(yè) 所有工件必須 按相同序從在第一臺機器到最后一臺機器上完成每道工序 工件從一臺機器到 下一臺機器的運輸工作由有限個有容量限制 開始時在第一臺機器處的運輸工 具來完成 不同的工件可以在同一批被運送 而運輸工具在不同的機器間運送 需要的時間各不相同 目標是極小化在最后一臺機器上的最大工件完工時間 當運輸工具數目 運輸工具容量以及工件的一些性質各不相同時 作者討論了 問題的計算復雜性 給出了動態(tài)規(guī)劃算法 在第二類問題 t y p c2 中 工件 在機器上完成加工后 需要由有限個有容量限制 開始時在機器處的運輸工具 運送到同一個顧客處 運輸工具從機器到顧客與從顧客回到機器的時間不同 目標是極小化最后一個到達顧客的工件的到達時間 當機器環(huán)境 運輸工具數 目 運輸工具容量各不相同時 作者討論了問題的計算復雜性 給出了動態(tài)規(guī) 劃算法 文獻 3 4 研究了原材料與完工工件都需要運輸的問題 在開工之初 僅有的一個有容量限制的運輸工具要把未加工的工件從倉庫運送到一臺單臺機 上去加工 這輛運輸工具還要把完成加工的工件運送回這個倉庫 運輸工具從 倉庫到機器與從機器回到倉庫的容量限制不同 而所需時間相同 問題的目標 是極小化最后一個到達倉庫的完工工件的到達時間 作者討論了問題的計算復 雜性 提出了一個多項式時間近似算法 并且進行了數值模擬 文獻 3 7 研究 了如下的帶運輸排序問題 工件在單臺機上完成加工后 需要由僅有的一臺有 一4 一 第一章緒論 容量限制的運輸工具運送到各自的顧客處 機器與不同的顧客之間的運輸時間 以及不同的顧客間的運輸時間各不相同 工件的完工時間定義為其到達相應顧 客的時間 問題的目標是極小化工件總完工時間 進一步的 作者還討論了運 輸工具在顧客內部不能運輸 即同一批的工件只能屬于同一個顧客的情形 作 者討論了問題的計算復雜性 給出了問題的動態(tài)規(guī)劃算法 并對一些特殊情形 給出了最優(yōu)算法 文獻 3 9 考慮了帶工件釋放時間的問題 在每個工件的釋放 時間之前 不能加工該工件 工件在單臺機上完成加工后 要由唯一的一個運 輸工具送到同一顧客處 每個工件占用運輸工具的空間相同 目標是極小化最 后一個到達顧客的工件的到達時間 當工件的加工是可中斷時 問題是多項式 時間可解的 當工件加工不可中斷時 作者提出了一個近似算法 分析了最壞 情況界 文獻 4 0 中 工件在兩臺流水作業(yè)機器上完成加工后 由僅有的一臺 有容量限制的運輸工具送到同一個顧客處 每個工件占用運輸工具空間大小不 同 工件的完工時間定義為到達顧客的時間 目標是極小化工件總完工時間或 最大工件完工時間 作者討論了問題的計算復雜性 對一些問題給出了多項式 時間的近似算法 文獻 4 3 研究了這樣一類問題 一個加工工廠可以自己加 工接收的訂單中的工件 也可以把一些工件交由另一個工廠加工 并把完成的 工件送回原來的工廠 針對目的地相同的工件只可以一批運送或者一個一個地 運送以及目標函數不同的情形 作者給出了最優(yōu)算法或者動態(tài)規(guī)劃算法 文獻 5 0 研究了帶機器維護時段的問題 機器并不總是可運作的 在某個需要維護 的時間段內不能加工任何工件 工件在機器上完成加工后 需要由唯一的有容 量限制的運輸工具送到同一個顧客處 運輸工具在機器與顧客間往返的時間相 同 問題的目標是極小化最后一個到達顧客的工件的到達時間 對機器環(huán)境是 單臺機器和兩臺平行機的情形 作者分別給出了問題的多項式時間最優(yōu)算法或 者近似算法 1 2 算法和計算復雜性 定義1 2 1 算法是指一步步求解問題的通用程序 它是解決問題的程序步驟的 一個清晰描述 確定性算法從前一步到后一步的運行由當前狀態(tài)唯一確定 定義1 2 2 對于一個排序問題7 r 如果給定任意一個實例 算法a 總能找到 一個可行解仃 并且仃的目標值總等于最優(yōu)解值 則稱a 為最優(yōu)算法 o p t i m a l a l g o r i t h m 一5 一 第一章緒論 將實例通過某種規(guī)則編碼后輸入計算機所用的字節(jié)數稱為該實例的的輸入 長度 通常 算法所用的時間是指算法中所含的加 減 乘 除 比較等基本 運算次數 而算法所用的時間與實例的輸入長度有關 定義1 2 3 算法的時間復雜性是指關于實例輸入長度n 的函數 廠 幾 用來表示 算法的時間需求 對每一個可能的輸入長度 它是指在最壞情況下該算法解此 輸入長度的實例時所需時間 基本運算步數 即對于輸入長度相同的所有實 例 把算法對這些實例的最壞情況作為時間復雜性的度量 如果存在一個多項式函數p 佗 使得算法的時間復雜性為d p 釓 那么 稱該算法為多項式時間算法 否則稱為指數時間算法 還有一類算法叫偽多項 式時間算法 它的時間復雜性是關于實例輸入長度n 和實例中最大數的二元多 項式函數 在二進制編碼下 偽多項式時間算法并不是多項式時間算法 而是 指數時間算法 由此出發(fā) 可以導出計算復雜性理論的一系列重要概念和結論 1 3 1 計算復雜性理論興起于二十世紀六十年代 和算法的設計與分析密切相 關 通過幾十年來人們在計算復雜性方面的研究 現今p p 的猜想己被基 本接受 在此前提下 所謂的n p h a r d 問題就不可能在多項式時間內找到最 優(yōu)解 同時 尸一h a r d 問題中有一類更難的問題 稱為強 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)解的尋找 而把研究的重點轉向尋找能在較短時間 多項 式時間 內得到接近于最優(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 是經典平行機排序問題的近似算法 l s 算法將工件按序安排在能使其最早 完工的機器上加工 三p t 算法先把所有工件按加工時間的非增序排列 然后依 次將它們安排在能使其最早完工的機器上加工 我們衡量近似算法的優(yōu)劣可從兩個方面來看 一是算法的時間復雜性 二 是算法得到的解值與最優(yōu)解值的接近程度 一6 一 第一章緒論 定義1 2 5 如果7 r 是一個極小 大 化i j 題 是任意實例 設a 是丌的一個 近似算法 用 j 和c 分別表示算法a 解實例 所得的目標函數值和實 例j 的最優(yōu)目標函數值 記肌 黜 以 拱 則近似算法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 進一步的 如果 a 的時間復雜性是關于輸入長度以及 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 對一個強 p 一難的問題7 r 若存在兩個變量的多項式g 使得對于任何7 r 的實例 有 d p 丁 s f 試問應該如何 把物品放到箱子中 使得各個箱子中所裝物品的尺寸總和不超過c 并且所用的 箱子數盡可能的少 關于裝箱問題 已經能夠證明 除非p p 否則不存在最壞情況界 s j 試問應該選取哪 些物品放入背包中 使得背包中所裝物品的尺寸總和不超過c 并且背包中物品 的價值總和盡可能的大 下面我們列出背包問題的 個近似算法 其最壞情況界為2 2 6 1 算法e x t g r e e d y 1 j 1 s 0 s 表示當前背包中物品序g 尺寸之和 穢 0 秒表示當前背包中物品的價值之和 2 若歹 禮 s s 3 c 則巧 1 把乃 放入背包中 否則 z j 0 一l o 第一章緒論 3 若j n 輸出m a x 器 巧 m 啦 吻 停止 否則 j 歹 1 進入第2 步 l a w l e r 2 8 給出了背包問題的f 刀a s 其時間復雜性為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 其時間復雜性是 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 它的時間計算復雜性為o n 2 算法b a s i c f p t a s 1 運行算法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 證明 每一批中的工件對應的物品的集合都構成背包問題實例的可行解 而 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 只運行算法h 1 因此c m m c 1 并且根 據前面的假設我們只需要考慮c 1 p 1 b l t 的情形 注意到此時有1 1 t 若擴 1 即所有工件尺寸之和不超過z 則b 1 1 以及c 1 c p 丁 因此 我們下面只考慮b 2 的情形 若b l b 由引理2 2 3 可知 萬c 1 籌 嚳 1 爭吉 3 擴的情形 情形l c 亂 6 t 由引理2 2 3 我們可知 u 6 事t p 十丁 即p u b 一1 t 注意到有 p l 島 冬r 因此bs 善 蘭 業(yè) 進一步的我們可以得到 1 7 一 第二章工件占運輸工具不同空間的帶運輸排序問題 c 1 一 p 1 b l 丁 半 6 1 t c u 6 卓t t 正 滬t 1 亂 擴t 晴一1 t b l 锃 滬t 11 6 2 1 t j 6 1 b l u 6 t 11b 2 1 擴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 這與假設b l 3 矛盾 若擴 3 由式 2 2 可知b l 警 礦 因此b 1 4 結合式 2 i 可以得到象 類似的 若b 4 則b 1 5 并且籍 若b 5 由式 2 2 和引理 1 4 2 可知b l 6 因此孓 若擴 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 中我們已經證明了似c a 擴 因此有b 2 由引理1 4 1 可以得到5 2 幸2 蠆7 也就是 b 2 3 進一步的 如果b 2 b 與引理2 2 6 中類似的證明 我們可以得到 岳 i 因此 下面我們假設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 第二章工件占運輸工具不同空間的帶運輸排序問題 因此 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 中一樣的方式加工和運輸玩h z 之前的各個批中的工件 把 b b z b 8 中的工件分配給仃h 2 中b b h z 所在的機器 把j e 7 8 中的工件分配 給另一臺機器 仍然把b b u z 伊與伊中的工件一起運送 記排序孑的目標函數值為否 機器的完工時間為石兩 下面我們列出對問題p 2 一d k 1 v 1 c z l c m 缸的改進算法m h 2 算法m h 2 1 運行算法h 2 2 若b m 3 且c h 2 c m t 輸出c m 停止 一2 2 第二章工件占運輸工具不同空間的帶運輸排序問題 3 若c 日2 c m t 運行算法1 3 輸出c 停止 4 若b h 2 3 且c 2 c m t 運行算法a 輸出m i n c h 2 蠆 停止 在給出一些實例之前 我們先列出本節(jié)以下部分用到的一些記號 算法 日24b最優(yōu) 得到的捧序 o h 2仃盯 算法 一 工件被分成的批數 b h b b s 2b 目標函數值c h 2cc c 事 機器完工時間 c m c m c m c m 開始運送第一批工件的時問 zzu 第二批工件的總加工時間 秒 可 口 另外 記由算法m h 2 得到的排序的目標函數值為c m m p t 6 2 以及 p 的定義與上一節(jié)中的相同 把第一臺機器記為m 1 第二臺機器記為m 2 例2 3 1 我們考慮文獻 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 首先運行算法日2 得到 2 2 b 1 以 以 b 2 j 3 以 最 2 6 以及b 2 工件的加工和運 輸安排如下 i p a f 4 nc m 2 c h 2 c m t 2 6 因為c 日2 c m t 算法 m h 2 進入第3 步 運行算法召 我們得到b 8 五 在排序孑中 工件的加 工和運輸安排如下 m 1 m 2 一 因此c m 1 2 6 c c m t 1 3 6 一2 3 第二章工件占運輸工具不同空間的帶運輸排序問題 不難看出 c 1 2 6 弋c m 廠h 2 岳 i 而警一2 6 o 這是因為在 h 2 中 算法將島中的工件都由m 2 加工 而