生產(chǎn)線軸類零件上下料機構(gòu)設(shè)計

生產(chǎn)線軸類零件上下料機構(gòu)設(shè)計,生產(chǎn)線軸類零件上下料機構(gòu)設(shè)計,生產(chǎn),出產(chǎn),線軸,零件,上下,機構(gòu),設(shè)計 Discrete Applied Mathematics 98 (1999) 121130 Pattern minimisation in cutting stock problems Colin McDiarmid Department of Statistics, University of Oxford, 1 South Parks Road, Oxford OX1 3TG, UK Received 21 October 1997; accepted 8 February 1999 Abstract In the cutting stock pattern minimisation problem, we wish to satisfy demand for various customer reels by cutting as few as possible jumbo reels, and further to minimise the number of 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 case that is not trivial, and partly because it may arise in practice when one attempts to improve a solution 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 focusses on balanced subsets, and suggests an approach for heuristic methods involving searching for balanced subsets. ? 1999 Elsevier Science B.V. All rights reserved. Keywords: Cutting stock; Cutting patterns; Partition; NP-hard; Dynamic programming 1. Introduction Some materials such as paper may be manufactured in wide jumbo rolls, which arelatercutintomuchnarrowerrollstosatisfycustomerdemands.Tominimisewaste, cuttingpatternsshouldbechosensoastouseasfewjumbosaspossible(see4,7,8). Thus the basic cutting stock problem has input a positive integer J, distinct positive integersr 1 ;:;r n ,andpositiveintegersd 1 ;:;d n ;andtherequiredtaskistouseasfew aspossiblejumbosofwidthJ tosatisfythedemandford i customerreelsofwidthr i , for each i=1;:;n. This is one of the classical OR problems. It contains the strongly NP-complete problem 3-PARTITION: thus it is NP-hard even if the jumbo size J is bounded by a polynomial in n, and each customer reel size r i satis es J=4r i n (d). To prove the reverse inequality, consider any partition of fv 1 ;:;v n ginto sets (K i :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 (G i :i2I) where G i has vertex set K i , and these components are such that, if K i is balanced then G i is a tree and if not then G i is a tree with one added loop. This will complete the proof of the lemma. Consider a balanced set K, with partition AB such that P i2A d i = P i2B d i .We must show that there is a tree T on K and non-negative weights w e on the edges e of T such that, for each node v2K, the sum of the weights of the incident edges equals d v (where loops count double). We use induction on jKj. If either A or B is empty, the result is trivial, since we must have d v =0 for each v2K. Suppose then that both A and B are non-empty. Pick any a 2 A and b 2 B, and without loss of generality suppose that d a d b . Reduce d a by d b . Now Knfbgis balanced, and inductively we can nd an appropriate weighted tree. Then add the edge ab with weight d b . Finally, consider a set K which is not balanced, but is such that the corresponding sum of demands is even. As above, we can always replace two demands by their di erence at the cost of using one edge. Thus we can satisfy all but one demand by using edges forming a tree on K, and then one added loop completes the component. 3. PATTERN MINIMISATION is strongly NP-hard InthissectionweproveTheorem1,thattheproblemPATTERNMINIMISATIONis stronglyNP-hard.A summing triple (or Schur triple)isasetofthreedistinctintegers such that the sum of two equals the third. The following problem could be more fully described as partition of distinct integers into summing triples. SUMMING TRIPLES Input: distinct positive integers s 1 ;:;s 3n . Question: can the input be partitioned into summing triples? C. McDiarmid/Discrete Applied Mathematics 98 (1999) 121130 125 This problem is similar to NUMERICAL MATCHING WITH TARGET SUMS in GareyandJohnson6,p.224,butwiththeextra(surprisinglytroublesome)condition that the numbers involved must be distinct. Lemma 2. The problem SUMMINGTRIPLES is strongly NP-complete. Mostofthissectionwillbedevotedtoprovingtheabovelemma,but rstletussee that it will yield Theorem 1. Proof of Theorem 1 (assumingLemma2). Wegiveastrightforwardpolynomialtime reductionofSUMMINGTRIPLEStoDEGREES.ConsideraninstanceofSUMMING TRIPLES as above. Take d =(2s 1 ;:;2s 3n ) as an instance of DEGREES. Since the s i are distinct positive integers, there are no balanced sets of size less than 3. Thus (d)6n.HencebyLemma1, (d)2nand (d)=2nifandonlyifs 1 ;:;s 3n canbe partitioned into summing triples. Now consider the problem SUMMING TRIPLES, which is clearly in NP. We shall show that it is strongly NP-complete by giving a reduction from the NP-complete problem RESTRICTED X3C, described below, to SUMMING TRIPLES with each interger s i in O(n 3 ). RESTRICTED X3C Input: a set X of 3q elements and a collection C of triples contained in X, such that 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 to be in at most 3 triples rather than exactly 3 see Garey and Johnson 6, p. 221. It is 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 partition the elements which are in exactly two triples into blocks of size three. For each block fx;y;zg, add three new elements x 0 ;y 0 ;z 0 and four new triples fx;y 0 ;z 0 g;fx 0 ;y;z 0 g; fx 0 ;y 0 ;zg;fx 0 ;y 0 ;z 0 g. Call the new instance X 0 ;C 0 . Clearly, each element of X 0 is in exactly 3 triples in C 0 ; and X can be partitioned into triples in C if any only if X 0 can be partitioned into triples in C 0 . 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 collection D of triples contained in Y, such that X can be partitioned into triples in C if and only 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(n 2 ), such that the summing triples correspond precisely to the triples in D. 126 C. McDiarmid/Discrete Applied Mathematics 98 (1999) 121130 Form a bipartite graph G=(C;X;E) with vertex parts C and X and with vertices T 2C and x2X adjacent (that is, edge Tx2E) exactly when x2T. Since each vertexdegreeinG 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 T 0 be the triple T 0 =f(x; (Tx);(y; (Ty);(z; (Tz)g: Observe that the elements in the triple T 0 have distinct rst co-ordinates (in X), and distinctsecondco-ordinates(whichmustbe1,2,3);andthatthefamilyC 0 =(T 0 :T2C) partitions the set X f1;2;3g. Next, for each x2X, let F x be 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.LetD be the collection consisting of C 0 together with all the triples in the collections F x for x2X. Thus D containsjCj+4jXj=5ntriples. If some subcollection D 0 of D is a partition of Y, then for each x2X, exactly one of the elements (x;1);(x;2);(x;3) is not covered by triples in D 0 F x and so must be coveredbytriplesinD 0 C 0 .ItfollowseasilythatX maybepartitionedintotriplesin C if and only if Y may be partitioned into triples in D. This completes the rst part of the construction. Next we shall see how to assign a size s(y) to each element y 2Y so that the summingtriplesofelementsinY arepreciselythetriplesinD.Weshalluseafamily of almost k-wise independent random variables de ned on a small sample space. Letl=d3log 2 ne+10,lett=2nl,letk=9l,andlet = 1 2 .ThereisasubsetLFoff0;1g t , of size 2 (1+o(1)k , with the following property: if a point !=(! 1 ;:;! t ) is picked uniformly 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 a polynomial in n. Given a point !2LF, for each i=1;:;2n, let S i =S i (!) be the non-negative in- teger with binary expansion ! (i1)l+1 ! il . When a point !=(! 1 ;:;! t ) is picked uniformly at random from LF, then S 1 ;:;S 2n are random variables, taking values in 0;1;:;N1, where N =2 l , and they have the following property. For any I f1;:;2ngwith 04N). This de nes s(x;i) for each x2X and i2f1;2;3g. Now, for each x2X, 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 nedapositiveinteger size s(y) for each y2Y, and each triple in D is always summing. C. McDiarmid/Discrete Applied Mathematics 98 (1999) 121130 127 LetB LFbethebadeventthateitherthevaluess(y)fory2Y failtobedistinct, or some triple other than those in D is summing. We shall show that P(B)1. It will follow that there is a sample point !2LFnB, and we can nd such a point in polynomialtimebyexhaustivesearch.Thiswillthencompletetheproofofthelemma. To prove that P(B)1, it su ces for us to suppose that the random variables S 1 ;:;S 2n are precisely 9-wise independent, with each uniformly distributed on f0;1;:;N1g, and then to prove that P(B)1=2. Observe that, from the de nition ofs(y),foreachy thereisavector a(y)2f1;0;1;2g 2n ,withsupportofsizeatmost 3, such that s(y) P i a(y) i S i is a constant (that is, does not depend on !). Let y 1 and y 2 be distinct elements of Y. Let a=a(y 1 )a(y 2 ). It is easy to see that a is a non-zero integer vector with support of size at most 6, and there is a constant c such that s(y 1 )=s(y 2 ) if and only if P i a i S i =c. But the probability of this last event is at most 1=N. Thus the probability that the values s(y) for y2Y are not all distinct is at most jYj 2 1 N 6 (7n) 2 2N . We may argue similarly for the unwanted triples. Let y 1 ;y 2 and y 3 be distinct elements of Y, which form a triple T which is not in D. Consider the event that s(y 1 )+s(y 2 )=s(y 3 ). Let a=a(y 1 )+a(y 2 )a(y 3 ). Then a has support of size at most9,andthereisaconstantcsuchthats(y 1 )+s(y 2 )=s(y 3 )ifandonlyif P i a i S i =c. Weclaimthatthevector a isnon-zero.Itwillthenfollowthattheprobabilitythatsome triplenotinDissummingisatmost jYj 3 3 1 N 6 (7n) 3 2N ;andhenceP(B)6 (7n) 2 (8n) 2 10 n 3 4 (y 3 )0. Now suppose that 2 (y 1 )2f1;2g, that is (y 1 )=2. Then (y 2 ) must be 1 or 2. We consider these two cases. (i) Suppose rst that (y 2 )=1. Then (y 3 )=3.Nowa(y 1 ) has only one non-zero co-ordinate 2, a(y 2 ) has1;1;1 and a(y 3 ) has 1;1;1. Then 1 (y 1 )= 1 (y 2 )= 1 (y 3 ) and the triple T=(y 1 ;y 2 ;y 3 )isinD, a contradiction. (ii) Now suppose that (y 2 )=2. Then (y 3 )=4.Nowa(y 1 ) has one 2, a(y 2 ) has one 2 and a(y 3 ) has 2,2. Again the triple T is in D, a contradiction. We have now shown that 2 (y 1 )62f1;2;3g, and similarly for y 2 . Thus both 2 (y 1 ) and 2 (y 2 ) are inf4;5;6;7g.So (y 1 ) and (y 2 )are1or3,and (y 3 )is2or4. Suppose rst that (y 1 )= (y 2 )=1, and so (y 3 )=2. Then both a(y 1 ) and a(y 2 ) have non-zero co-ordinates 1;1;1 and a(y 3 ) has one 2. But then a(y 1 ) and a(y 2 ) must have the same support. It follows that 1 (y 1 )= 1 (y 2 ), and this is not possible. Without loss of generality, we may now assume that (y 1 )=1and (y 2 )=3. Then (y 3 )=4;and a(y 1 ) has non-zero co-ordinates 1;1;1; a(y 2 ) has 1;1;1; and a(y 3 ) has 2,2. Then again we nd that a(y 1 ) and a(y 2 ) must have the same support, and so 1 (y 1 )= 1 (y 2 )= 1 (y 3 ). But now the triple T is in D, a contradiction. 128 C. McDiarmid/Discrete Applied Mathematics 98 (1999) 121130 4. Finding balanced subsets We noted earlier that it is NP-complete to test if a given family a 1 ;:;a n of pos- itive integers has a balanced subset, but that we may nevertheless wish to search for balancedsubsetsincertainheuristicapproachestopatternminimisation.Inthissection weseethatastraightforwardapproachbasedondynamicprogrammingwillsolvesuch problems in pseudo-polynomial time. We rst see how to test if there is a balanced subset, and if so to nd one (with smallest corresponding sum), in O(n P i a i ) steps. After that we shall see how to nd a smallest balanced subset, in O(n 2 P i a i ) steps. It is not obvious which of these algorithms would be better within a heuristic method for pattern minimisation. Let s 0 = P i a i =2. For each s=0;1;:;s 0 , and each j=0;1;:;n, let f(s;j)be Tif there is a subset off1;:;jgwith corresponding sum s, and let f(s;j) equal F otherwise.Thenf(0;j)=Tforeachj=0;1;:;n,andf(s;0)=F foreachs=1;:;s 0 . We can calculate all the values f(s;j) in turn, in O(1) steps per value, as follows. for s=1;:;s 0 for j=1;:;n f(s;j) f(s;j1)_f(sa j ;j1): (If s0 we interpret f(s;j)asF.) If,intherecurrenceabove,itisneverthecasethatbothtermsontherightareT,then thereisnobalancedsubset.Butsupposethatthiscasedoesoccur,andthe rsttimewe meetitisats 0 ;j 0 .ThentherearetwodistinctsubsetsAandBwithcorrespondingsum s(onecontainingj 0 andonenot).FurtherAandBmustbedisjoint,bytheminimality of s 0 . Clearly we can nd such sets A and B quickly, and their union is the desired balanced set. Now suppose that we wish to nd a smallest balanced subset if there is one. We describe a method based on dynamic programming which takes O(n 2 P i a i ) steps. Asbefore,lets 0 = P i a i =2.Foreachs=0;1;:;s 0 ,andeachj;k=0;1;:;nwithk6j, letf(s;j;k)beTifthereisasubsetoff1;:;jgofsizeatmostk withcorresponding sum s, and let f(s;j;k) equal F otherwise. Then the recurrence. f(s;j;k)=f(s;j1;k)_f(sa j ;j1;k1); together with appropriate boundary conditions, allows us to determine all the values f(s;j;k) in O(1) steps per value. For each s=1;:;s 0 let a s be the smallest size of a subset of f1;:;ngwith corresponding sum s if there is such a subset, and let a s =0 if not; and let b s be the second smallest size of a subset off1;:;ngwith corresponding sum s if there are at least two such subsets, and let b s =0 if not. We have seen that we can calculate all thevaluesf(s;j;k)inO(n 2 s 0 )steps.Fromthesevaluesf(s;j;k),wecancalculateall the values a s and b s within the same time bound, as follows. C. McDiarmid/Discrete Applied Mathematics 98 (1999) 121130 129 Tocalculatea s ,notethata s =0iff(s;n;n)=Fandifnotthena s isthesmallestk such that f(s;n;k)=T. Now suppose that a s 6=0, and consider how to calculate b s . Note that, if f(s;j;k)=Tthen we can nd a subset of f1;:;jgof size at most k with corresponding sum s, by backtracking through the recurrence. We can also tell if there is more than one such subset by checking if the right side in the recurrence ever has both terms T. If corresponding to f(s;n;n) (which we know is T) there is a unique solution, then b s =0. Otherwise, b s is the least k such that corresponding to f(s;n;k) there is more than one solution. Ifb s =0foreachsthentherecanbenobalancedsubset.Supposenowthatthereis atleastonenon-zerovalue b s ,andlet t beavalue s whichminimisesa s +b s overall s with b s 6=0. Let A t and B t be distinct sets each with corresponding sum t and such thatjA t j=a t andjB t j=b t . (We can nd such sets quickly.) The following claim will complete our proof. Claim. The sets A t and B t are disjoint; and C t =A t B t is a smallest balanced set. Proof of claim. SupposethatthedistinctsetsA t andB t meet.DenotethesumforA t nB t by u. Then this is also the sum for B t nA t . But now a u +b u a s +b s a t +b t =jC t j. 5. Concluding remarks We 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 we cannot expect to be able to solve such problems even in pseudo-polynomial time. The key notion was that of a balanced subset, and we were led to consider heuristics for packing balanced subsets, and thus to consider the NP-hard problem of seeking such subsets. 6. For Further Reading The following reference is also of interest to the reader: 14. Acknowledgements Iwouldliketoacknowledgehelpfulandenjoyablediscussionswiththeothermem- bers of the Study Group listed in the rst reference below. 130 C. McDiarmid/Discrete Applied Mathematics 98 (1999) 121130 References 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 stock problem,InternalReportofControlSection,ElectricalEngineeringDepartment,ImperialCollege,1988. 3 N.Alon,O.Goldreich,J.H astad,R.Peralta,Simpleconstructionsofalmostk-wiseindependentrandom variables, Random Structures and Algorithms 3 (1992) 289304. 4 V. Chv atal, Linear Programming, Freeman, San Francisco, 1983, pp. 195212. 5 E.G.Co man,G.S.Lueker,ProbabilisticAnalysisofPackingandPartitioningAlgorithms,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) 849859. 8 P.C. Gilmore, R.E. Gomory, A linear programming approach to the cutting-stock probelem Part II, Oper. Res. 11 (1963) 863888. 9 C.N. Goulimis, Optimal solutions for the cutting stock problem, European J. Oper. Res. 44 (1990) 197208. 10 D. Johnson, The NP-completeness column: an ongoing guide, J. Algorithms 3 (1982) 182195. 11 R.E. Johnston, Rounding algorithms for cutting stock problems, J. AsianPaci c Oper. Res. Soc. 3 (1986) 166171. 12 N. Karmarkar, R.M. Karp, The di erencing method of set partitioning, Technical Report UCB=CSD 82=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 of Computing, 1979, pp. 118129. 14 P.E. Sweeney, E.R. Paternoster, Cutting and packing problems: a categorized, application-orientated research bibliography, J. Oper. Res. Soc. 43 (1992) 691706. 15 L-H.Tsai,Themodi eddi erencingmethodforthesetpartitioningproblemwithcardinalityconditions, Discrete Appl. Math. 63 (1995) 175180. 16 H. Tuenter, Personal communication, 1996. 17 B. Yakir, The di erencing algorithm LDM for partitioning: a proof of a conjecture of Karmarkar and Karp, Math. Oper. Res. 21 (1996) 8599.