已閱讀5頁,還剩5頁未讀, 繼續(xù)免費(fèi)閱讀
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
Discrete Applied Mathematics 98 (1999) 121130Pattern minimisation in cutting stock problemsColin McDiarmid Department of Statistics, University of Oxford, 1 South Parks Road, Oxford OX1 3TG, UKReceived 21 October 1997; accepted 8 February 1999AbstractIn the cutting stock pattern minimisation problem, we wish to satisfy demand for variouscustomer reels by cutting as few as possible jumbo reels, and further to minimise the numberof distinct cutting patterns used. We focus on the special case in which any two customer reels t into a jumbo, but no three do: this case is of interest partly because it is the simplest casethat is not trivial, and partly because it may arise in practice when one attempts to improve asolution iteratively.We nd that the pattern minimisation problem is strongly NP-hard even in this special case,when the basic problem of nding a minimum waste solution is trivial. Our analysis focusseson balanced subsets, and suggests an approach for heuristic methods involving searching forbalanced subsets. ? 1999 Elsevier Science B.V. All rights reserved.Keywords: Cutting stock; Cutting patterns; Partition; NP-hard; Dynamic programming1. IntroductionSome materials such as paper may be manufactured in wide jumbo rolls, whicharelatercutintomuchnarrowerrollstosatisfycustomerdemands.Tominimisewaste,cuttingpatternsshouldbechosensoastouseasfewjumbosaspossible(see4,7,8).Thus the basic cutting stock problem has input a positive integer J, distinct positiveintegersr1;:;rn,andpositiveintegersd1;:;dn;andtherequiredtaskistouseasfewaspossiblejumbosofwidthJ tosatisfythedemandfordicustomerreelsofwidthri,for each i=1;:;n. This is one of the classical OR problems. It contains the stronglyNP-complete problem 3-PARTITION: thus it is NP-hard even if the jumbo size J isbounded by a polynomial in n, and each customer reel size risatis es J=4rin (d).To prove the reverse inequality, consider any partition of fv1;:;vnginto sets(Ki:i 2 I) of which at most one is not balanced. We will show that there is rep-resenting network G;w such that the graph G has components (Gi:i2I) where Gihas vertex set Ki, and these components are such that, if Kiis balanced then Giis atree and if not then Giis a tree with one added loop. This will complete the proof ofthe lemma.Consider a balanced set K, with partition AB such thatPi2Adi=Pi2Bdi.Wemust show that there is a tree T on K and non-negative weights weon the edges eof T such that, for each node v2K, the sum of the weights of the incident edgesequals dv(where loops count double). We use induction on jKj. If either A or Bis empty, the result is trivial, since we must have dv=0 for each v2K. Supposethen that both A and B are non-empty. Pick any a 2 A and b 2 B, and withoutloss of generality suppose that dadb. Reduce daby db. Now Knfbgis balanced,and inductively we can nd an appropriate weighted tree. Then add the edge ab withweight db.Finally, consider a set K which is not balanced, but is such that the correspondingsum of demands is even. As above, we can always replace two demands by theirdi erence at the cost of using one edge. Thus we can satisfy all but one demand byusing edges forming a tree on K, and then one added loop completes the component.3. PATTERN MINIMISATION is strongly NP-hardInthissectionweproveTheorem1,thattheproblemPATTERNMINIMISATIONisstronglyNP-hard.A summing triple (or Schur triple)isasetofthreedistinctintegerssuch that the sum of two equals the third. The following problem could be more fullydescribed as partition of distinct integers into summing triples.SUMMING TRIPLESInput: distinct positive integers s1;:;s3n.Question: can the input be partitioned into summing triples?C. McDiarmid/Discrete Applied Mathematics 98 (1999) 121130 125This problem is similar to NUMERICAL MATCHING WITH TARGET SUMS inGareyandJohnson6,p.224,butwiththeextra(surprisinglytroublesome)conditionthat the numbers involved must be distinct.Lemma 2. The problem SUMMINGTRIPLES is strongly NP-complete.Mostofthissectionwillbedevotedtoprovingtheabovelemma,but rstletusseethat it will yield Theorem 1.Proof of Theorem 1 (assumingLemma2). WegiveastrightforwardpolynomialtimereductionofSUMMINGTRIPLEStoDEGREES.ConsideraninstanceofSUMMINGTRIPLES as above. Take d =(2s1;:;2s3n) as an instance of DEGREES. Since thesiare distinct positive integers, there are no balanced sets of size less than 3. Thus (d)6n.HencebyLemma1, (d)2nand (d)=2nifandonlyifs1;:;s3ncanbepartitioned into summing triples.Now consider the problem SUMMING TRIPLES, which is clearly in NP. We shallshow that it is strongly NP-complete by giving a reduction from the NP-completeproblem RESTRICTED X3C, described below, to SUMMING TRIPLES with eachinterger siin O(n3).RESTRICTED X3CInput: a set X of 3q elements and a collection C of triples contained in X, suchthat each element of X is in exactly 3 triples.Question: can X be partitioned into triples in C?Lemma 3. The problem RESTRICTEDX3C is NP-complete.Proof. It is known that the problem is NP-complete if each element is constrained tobe in at most 3 triples rather than exactly 3 see Garey and Johnson 6, p. 221. Itis easy to tidy up an instance X;C so that each element is in exactly 3 triples.Clearly we can insist that each element is in either 2 or 3 triples. We can partitionthe elements which are in exactly two triples into blocks of size three. For each blockfx;y;zg, add three new elements x0;y0;z0and four new triples fx;y0;z0g;fx0;y;z0g;fx0;y0;zg;fx0;y0;z0g. Call the new instance X0;C0. Clearly, each element of X0is inexactly 3 triples in C0; and X can be partitioned into triples in C if any only if X0can be partitioned into triples in C0.Proof of Lemma 2. Consider an instance X;C of RESTRICTED X3C, where jXj=jCj=3q=n. Let Y =X f1;:;7g. We shall construct an expanded collectionD of triples contained in Y, such that X can be partitioned into triples in C if andonly if Y can be partitioned into triples in D; and then we shall construct an instance(s(y):y2Y) of SUMMING TRIPLES, where each size s(y)isO(n2), such that thesumming triples correspond precisely to the triples in D.126 C. McDiarmid/Discrete Applied Mathematics 98 (1999) 121130Form a bipartite graph G=(C;X;E) with vertex parts C and X and with verticesT 2C and x2X adjacent (that is, edge Tx2E) exactly when x2T. Since eachvertexdegreeinG isthree,wemay ndinpolynomialtimeaproper3-edge-colouring :E!f1;2;3g. We now split each element x2X into three copies (x;1);(x;2) and(x;3). Given a triple T=fx;y;zg2C, let T0be the tripleT0=f(x; (Tx);(y; (Ty);(z; (Tz)g:Observe that the elements in the triple T0have distinct rst co-ordinates (in X), anddistinctsecondco-ordinates(whichmustbe1,2,3);andthatthefamilyC0=(T0:T2C)partitions the set X f1;2;3g.Next, for each x2X, let Fxbe the collection consisting of the four triplesf(x;1),(x;4);(x;5)g; f(x;3);(x;4);(x;5)g; f(x;2);(x;6);(x;7)gandf(x;3);(x;6);(x;7)g.LetDbe the collection consisting of C0together with all the triples in the collections Fxforx2X. Thus D containsjCj+4jXj=5ntriples.If some subcollection D0of D is a partition of Y, then for each x2X, exactly oneof the elements (x;1);(x;2);(x;3) is not covered by triples in D0Fxand so must becoveredbytriplesinD0C0.ItfollowseasilythatX maybepartitionedintotriplesinC if and only if Y may be partitioned into triples in D. This completes the rst partof the construction.Next we shall see how to assign a size s(y) to each element y 2Y so that thesummingtriplesofelementsinY arepreciselythetriplesinD.Weshalluseafamilyof almost k-wise independent random variables de ned on a small sample space.Letl=d3log2ne+10,lett=2nl,letk=9l,andlet =12.ThereisasubsetLFoff0;1gt,of size 2(1+o(1)k, with the following property: if a point !=(!1;:;!t) is pickeduniformly at random from LF, then (!1;:;!t)is -away from k-wise independent see 3. Further such a set LF can be (explicitly) constructed in time bounded by apolynomial in n.Given a point !2LF, for each i=1;:;2n, let Si=Si(!) be the non-negative in-teger with binary expansion !(i1)l+1 !il. When a point !=(!1;:;!t) is pickeduniformly at random from LF, then S1;:;S2nare random variables, taking valuesin 0;1;:;N1, where N =2l, and they have the following property. For anyI f1;:;2ngwith 04N). This de nes s(x;i) for each x2X and i2f1;2;3g. Now, for eachx2X, let s(x;4)=(s(x;1)+s(x;3)=2, s(x;5)=(s(x;1)+s(x;3)=2;s(x;6)=(s(x;2)+s(x;3)=2,ands(x;7)=(s(x;2)+s(x;3)=2.Wehavenowde nedapositiveintegersize s(y) for each y2Y, and each triple in D is always summing.C. McDiarmid/Discrete Applied Mathematics 98 (1999) 121130 127LetB LFbethebadeventthateitherthevaluess(y)fory2Y failtobedistinct,or some triple other than those in D is summing. We shall show that P(B)1. Itwill follow that there is a sample point !2LFnB, and we can nd such a point inpolynomialtimebyexhaustivesearch.Thiswillthencompletetheproofofthelemma.To prove that P(B)1, it su ces for us to suppose that the random variablesS1;:;S2nare precisely 9-wise independent, with each uniformly distributed onf0;1;:;N1g, and then to prove that P(B)1=2. Observe that, from the de nitionofs(y),foreachy thereisavector a(y)2f1;0;1;2g2n,withsupportofsizeatmost3, such that s(y)Pia(y)iSiis a constant (that is, does not depend on !).Let y1and y2be distinct elements of Y. Let a=a(y1)a(y2). It is easy to seethat a is a non-zero integer vector with support of size at most 6, and there is aconstant c such that s(y1)=s(y2) if and only ifPiaiSi=c. But the probability ofthis last event is at most 1=N. Thus the probability that the values s(y) for y2Y arenot all distinct is at most jYj2 1N6(7n)22N.We may argue similarly for the unwanted triples. Let y1;y2and y3be distinctelements of Y, which form a triple T which is not in D. Consider the event thats(y1)+s(y2)=s(y3). Let a=a(y1)+a(y2)a(y3). Then a has support of size atmost9,andthereisaconstantcsuchthats(y1)+s(y2)=s(y3)ifandonlyifPiaiSi=c.Weclaimthatthevector a isnon-zero.ItwillthenfollowthattheprobabilitythatsometriplenotinDissummingisatmost jYj3 31N6(7n)32N;andhenceP(B)6(7n)2(8n)210n34 (y3)0.Now suppose that 2(y1)2f1;2g, that is (y1)=2. Then (y2) must be 1 or 2.We consider these two cases.(i) Suppose rst that (y2)=1. Then (y3)=3.Nowa(y1) has only one non-zeroco-ordinate 2, a(y2) has1;1;1 and a(y3) has 1;1;1. Then 1(y1)= 1(y2)= 1(y3)and the triple T=(y1;y2;y3)isinD, a contradiction.(ii) Now suppose that (y2)=2. Then (y3)=4.Nowa(y1) has one 2, a(y2) hasone 2 and a(y3) has 2,2. Again the triple T is in D, a contradiction.We have now shown that 2(y1)62f1;2;3g, and similarly for y2. Thus both 2(y1)and 2(y2) are inf4;5;6;7g.So (y1) and (y2)are1or3,and (y3)is2or4.Suppose rst that (y1)= (y2)=1, and so (y3)=2. Then both a(y1) and a(y2)have non-zero co-ordinates 1;1;1 and a(y3) has one 2. But then a(y1) and a(y2)must have the same support. It follows that 1(y1)= 1(y2), and this is not possible.Without loss of generality, we may now assume that (y1)=1and (y2)=3.Then (y3)=4;and a(y1) has non-zero co-ordinates 1;1;1; a(y2) has 1;1;1; anda(y3) has 2,2. Then again we nd that a(y1) and a(y2) must have the same support,and so 1(y1)= 1(y2)= 1(y3). But now the triple T is in D, a contradiction.128 C. McDiarmid/Discrete Applied Mathematics 98 (1999) 1211304. Finding balanced subsetsWe noted earlier that it is NP-complete to test if a given family a1;:;anof pos-itive integers has a balanced subset, but that we may nevertheless wish to search forbalancedsubsetsincertainheuristicapproachestopatternminimisation.Inthissectionweseethatastraightforwardapproachbasedondynamicprogrammingwillsolvesuchproblems in pseudo-polynomial time.We rst see how to test if there is a balanced subset, and if so to nd one (withsmallest corresponding sum), in O(nPiai) steps. After that we shall see how to nda smallest balanced subset, in O(n2Piai) steps. It is not obvious which of thesealgorithms would be better within a heuristic method for pattern minimisation.Let s0=Piai=2. For each s=0;1;:;s0, and each j=0;1;:;n, let f(s;j)beTif there is a subset off1;:;jgwith corresponding sum s, and let f(s;j) equal Fotherwise.Thenf(0;j)=Tforeachj=0;1;:;n,andf(s;0)=F foreachs=1;:;s0.We can calculate all the values f(s;j) in turn, in O(1) steps per value, as follows.for s=1;:;s0for j=1;:;nf(s;j) f(s;j1)_f(saj;j1):(If s0 we interpret f(s;j)asF.)If,intherecurrenceabove,itisneverthecasethatbothtermsontherightareT,thenthereisnobalancedsubset.Butsupposethatthiscasedoesoccur,andthe rsttimewemeetitisats0;j0.ThentherearetwodistinctsubsetsAandBwithcorrespondingsums(onecontainingj0andonenot).FurtherAandBmustbedisjoint,bytheminimalityof s0. Clearly we can nd such sets A and B quickly, and their union is the desiredbalanced set.Now suppose that we wish to nd a smallest balanced subset if there is one. Wedescribe a method based on dynamic programming which takes O(n2Piai) steps.Asbefore,lets0=Piai=2.Foreachs=0;1;:;s0,andeachj;k=0;1;:;nwithk6j,letf(s;j;k)beTifthereisasubsetoff1;:;jgofsizeatmostk withcorrespondingsum s, and let f(s;j;k) equal F otherwise. Then the recurrence.f(s;j;k)=f(s;j1;k)_f(saj;j1;k1);together with appropriate boundary conditions, allows us to determine all the valuesf(s;j;k) in O(1) steps per value.For each s=1;:;s0let asbe the smallest size of a subset of f1;:;ngwithcorresponding sum s if there is such a subset, and let as=0 if not; and let bsbe thesecond smallest size of a subset off1;:;ngwith corresponding sum s if there are atleast two such subsets, and let bs=0 if not. We have seen that we can calculate allthevaluesf(s;j;k)inO(n2s0)steps.Fromthesevaluesf(s;j;k),wecancalculateallthe values asand bswithin the same time bound, as follows.C. McDiarmid/Discrete Applied Mathematics 98 (1999) 121130 129Tocalculateas,notethatas=0iff(s;n;n)=Fandifnotthenasisthesmallestksuch that f(s;n;k)=T. Now suppose that as6=0, and consider how to calculate bs.Note that, if f(s;j;k)=Tthen we can nd a subset of f1;:;jgof size at most kwith corresponding sum s, by backtracking through the recurrence. We can also tellif there is more than one such subset by checking if the right side in the recurrenceever has both terms T. If corresponding to f(s;n;n) (which we know is T) there isa unique solution, then bs=0. Otherwise, bsis the least k such that corresponding tof(s;n;k) there is more than one solution.Ifbs=0foreachsthentherecanbenobalancedsubset.Supposenowthatthereisatleastonenon-zerovalue bs,andlet t beavalue s whichminimisesas+bsoveralls with bs6=0. Let Atand Btbe distinct sets each with corresponding sum t and suchthatjAtj=atandjBtj=bt. (We can nd such sets quickly.) The following claim willcomplete our proof.Claim. The sets Atand Btare disjoint; and Ct=AtBtis a smallest balanced set.Proof of claim. SupposethatthedistinctsetsAtandBtmeet.DenotethesumforAtnBtby u. Then this is also the sum for BtnAt. But now au+buas+bsat+bt=jCtj.5. Concluding remarksWe have seen that, even for a very restricted case of the cutting stock problem,it is strongly NP-hard to minimise the number of distinct patterns used, and thus wecannot expect to be able to solve such problems even in pseudo-polynomial time. Thekey notion was that of a balanced subset, and we were led to consider heuristics forpacking balanced subsets, and thus to consider the NP-hard problem of seeking suchsubsets.6. For Further ReadingThe following reference is also of interest to the reader: 14.AcknowledgementsIwouldliketoacknowledgehelpfulandenjoyablediscussionswiththeothermem-bers of the Study Group listed in the rst reference below.130 C. McDiarmid/Discrete Applied Mathematics 98 (1999) 121130References1 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,InternalReportofControlSection,ElectricalEngineeringDepartm
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024年對外貿(mào)易協(xié)議簽訂流程及注意事項版B版
- 2024年標(biāo)準(zhǔn)代銷業(yè)務(wù)協(xié)議示例版B版
- 漯河職業(yè)技術(shù)學(xué)院《地籍管理》2023-2024學(xué)年第一學(xué)期期末試卷
- 2025年吉林道路貨運(yùn)從業(yè)資格證模擬考試
- 2024年商業(yè)物業(yè)管理與社區(qū)安全防范體系建設(shè)合同3篇
- 2024年模具生產(chǎn)服務(wù)協(xié)議標(biāo)準(zhǔn)文本版B版
- 單位人事管理制度展示選集
- 2025出租車半股轉(zhuǎn)讓合同
- 鄉(xiāng)村水廠建設(shè)與運(yùn)營合作協(xié)議
- 環(huán)保工程總包施工合同
- 多金屬廢料高效綜合回收利用產(chǎn)業(yè)升級項目環(huán)評報告書
- 石方開挖的環(huán)保措施
- 商洛市商州區(qū)金礦煤礦礦山地質(zhì)環(huán)境保護(hù)與土地復(fù)墾方案
- 中國鐵塔股份有限公司代維交接指南(2017年)
- 常用藥物皮試配制法和藥物過敏反應(yīng)的急救措施
- 醫(yī)學(xué)微生物學(xué)知到章節(jié)答案智慧樹2023年山東第一醫(yī)科大學(xué)
- 印刷通用質(zhì)量檢驗標(biāo)準(zhǔn)
- 電子測量技術(shù)基礎(chǔ)課后答案
- 大興調(diào)查研究研討發(fā)言材料學(xué)習(xí)心得體會中心組3篇
- 培訓(xùn)學(xué)?;馂?zāi)應(yīng)急預(yù)案
- 面試評分表完整版
評論
0/150
提交評論