725 空氣濾清器連接板沖孔、沖槽、落料復(fù)合模設(shè)計(有cad圖+文獻翻譯)
725 空氣濾清器連接板沖孔、沖槽、落料復(fù)合模設(shè)計(有cad圖+文獻翻譯),725,空氣濾清器連接板沖孔、沖槽、落料復(fù)合模設(shè)計(有cad圖+文獻翻譯),空氣濾清器,連接,沖孔,復(fù)合,設(shè)計,cad,文獻,翻譯
離散應(yīng)用數(shù)學(xué)離散應(yīng)用數(shù)學(xué)98(1999) 121-130最小化模式下料問題科林麥克迪爾米德統(tǒng)計部門,牛津大學(xué),南公園路一號,牛津大學(xué)OX1 3TG,英國收稿于1997年10月21日,接受于1999年2月8日摘 要在切割存量模式最小化問題,我們希望,以滿足盡可能少巨型卷軸卷軸切割各種客戶的需求,并進一步減少使用不同的切削模式的數(shù)量。我們專注于特殊情況,其中任何兩個客戶卷軸到一個巨型合適,但沒有三事:這個案件的興趣,部分是因為它是最簡單的情況是不平凡的,部分是因為它在實踐中可能會出現(xiàn)當一個嘗試一個解決方案,以改善迭代。我們發(fā)現(xiàn),該模式最小化問題是強NP難的,即使在這種特殊情況下,當inding最低廢液的基本問題是微不足道的。我們的分析主要論點集中在均衡的子集,并提出了涉及亞均衡的啟發(fā)式搜索方法的方法。 1999 Elsevier科學(xué)BV公司保留所有權(quán)利。關(guān)鍵詞:下料,切割模式;分區(qū); NP難;動態(tài)規(guī)劃1 簡介有些材料如紙,可制造性巨無霸卷,這是后來成為更窄輥切,以滿足客戶的需求。為了減少浪費,應(yīng)選擇切割方式,以盡可能少的使用客機(見4,7,8)。因此,下料問題已基本輸入一個正整數(shù)j,不同的正整數(shù)r1的,., Rn和D1的,.,正整數(shù)的DN,以及需要的任務(wù)是,以盡可能客機的寬度j的數(shù)為滿足客戶的卷筒寬度里迪需求對每個i = 1 ,.,,全這是其中的經(jīng)典OR問題之一。它包含了強烈的NP -完全問題三分區(qū):因此即使巨幅大小J外面有一層氮、多項式滿足每個客戶的卷軸大小國際扶輪扶輪J / 4 J / 2 -看6,p。224。因此我們不能指望在合理時間內(nèi)總是能找到最優(yōu)解等問題的。每一次不同的客戶卷軸模式是被削減,在切割機的刀需要重新設(shè)置。甲由Cn中Goulimis并在第29屆歐洲與產(chǎn)業(yè)調(diào)查研究組1996年3月有關(guān)如何找到辦法來解決上述料問題,這進一步減少了用于切割不同模式的數(shù)量問題 - 見1,2,9 。一般情況下這當然是變得越來越難。為了探討擴展問題雪上加霜,我們在這里考慮一個特殊的案件中,盡量減少對客機(減少廢物),數(shù)量基本問題是微不足道的。最小化格局:輸入:D1的正整數(shù);的DN。任務(wù):在切割存量問題,即要求I型迪卷軸是,任何兩個卷軸到一個巨型做它,但沒有三,工業(yè)最低廢液,進一步減少了使用不同模式的數(shù)量。這種特殊的情況是非常有限的部分原因是因為它似乎是最簡單的情況是完全不平凡的,部分是因為它可能會在實踐中產(chǎn)生的,當一個一個解決方案試圖改善迭代的興趣。例如,如果對目前使用的一些模式集合同意的大型卷軸和difer小卷軸而已,它在任何兩個小卷軸左邊的大型卷軸的寬度,那么當我們試圖重新分配小我們面臨的正是這種卷軸的特殊情況16。我們調(diào)查模式是否最小化問題還很難在這個特殊的情況,并簡要考慮辦法找到好的解決辦法。很明顯,所需要的客機數(shù)量最少的是我的di / 2,圓了總需求的一半,它是微不足道的一個相應(yīng)的最低工業(yè)廢液。但是,它是多么容易躋身工業(yè)廢物最小的解決方案,一個能最大限度地降低使用的模式的數(shù)量,?對于這個問題的變體在沒有三個客戶卷軸它變成珍寶,但也有一些對可能不是,它是在1表明,問題是強NP -難問題。下面的定理加強這種不利的結(jié)果。定理1:這個問題最小化模式是強NP -難問題。對上述問題的理解關(guān)鍵是一個平衡的一個子集的概念。給定一個家庭d =(d1,dn)的非負整數(shù),表示x(d)的在任何解決方案中使用最少的廢物模式的最小數(shù)量。還有,另一個平衡的非空的子集 1,n ,如果它能夠被分割成兩個集合A和B,tA di = 5ieB di。因此,如果 di = 0然后單獨設(shè)置i是平衡的。讓v(d)是最大的數(shù)字的平衡子集兩兩相互無關(guān)的。引理1:如果J2i di是偶數(shù),然后x(d)= n - v(d)。如果i di 是奇數(shù),令x(d) = i(d),其中d1從D獲得通過增加一個額外的統(tǒng)籌的DN +1 = 1。我們將在下一節(jié)中證明這個引理。當與一個模式最小化所面臨的問題,我們領(lǐng)導(dǎo)的定理1和引理1以上考慮啟發(fā)式方法inding亞群平衡的好包裝。不幸的是NP -完全甚至是測試,如果一個家庭中的正整數(shù)格a1,.,an有一個平衡的一個子集。這就是問題稱為弱分區(qū)是大衛(wèi)約翰遜的NP完全列10,其中四分之三的NP完全獨立的證據(jù)被引用,最早在13。 我們希望工業(yè)亞群的平衡好包裝,但我們知道這是很難工業(yè)最佳包裝,的確是很難平衡的工業(yè)任何一個子集。自然啟發(fā)式的方法是反復(fù)尋找和刪除一個平衡的一個子集,最好是小的。其中尋求一個平衡的一個子集的方法是使用diferencing,這里我們再次取代其diference絕對值兩個數(shù)字 - 參見5,12,15,17。這種方法目前正在調(diào)查中最小的格局16中。另一種方法是使用一個還算快速算法,保證工業(yè)均衡的子集或子集的最小平衡:我們會看到,我們可以使用一個簡單的動態(tài)規(guī)劃方法來測試,如果有一個平衡的子集,均衡和IND一個最小的子集如果有一個,在偽多項式時間。最小的模式啟發(fā)式方法更普遍的情況下在降低庫存的問題被認為是1,2,9,11。 該論文的其余部分計劃如下。在下一節(jié)中,我們建立的模式之間的平衡亞群的數(shù)量和包裝的關(guān)系。接下來,我們證明我們的主要結(jié)果,這個問題最小化模式是強NP -難問題。在此之后,我們認為briely如何尋找平衡的子集,并inally我們做一些總結(jié)性發(fā)言。2 模式,學(xué)位和平衡套在這一節(jié)中,我們將證明引理1,其中涉及的圖案編號,包亞群平衡英格斯。最小化的問題可以改寫格局在圖上。一個模式,涉及卷軸I型和J型卷筒之間將對應(yīng)頂點頂點vi和vj的邊緣。我們將讓我們的圖,包含在任何頂點循環(huán)但不包含多個邊緣。給定一個圖G =(V,E)對集V = v1,.,v2的頂點,連同非負整數(shù)重量的邊緣E,我們的家庭W時,頂點加權(quán)第六度過度的重量與我們六邊事件的總和與任何循環(huán),計數(shù)兩次。給定一個向量d =(d1. dn)的正整數(shù),我們呼吁d如果每個頂點Vi有兩人加權(quán)程度地代表公克WA網(wǎng)絡(luò)。考慮以下問題。學(xué)位:輸入:積極intergers d1.甚至與dn。任務(wù):工業(yè)用盡可能少的邊緣一個代表網(wǎng)絡(luò)。給定一個d組=(d1. dn)的正整數(shù),甚至與我二,有一個度之間的解決方案和模式MINIMI SATION這些自然的對應(yīng),特別是最小的邊數(shù)前者的可能等于 (d)項。引理1:假設(shè)di是偶數(shù)。設(shè)G w是任何代表工作,并考慮為G的K個節(jié)點集K表的組成部分。這當然必須有至少k - 1條邊,如果它有這個數(shù)目,因此是對K樹,那么三分之二的頂點著色表明,K是平衡的。因此,在G的邊數(shù)至少有n減去若干套組成部分的平衡。因此(D)Jsn - 的v(d)。為了證明反向不等式,考慮任何V1.Vn(Ki:i I),其中一個最不均衡。我們將證明,有代表怨恨網(wǎng)絡(luò)G,W使得圖G有組件(Gi:I i)如已設(shè)立文基頂點,這些組件是這樣,如果文是平衡的,然后是一樹基如果沒有則Gi是一加一樹循環(huán)。這將完成該引理的證明??紤]平衡集K,其中分區(qū)A U S使得YieA= igBdi國際能源署。我們必須表明,有對T邊緣E對K和非負權(quán)重,我們一樹T,使得對于每一個節(jié)點v K時,對事件邊的權(quán)重之和等于的dv(其中雙回路數(shù))。我們使用 K|表感應(yīng)。如果A或B是空的,結(jié)果是微不足道的,因為我們必須為每個V光那假設(shè)A和B都是非空的dv = 0。選擇任何一個和b阿B和不失一般性假設(shè)大分貝。減少大的分貝?,F(xiàn)在K表 B的是平衡的,我們可以感應(yīng)工業(yè)適當?shù)募訖?quán)樹。然后加入與體重分貝邊緣抗體。最后,考慮一個集K這是不均衡的,但就是這樣,相應(yīng)的要求和是偶數(shù)。如上所述,我們可以隨時更換了使用成本的一個邊緣的diference兩個要求。因此,我們能滿足所有,但一用邊緣形成一個對K樹需求,然后添加一個循環(huán)結(jié)束的組成部分。3 最小化模式是強NP -難在本節(jié)中,我們證明定理1,這個問題最小化模式是強NP -難問題??偨Y(jié)三(或舒爾三)是三,這樣的兩個之和等于第三個不同的整數(shù)集合。下面的問題可以得到更充分的描述,總結(jié)成獨特的整數(shù)分區(qū)的三倍作為。總結(jié)三元輸入:S1.S3n不同的正整數(shù)。問:能否輸入三元分割成總結(jié)?這個問題類似于數(shù)值匹配與目標款項,加里和Johnson 6,第224,但額外的(令人驚訝的麻煩),條件是涉及的人數(shù)必須是不同的。引理2:問題總結(jié)三元是強NP -完全的。本節(jié)的大部分將用于證明上述引理,但首先,讓我們看到,它會產(chǎn)生定理1。證明定理1(假設(shè)引理2):我們給一個總結(jié),學(xué)位strightforward三倍,多項式時間減少。考慮一個總結(jié)三元上述實例。以 =作為學(xué)位實例(2s1 .2s3n)。由于硅是不同的正整數(shù),也有規(guī)模不小于3套平衡。因此,(dHence由引理1,第十章x(d) 2n與x(d)為2n =當且僅如果s1 .s3n可分為總結(jié)三倍現(xiàn)在考慮的問題總結(jié)三倍,這顯然是在NP。我們將證明它是強NP -通過給從NP -完全問題限制X3C減少完成,下述,總結(jié)每個三元組在O(n3)的。限制X3C:輸入:一組第三季度的X元素和一個三元組集合C在十,這樣每個X的 元素完全相同3三元載。問:可以劃分為三元X是在C?引理3: 限制X3C問題是NP完全的。證明 據(jù)了解,這個問題是NP完全問題,如果每個元素被限制在最多3三倍,而不是正好3 - 見加里和Johnson 6,第221。這是很容易對注冊整潔的實例X,使每個元素恰好是3的三倍。很明顯,我們能堅持,每個元素在2或3的三倍。我們可以在分區(qū)中的元素正好兩個三元組分為三個區(qū)塊的大小。對于每個塊x,Y,Z,添加新的元素三個x,y,z及x,y,z,x,y,z,x1, y,z,x1,y,z。調(diào)用新的實例X,C的。顯然,每個X的元素是完全相同三三元在C;和X可以被劃分在C到三倍,如果有僅當X可以被劃分為三元在C。引理2: 考慮一個實例X,C的限制X3C,其中| X = = CI=3q。季度全令Y = X x 1 ,., 7。我們將建設(shè)一個擴大在Y D的收集,包含三元使得X可分為三元在C分區(qū),當且僅當y可劃分為D中三元,接著我們將構(gòu)造一個實例(秒(y)的:你們的Y總結(jié)三倍,其中每個尺寸S(y)的異O(n2),),這樣的總結(jié)恰恰三倍對應(yīng)的三元組在D形成一個二分圖G =(C,X,E)的頂點C部及X和頂點窄隙室和X GX的相鄰(即邊發(fā)射GE)的正是由于當x 噸G中的每個頂點度是三,我們可以在多項式時間內(nèi)找到一個合適的3邊染色:E - 1,2,3?,F(xiàn)在,我們每個元素x GX的分割成三份(x,1),(x,2)和(x,3)。鑒于一特里普爾T = x,y,z氣相色譜,令T是三重T= (x,KTx),(y,(Ty),(z,(Tz)觀察,在三T的分子具有不同的第一坐標(X),以及獨特的第二個坐標(必須是1,2,3),而C=(T:TG)分區(qū)集X x 1,2,3。接著,每個X光霞,讓Fx的是集合組成的四個三元(x,1),(x,4),(x,5),(x,3),(x,4), (x,5),(x,2),(x,6),(x,7)和(x,3),(x,6),(x,7)。設(shè)D是由碳的收集與所有的X 十,因此D包含在集合在一起Fx的三元| | +4 | x |= 5n的三倍。如果某些子集合的D是Y的分區(qū),然后對每個x G X的時候,恰恰的要素之一(x,1),(x,2),(x,3)不包括由三元組在D東經(jīng)外匯,因此必須由在D東經(jīng)企業(yè)所得稅三倍以下方便,這包括X可以被劃分在C到三倍,當且僅當y劃分可分為三元在D這樣就完成了施工紅外警戒的一部分。下一步,我們將看到如何分配尺寸S(y)對每個元素y戈瑞以便在Y元素的總結(jié)三元正是在D的三元組,我們將使用一個界定差不多的K -明智的獨立隨機變量的家庭小樣本空間。設(shè)1 = 3 log2 n+10,令t = 2n1,令k = 91,讓8 = 2。有Q的一個子集0,1,大小2(1 + 0(1)K的:如果一個點的合作=(ro1 .,cot)是隨機挑選的統(tǒng)一Q,則,., cot)的是8距離的K -明智的獨立,見3。今后這類一套Q可以(明確)在多項式時間建成北界。給定一個點合作賓館,對每個i = 1 ,., 2n個,讓$ = $(co)是非負,teger二進制擴展coy。當一個點co=(co1,., cot)的采收有限公司。從Q隨機均勻,然后S1.,.S2n是隨機變量,以價值觀在0,1 ,., N - 1個,其中N = 2Z,它們具有以下屬性。對于任何集成電路與IC1 .2n 與0| 11 69,和任何集合0,1 ,., N - 我們:I I)G E) - |E| /NI/| 61 / 2:現(xiàn)在,我們可以定義元素的大小為我們總結(jié)三元原審(年)。為清楚起見,我們將寫的(X,1),而不是秒(X,1)等。給定一個采樣點的合作賓館,對每個i = 1 ,., n我們設(shè)S(xi,1)= 2S2i - 1(co)+ 2N個和S(xi,2)= 2S2i(m)+ 2N。設(shè)x G X,假設(shè)使(x,3)是在三T Cwhere T公司還包含(X,1)和(x ,2)。然后我們設(shè)S(x,3)=s(x,1)+ s(x,2)( 4N)。這個定義的(x,i)為每個X G X和iG1,2,3?,F(xiàn)在,對于每個x G X的,設(shè)S(x,4)=(s(x,1)+s(x,3)/ 2s(x,5)=(- S的(x,1)+ S(x),1)/ 2s(x,6)=(d(x,2)+s(x,3)/ 2和S(x,7)=(- S(x,2) +s(x,3)/ 2。現(xiàn)在我們已經(jīng)定義了一個正整數(shù)的大小為每個Y戈瑞的(y)和D中的每個三是始終總結(jié)。讓BCQ公司是壞的情形,或者因為你們的價值之(y)的失敗是不同的,或一些較D組其他三是總結(jié)。我們將表明,P(B)“1。它會跟有一個采樣點的合作 Q b,和我們能找到這樣一個由窮舉搜索多項式時間點。這將完成該引理的證明。為了證明P(B)“1,它足以讓我們假設(shè)隨機變量的S1,S2n正是9明智的每個獨立的均勻分布于0,1,N - 1,然后,以證明P(B)“1 / 2。觀察,從s的定義(y)的,為每個Y有一個向量a(y)的e - 1,0,1,2 2n個,大小為支持最多3,使得s(y)的,保險業(yè)監(jiān)督(y)的;是一個常數(shù)(即不依賴于合作)。讓y1和y2是Y的不同元素,讓a=a(y1)a(y2)。這是很容易看到,a是一個非零整數(shù)大小為支持最多6個載體,并有一個常數(shù)c使得s(y1)=s(y2)的當且僅當易=角但是,這最后事件的概率至多為1 /全因此,概率為你們的價值之(y)的并不都是最明顯的是在 2N6同樣,對于我們可能會說不需要的三倍。讓日y1,y2和y3 的是不同的元素,形成一個不考慮在D事件的s(y1)+s(y2)=s(y3)。設(shè)a =a(y1)+a(y2)=s(y3)。然后,一個有規(guī)模的支持最多9,并有一個常數(shù)c使得s(y1)+s(y2)=s(y3)當且僅當易=角我們斷言向量a是非零。然后,它將按照三倍的概率并不一定是在D總結(jié)至多()3 6 ;,因此P(B)6(72i0nfn)“1 / 2,根據(jù)需要。它仍然只是建立上述索賠。對于每一個元素y =(x i)e ,讓n1(y)= x和7i2(y)= i,記Yia(y)i的由c(y)。假設(shè)a = 0時:我們必須獲得矛盾。請注意:第一,如果7i2(y)= 3,那么r(y)= 4。因此,既不氮氣,也不7i2(y2)的可以等于3,因為我們不是讓Yiai“4 - ff(y3) 0?,F(xiàn)在假設(shè)氮氣(y2)的 1,2,這是ff(y1)= 2。那么C(Y2)的必須是1或2。我們認為這兩種情況。(一) 首先假設(shè)的c(y2)= 1。然后,cr(y3)= 3?,F(xiàn)在a(y1的只有一個非零統(tǒng)籌2,a(y2)的有-1,1,1和a(y3)有1,1,1。然后的n1(y1)= n1(y2)= n1 (y2)和特里普爾T =(y1 y2 y3)isinD,矛盾。(二) 現(xiàn)在假設(shè)r(y2)= 2。然后,r(y2)= 4?,F(xiàn)在a(y1有一個2,(y2)的有1個2和a(y3)有2,2。同樣的三重性T D,一個矛盾。現(xiàn)在我們已經(jīng)表明,n2(y1)的e 1,2,3,同樣y2。因此,這兩個n2(y1)和7i2(y2)在4,5,6,7。因此ff(y1)和cr(y2)的are1or3,cr(y2)is2或4。首先假設(shè)ff(y1)= C(y2)= 1,所以C(y3)= 2。然后兩個a(y1)和a(y2)的有非零統(tǒng)籌-1 1 1和a(y3)有2。但接下來a(y1)和a(y2)的必須具有相同的支持。接下去的n1(y1)= n1(y2),這是不可能的。不失一般性,我們現(xiàn)在可以假設(shè)ff(y1)= 1和“r(y2)= 3。然后,r(y1)= 4,和a(y1)的有非零協(xié)調(diào)-1,1,1,a(y1)有1,1,1,和a(y3)有2,2。然后,我們再一次工業(yè)a(y1)和a(y2)的必須具有相同的支持,等的n1(y1)= n1(y2)= 1(y3)。但現(xiàn)在,三T是在D,一對矛盾。4 尋找平衡的子集這是一個NP完全測試,如果一個家庭中格A1 ,., 可持續(xù)的競爭整數(shù)的POS機一有一個平衡的一個子集,但我們?nèi)匀豢赡芟M麨閬喨浩胶獾母窬种兴阉鞯阶钚∧承﹩l(fā)式方法。在本節(jié)中,我們看到,一個簡單的基于動態(tài)規(guī)劃的方法就能解決的偽多項式時間等問題。紅外警戒看到我們?nèi)绾螠y試,如果有一個平衡的一個子集,如果這樣工業(yè)之一(另外兩個最小相應(yīng)的總和)在O( 5 iai)的步驟。之后,我們將看到如何找到一個平衡的最小的子集,在O(n2J iai)的步驟。這不是明顯的,這些算法將在一個最小化的啟發(fā)式方法具有更好的模式。讓s0=5 0 / 2。對于每個S = 0,1 ,., S0的,而且每個j = 0,1 ,., n,設(shè)集f(s,j)為T。如果有一個相應(yīng)和S子集,讓集f(s,j)的平等F,否則。則f(0,j)的每個j = T為= 0,1 ,., n,且集F(S,0)=每次的F = 1 ,., S0的。我們可以計算所有的值集f(0,j)在反過來,在O(1)每個值的步驟,如下所示。為s = 1 ,.,對于j = 1 .n s0f(s,j) f(s,j - 1)V f(s - aj,j - 1)。(如果s 0,我們解釋集f(s,j)a s F)如果在上述復(fù)發(fā),這是從來沒有的情況是,在右邊兩個術(shù)語是T,那么就沒有平衡的一個子集。但假設(shè)這種情況確實存在,而且我們第一次見面是在s0和j0。那么有兩種不同的亞群的相應(yīng)和 A和B(一j0和一個不包含)。此外A和B必須是不相交的,由s0的極小。很明顯,我們可以發(fā)現(xiàn)這樣集合A和B很快,他們的聯(lián)盟是需要平衡的設(shè)置?,F(xiàn)在假設(shè)我們希望工業(yè)一個最小的平衡,如果有一子。我們描述動態(tài)規(guī)劃的需要O(n2J iai)的步驟為基礎(chǔ)的方法。和以前一樣,讓s0= iai / 2。對于每個s = 0,1 ,.,s0的,而且每個J型,K和K = 0,1 ,., 6 ,讓集f(s,j,k)為T,如果有一個大小最多K表的一個子集與對應(yīng)和s,讓集f(s,j,k),否則等于F。然后再次發(fā)生f(s,j,k)=f(s,j - 1,k)V f(s - flj,j - 1,k - 1)再加上適當?shù)倪吔鐥l件,使我們能夠確定的所有值在O集f(s,j,k)O(1) 每個值的步驟。對于每個S = 1,s0的是讓作為一個子集最小尺寸1,n的相應(yīng)和S如果有這樣的一個子集,讓為as= 0,如果不是;,讓旅館是第二小的尺寸一個子集1 . n s如果至少有兩個這樣的子集,讓bs= 0,如果沒有。我們已經(jīng)看到,我們可以計算出所有值集f(s,j,k)inO(n2s0)步驟。從這些值集f(s,j,k),我們可以計算出在相同的約束,因為所有的價值和BS,內(nèi)容如下。要計算的,注意,如果f = 0的(s,N組,n)= F和如果沒有則因為是最小的k,使得集f(s,n,k)=T現(xiàn)在假設(shè)as= 0,考慮如何計算學(xué)士學(xué)位。請注意,如果集f(s,j,k)= T接著我們可以找到一個子集1,j大小至多k與相應(yīng)和S透過回溯復(fù)發(fā)。我們也可以說,如果有多個這樣的子集檢查,如果再發(fā)生在右側(cè),如果過了相應(yīng)的集f(s,n,n)(我們知道的是T)這兩個術(shù)語噸有一個獨特的解決方案,然后bs= 0。否則,bs是最K,使得相應(yīng)的f(s,n,k)有一個以上的解決方案。如果bs當時的不可能有平衡的一個子集0。假設(shè)現(xiàn)在至少有一個非零值學(xué)士學(xué)位,并設(shè)T是一個值之比達到最小為+ BS上旅館所有的S = 0。讓我們在與Bt是每個T和相應(yīng)的金額,這樣獨特的套裝| AT= | 轉(zhuǎn)Bt =勝。 (我們可以找到這樣集快。)以下的索賠將完成我們的證明。索賠:該套在與Bt是不相交的,并在u =轉(zhuǎn)Bt CT是最小的平衡設(shè)置證明索賠:假設(shè)在滿足不同的集合和Bt。記的在 Bt基因的總和美國那么這也是轉(zhuǎn)Bt和在。但現(xiàn)在金+不at+bt= | Ct|。5 結(jié)束語我們已經(jīng)看到,即使是在削減庫存問題非常有限的情況下,它是強NP -難,盡量減少使用不同模式的數(shù)量,因此,我們不能期望能夠解決偽多項式時間等問題,即使。關(guān)鍵的概念,是一個平衡的子集,我們被帶往亞群平衡的考慮包裝啟發(fā)式,從而考慮尋求這種子集NP難問題。6 如需進一步閱讀以下參考,也是讀者所關(guān)心的:14。致 謝我非常感謝其他參與在紅外警戒中討論的研究組成員。參考文獻1 C. Aldridge, J. Chapman, R. Gower, R. Leese, C. McDiarmid, M. Shepherd, H. Tuenter, H. Wilson, A.Zinober, Pattern Reduction in Paper Cutting, Report of the 29th European Study Group with Industry,University of Oxford, March 1996.2 J.M. Allwood, C.N. Goulimis, Reducing the number of patterns in the 1-dimensional cutting stockproblem, Internal Report of Control Section, Electrical Engineering Department, Imperial College, 1988.3 N. Alon, O. Goldreich, J. Hastad, R. Peralta, Simple constructions of almost k-wise independent randomvariables, Random Structures and Algorithms 3 (1992) 289-304.4 V. Chvatal, Linear Programming, Freeman, San Francisco, 1983, pp. 195-212.5 E.G. Coffman, G.S. Lueker, Probabilistic Analysis of Packing and Partitioning Algorithms, Wiley, New York, 1991.6 M.R. Garey, D.S. Johnson, Computers and Intractability, Freeman, San Francisco, 1979.7 P.C. Gilmore, R.E. Gomory, A linear programming approach to the cutting-stock problem, Oper. Res.9 (1961) 849-859.8 P.C. Gilmore, R.E. Gomory, A linear programming approach to the cutting-stock probelem - Part II,Oper. Res. 11 (1963) 863-888.9 C.N. Goulimis, Optimal solutions for the cutting stock problem, European J. Oper. Res. 44 (1990)197-208.10 D. Johnson, The NP-completeness column: an ongoing guide, J. Algorithms 3 (1982) 182-195.11 R.E. Johnston, Rounding algorithms for cutting stock problems, J. Asian-Pacific Oper. Res. Soc. 3(1986) 166-171.12 N. Karmarkar, R.M. Karp, The differencing method of set partitioning, Technical Report UCB/CSD82/113, Computer Science Division (EECS), University of California, Berkeley, 1982. 13 A. Shamir, On the cryptocomplexity of knapsack systems, Proc. 11th Ann. ACM Symp. on Theory ofComputing, 1979, pp. 118-129.14 P.E. Sweeney, E.R. Paternoster, Cutting and packing problems: a categorized, application-orientatedresearch bibliography, J. Oper. Res. Soc. 43 (1992) 691-706. 15 L-H. Tsai, The modiied diferencing method for the set partitioning problem with cardinality conditions,Discrete Appl. Math. 63 (1995) 175-180.16 H. Tuenter, Personal communication, 1996.17 B. Yakir, The diferencing algorithm LDM for partitioning: a proof of a conjecture of Karmarkar andKarp, Math. Oper. Res. 21 (1996) 85-99.16
收藏