Laman utama
A I I E Transactions A Minimax Layout Problem on the Line Involving Distances between Classes of Objects
A Minimax Layout Problem on the Line Involving Distances between Classes of Objects
Papineau, Robert L., Francis, Richard L.Sukakah Anda buku ini?
Bagaimana kualitas file yang diunduh?
Unduh buku untuk menilai kualitasnya
Bagaimana kualitas file yang diunduh?
Jilid:
6
Bahasa:
english
Majalah:
A I I E Transactions
DOI:
10.1080/05695557408974960
Date:
September, 1974
File:
PDF, 404 KB
Tag Anda:
 Silakan masuk ke akun Anda dulu

Butuh bantuan? Silakan baca instruksi pendek cara mengirim buku ke Kindle
Selama 15 menit file akan dikirim ke email Anda.
Selama 15 menit file akan dikirim ke kindle Anda.
Catatan: Anda perlu memverifikasi setiap buku yang ingin Anda kirim ke Kindle Anda. Periksa email Anda untuk yakin adanya email verifikasi dari Amazon Kindle.
Catatan: Anda perlu memverifikasi setiap buku yang ingin Anda kirim ke Kindle Anda. Periksa email Anda untuk yakin adanya email verifikasi dari Amazon Kindle.
Daftar buku terkait
0 comments
Anda dapat meninggalkan komentar Anda tentang buku dan berbagi pengalaman Anda. Pembaca lain tertarik untuk mengetahui pendapat Anda tentang buku yang telah Anda baca. Terlepas Anda suka atau tidak buku itu, jika Anda menceritakan secara jujur dan mendetil, orang dapat menemukan buku baru buat diri mereka, buku yang sesuai dengan minatnya.
1


2


This article was downloaded by: [Monash University Library] On: 01 February 2015, At: 07:50 Publisher: Taylor & Francis Informa Ltd Registered in England and Wales Registered Number: 1072954 Registered office: Mortimer House, 3741 Mortimer Street, London W1T 3JH, UK A I I E Transactions Publication details, including instructions for authors and subscription information: http://www.tandfonline.com/loi/uiie19 A Minimax Layout Problem on the Line Involving Distances between Classes of Objects a Robert L. Papineau & Richard L. Francis a b Université du Québec à Trois—Rivières Trois , Rivierès, Québec b University of Florida , Gainesville, Florida, 32611 Published online: 09 Jul 2007. To cite this article: Robert L. Papineau & Richard L. Francis (1974) A Minimax Layout Problem on the Line Involving Distances between Classes of Objects, A I I E Transactions, 6:3, 252256, DOI: 10.1080/05695557408974960 To link to this article: http://dx.doi.org/10.1080/05695557408974960 PLEASE SCROLL DOWN FOR ARTICLE Taylor & Francis makes every effort to ensure the accuracy of all the information (the “Content”) contained in the publications on our platform. However, Taylor & Francis, our agents, and our licensors make no representations or warranties whatsoever as to the accuracy, completeness, or suitability for any purpose of the Content. Any opinions and views expressed in this publication are the opinions and views of the authors, and are not the views of or endorsed by Taylor & Francis. The accuracy of the Content should not be relied upon and should be independently verified with primary sources of information. Taylor and Francis shall not be liable for any losses, actions, claims, proceedings, demands, costs, expenses, damages, and other liabilities whatsoever or howsoever caused arising directly or indirectly in connection with, in relation to or arising out of the use of the Content. This article may be used for research, teaching, and private study purposes. Any substantial or system; atic reproduction, redistribution, reselling, loan, sublicensing, systematic supply, or distribution in any form to anyone is expressly forbidden. Terms & Conditions of access and use can be found at http:// www.tandfonline.com/page/termsandconditions TECHNICAL NOTE A Minimax Layout Problem on the Line Involving Distances between Classes of Objects* ROBERT L. PAPINEAU MEMBER, AIIE Universitd du Qudbec A Trois  RiviBres TroisRivierBs, Qudbec RICHARD L. FRANCIS Downloaded by [Monash University Library] at 07:50 01 February 2015 SENIORMEMBER, AIIE University of Florida Gainesville, Florida 3261 1 Abstract: A minimax layout problem on the line is considered for which the objective function depends upon the distances between classes of objects to be laid out. A closed form answer is obtained, as well as necessary and sufficient conditions for a layout to be a minimax layout. Problem Statement. Solution. and Literature Discussion The problem we consider may be described as follows. Suppose N classes of objects are given, and class j is located along the line, for I < j <N, as folIows: the region taken up by class j, denoted by $,. may be represented by the union of any finite collection of nonoveriapping intervalsnot necessarily adjacentwith the sum of the lengths of these intervals being L j , a known number. For any two different classes i and j, the regions Si and Sj do not overlap. Further, class 1 is numbered such that Any collection of N such regions will be represented by { S i , Sz, . . . , S N ) , and will be called a linear layout. The set consisting of all such linear layouts will be denoted by HN(L)where L = (L L 2 , . . . ,LN). In the next section we give a bit more general definition of HN(L), but, the definition here suffices for most purposes. Possible examples of a linear layout include the regions taken up by N classes of machines, work places, or activities to be located along an aisle, or along a conveyor belt or overhead trolley line on which objects can move in either direction. Other possible examples include regions taken up by N store fronts to be located alonga sidewalk, or regions taken up by N1 store fronts and one "shallow" parking lot, all of which are to be located along a street. While it is evident that planar layouts are generally of more interest than linear layouts, we do believe that linear layout problems are of interest. In addition to the examples mentioned above, other related linear layout problems occur in contexts to be mentioned in the literature discussion to follow. Further, the linear layout case,which is conceptually simpler than the planar case, gives insight into a means of attacking the planar layout case. Results have been obtained for the planar case, (7), and will be reported upon subsequently. Next we define an objective function for a linear layout. Given any such layout, denoted by { S , , . . . ,SN ) ,let Fij (Si, Sj) denote the maximum distance between Si and S j , that is, for 1 f i <j <N, F i j ( S i , S j ) = max [ / x i xjl : xi f Si,X j E Sj]  * Received September 1973; revised July 1974. A portion of this note is based on the dissertation work of the first author at the University of Florida.   AIIE TRANSACTIONS, Volume 6, No. 3 Next define F(Sl, . . . , SN) by Downloaded by [Monash University Library] at 07:50 01 February 2015 The expression [2] defines the objective function for the linear layout, and is the greatest distance between any two of the regions. Our interest is in finding a layout {Sl*, . . . , SN*)in HN(L) for which where {S1, . . . ,SN) is any other layout in HN(L); namely, we wish to find a minimax layout. Other objective functions for linear layouts have been considered, and will be discussed below. Roughly speaking, a minimax layout is one for which the two regions farthest apart are as near one another as possible. We note the objective function [2] does not include any information about relative movement between different classes of objects; it simply uses the maximum distance between the regions occupied by any two classes of objects as a measure of closeness for the two classes. When N = 2, it is evident that it would often be unnecessary in any event to use information about relative movement between the two classes in seeking a best layout; when N > 2, it is less evident that such information is unnecessary. The use of an objective function such as [2] when N > 2 may be justified when such data is not obtainable, or varies in an unknown manner over time. Also we consider a minimax layout of some use as a design guideline. It is a design guideline in the sense that it provides a basis of comparison for other layouts which are arrived at considering aspects in addition to those included in the model [2]. Further, the use of a minimax approach to optimization problems is often considered to be a conservative approach ; a minimax answer guarantees that the "worst case" is as good as possible. At this point it seems appropriate to emphasize the fact that the definition of a linear layout does not require that the region taken up by class j be a single interval of length Lj (when this requirement is imposed the layout problem has a trivial solution); we specifically adopt the approach of allowing class j to take up a region consisting of any finite collection of disjoint intervals, which may be separated by regions taken up by other classes of objects. Whether or not such an approach is reasonable clearly depends upon the problem context. For example, it is not too unusual to find a parking lot on each side of a building; thus if S2 represents the region taken up by the building and S, the region taken up by the parking lot, S1 could consist of two disjoint intervals. Next we state the major results obtained for this problem; proofs of the results are given in the next section. We find it convenient to define L by L ZN Lj. Recalling that classes of objects are numbered such thiTtl] holds, if{S1 *, . . . is any layout such that the union of S,* through SN* is an interval, say TI *, of length L  L and S1* is the union of two disjoint intervals, say S: * and st*, each of length L1 12, with S;'* adjacent to one end of TI* and Sy* adjacent to the other end of TI*,then {S1*, . . . ,SN*) is a minimax layout in the sense that it satisfies [3] ; an example is shown in Fig. 1. For another example, if {S,*, . . ,SN*} is such that T1 * = [0, L  L1 ] and S, * = [L, /2,0] IU [LL,, L  L 121, then {S, *, . . . ,SN*)is a minimax layout, and ,, . Conversely, we also show, if {S1*, . . . , SN*}is a minimax layout, then for some p such that L = L,, T, * A u{S'*: 1< j <N, j # p ) is an interval of length L  Lp and S,* is the union of two disjoint intervals, each of length L,/2 = L1 12, with one of the two intervals adjacent to one end of Tp * and the other interval adjacent to the other end. Thus for any minimax layout, an object class with the largest Li is always "split" with half of the region taken up by the object class on one end of the layout and the other half on the other end.If L1 > Lj, 2 <j <N, then object class 1 will always be split with half on one end of the layout and half on the other end if the layout is a minimax layout. Given that L1 > Lj, 2 G j dN, we also note that object classes 2, . . . ,N can take up any regions S2*, Sg*, . . . , &*,whatsoever provided only that {Sl*, . . . ,SN*) is a linear layout and that T1* is an interval of length L  I,,, with S1* "split" evenly into two parts abutting TI *. Thus if N > 2 we have a great deal of latitude in the choice of a minimax layout, and auxiliary criteria may possibly be employed in choosing the regions to be occupied by classes 2,3, . . . ,N. To the best of our knowledge the results just stated are the first closed form answers of any type to be obtained for layouts in HN(L) when the criterion being optimized is a function of the distance between object classes and N > 2; they are also believed to be the first results obtained for the minimax problem we examine. There is, however, some related work. The minimax problem for which we give a solution was suggested, but not solved, by Newman (6). Newman solved a linear layout problem for which N = 2 and the objective function is the average distance between Fig. 1. Sketch of a minimax linear layout. September 1974, AIIE TRANSACTIONS 253 Downloaded by [Monash University Library] at 07:50 01 February 2015 the two regions under an equal likelihood assumption. Newman obtained a lower bound on the value of the average distance and constructed a sequence of linear layouts which attain this average distance in the limit; his layouts are somewhat similar to ours in that at least some of the largest set is "split" symmetrically about the rest. Apparently an actual minimum solution does not exist to Newman's problem, which seems nonintuitive, and a bit discouraging. Further, Newman's analysis relies strongly upon properties of single integrals, so that the task of extending his analysis to solve planar layout problems appears formidable, and remains to be done. In other related work, Francis (2) has examined some facility design problems and presented results for planar layouts; entirely analogous results apply for linear layouts. The objective function considered in (2) is not dependent on the distances between the classes of objects to be located, but between classes of objects and points whose locations are known. Recently, Lowe (5) has considered a weighted minisum linear layout problem; the answers he obtains are somewhat similar to ours, except that each object class is "split" and there are fewer alternative optima. The remaining results on linear layouts of which we are aware are all closely related to the socalled module placement problem solved by Karp and Held (4). The module placement problem consists of assigning modules to locations on a line in such a way as to minimize a weighted sum of distances between all pairs of modules, where the appropriate weight for each pair is known. Karp and Held show that the module placement problem may be formulated and solved as a dynamic programming problem; no computational experience is reported, but the approach does not appear to be too tractable, computationally. Subsequently Elmaghraby (1) has shown that a sequencing problemmay be formulated and solved using the approach of Karp and Held. Simmons, (9), (lo), in work on a problem closely related to that of Karp and Held, studies a version of the module placement problem where the modules may have different lengths, and are considered to be room fronts along an aisle. Simmons develops a branch and bound approach for solving the problem, and presents computational results for his approach; the approach appears computationally feasible for N < 9. We note that the module placement problem is itself a special case of the quadratic assignment problem. Extensive discussions of the quadratic assignment r '>{em may be found in the review paper by Hanan and Kurr~berg (3), and in the literature discussion of the paper by Pierce and Crowston (8). The quadratic assignment problem is at least as difficult to solve as the module placement probiem, and is generally solved using heuristic procedures (3), although several branch and bound solution procedures have been developed. the next section without loss of continuity. We first generalize the definition of HN(L). Given sets Sl , . . . ,SNcontained in E l , we say that {S, , . . . ,SN}is a linear layout if Sj is a closed and bounded, that is, compact set of measure Lj for 1 f j < N , and Si and Sj contain no common interior points for 1 f i f j f N. The numbers L 1 , . . . , LN are given positive numbers and satisfy [ I ] . (The measure of Sj may be considered to be the integral over Sj of the constant function one.) HN(L) is then the collection of all linear layouts. For any layout {S,, . . . , SN)the definitions of Fij(Si,Sj) and F(S1, . . . , SN) remain unchanged. Our approach to finding a minimax linear layout basically will be one of showing that L  L, 12 is a lower bound on the objective function value of every layout. The layouts {S1* , . . . , S N * ) given in the first section have an objective function value equal to this lower bound, and therefore are minimax layouts. It is convenient to summarize one of our observations as follows. Remark I There exist layouts with objective function value L  L112. Given any layout {S1, . . . ,SN), the smallest and largest points in ~ ' j v will , ~ be~ called ~ the smallest and largest end points of the layout and will be denoted by e l and e2 respectively; further, we define Ti by Ti = U{Sj : 1 f j f N , j f i ) If for any i such that 1 f i d N , e l e S i a n d e 2 ~ s i , we call the layout a common end point layout. The layouts {S1*, . . . , SN*) of the previous section provide examples of common end point layouts. If{SI, . . . ,SN)is not a common erd point layout then evidently F(Sl , . . . , SN)=e2el 2 L >. L  L112, so that using Remark I ,we have Remark 2 If a layout is a minimax layout, it is a common end poi~i:layout. Due to Remark 2, we need only consider common endpoint layouts in seeking a minimax layout. In the subsequent discussion of this paragraph it may be useful to refer to Fig. 2. Let {S1,. . . , SN) be a common end point layout with e l e Si, ez e Si. Define f l and f 2 to be t h e smallest and largest points respectively in Ti.Since points of Si lie to the left of ,f, and t o the right of f 2 , e l f f l and e2 2 f 2 . Further, no points of Ti lie to the left of f l or to the right of f 2 , so that evidently Let b denote the fraction (possibly zero) such that bLi is the measure of that portion (if any) of Si contained in f 2 ] . Let a and c be nonnegative numbers such that aLi = f l  el and cLi = e2  fi.Since Si is contained in [el, e 2 ] , we have vl, Problem Analysis Further, there is a nonnegative number d such that In this section we derive the results presented in the previous section. The reader willing to accept the results may skip to f2 fl = L  L i + b L i + d . AIIE TRANSACTIONS, Volume 6 , No. 3 Downloaded by [Monash University Library] at 07:50 01 February 2015 Fig. 2a and 2b: Sketch of common end point layout with Si= Si U Si' U Sin, hoof Thus it follows that and u j=1 Sj = (U s;) U j=1 (US;') = Ti. j= 1 Suppose [7] does not hold; then (b+c1)Li+L+d<~L1/2. We now arrive at the following conclusion, based on [ 4 ] , 151, and [61. Lemma I If IS1, . . . ,SN)is a common end point layout with el E Si, e2 E Si, then there exist nonnegative numbers a, b, c, and d with [lo] I < a + b + c  2 , [ I 11 a + b + c  2<a+2b+c2, 1121 Li<(a+2b+c2)Li; [I31 0 <2d. [I 41 and so that further a+b+c 2 1 Adding [9], [ l o ], 1131 and [ I 41 gives such that Next we prove the main analytical result of this section. Lemma 2 Suppose nonnegative numbers a, b, c, and d are given such that a + b + c 2 1 , as well as positive numbers L 1 , Li, and L , with L1 2 Li. Then m a x [ ( a + b  l ) L i + L + d , ( b + c  l ) L i + L + d ]2 L  L 1 / 2 171 with equakty holding in [7] if and only if September 1974, MIE TRANSACTIONS Now if [7] does not hold then [9] and [ l o ] hold strictly, implying [16] holds strictly, which cannot be; hence [7] holds. Clearly, if the conditions [8] hold then [7] holds as an equality. Consider the case when [7] holds as an equality; then [9] and [lU] hold, so [16] holds and Li = Ll . Thus equality holds in [15] , and so 191 through [I41 must all hold as equalities. We then obtain d = 0 from [ 1 4 ] ,b = 0 from [ 1 2 ] ,a + c = 1 from [ I l l , and a = c from [9] and [I 01giving a =c= 112; thus the conditions 181 hold. 25 5 Using the foregoing analysis, we can completely characterize a minimax layout. Proposition In order for a linear layout {S1*, . . . ,SN* ) in HN(L) to be a minimax layout, it is necessary and sufficient that for some p for which 1 <p <N, T,*+U {Sj: 1 Sj<N,j#p}isanintervaloflengthLL,, S,* = s;* U S*: where S : and SE* are each intervals of length Lp/2 abutting the left and right end points respectively of T,*, and To establish sufficiency, we note that the layout IS1*, . . . , SN* ) SO defined is in HN(L) and satisfies [17]. Thus, by Remark 2, if {S1, . . . , SN)is any common end point linear layout, it suffices to show that Downloaded by [Monash University Library] at 07:50 01 February 2015 Proof smaller auxiliary problems are solved for N1 ,N2, . . . , 2 classes of objects, a minimax Iinear layout thus obtained, which is a solution to the original problem as well, has the objects ordered along the line as follows: 1,2, . . . ,N1, N. N1, . . . , 2, 1, with the length of each corresponding interval, except the central interval of length LN, equal to one half the length of the total interval for that class. Finally, we emphasize the fact that as with any layout model, the answers obtained should not be viewed as absolute answers, but as design guidelines. Acknowledgments This research was supported in part under AROD Contract No. DAAROD3112472G123, and NSF Grant GK41224. We wish to acknowledge the referee's very constructive comments. References to establish that {S1*, . . . , SN*(0 is a minimax layout, and [18] follows immediately on using Lemmas 1 and 2. To establish necessity, suppose {S1*, . . . ,SN* }inHN(L) is a minimax layout; it is then a common end point layout, and also satisfies Using Lemmas 1 and 2, we conclude that the parameters a, b, c, and d characterizing {S1*, . . , SN*}have the values a = c = 112, b = d = 0; further, using [7] , [8] and [19] , L1 = L, for some 1 S p < N. The conclusion now follows by referring to the interpretation of a, b, c, and d given prior to the statement of Lemma 1. . Conclusions In this note we have defined a linear layout, and defined an objective function for the layout which is, roughly speaking, the greatest distance between any two classes of objects in the layout. A minimax linear layout is a layout minimizing the objective function. We have found a minimax linear layout by obtaining a lower bound on the objective function, and then constructing a linear layout whose objective function value is equal to the lower bound; then we established that any minimax layout is essentially the same as that so constructed. The main analytical tool used was Lemma 2. We have also discussed why a linear layout may be of interest, and why a minimax objective function might be used. When there are more than two object classes to be laid out, there will always be alternative minimax layouts, so that it may be desirable to employ auxiliary criteria in choosing an appropriate minimax layout. The question of which auxiliary criteria are appropriate is very much a function of the context in which the layout problem occurs. For example, an auxiliary criterion might involvethedata on relative movement between some classes of objects, if available. Further, given Lk1 > Li, i = 2, . . . ,N, note that if ( 1 ) Elmaghraby, S. E., "The Sequencing of 'Related' Jobs," Naval Research Logistics Quarterly, 15, 1, 2332 (1968). ( 2 ) Francis, R. L., "Sufficient Conditions for Some OptimumProperty Facility Designs," Operations Research, 15, 3,448466 (MayJune 1967). ( 3 ) Hanan, M., and Kurtzberg, J. M., "A Review of the Placement and Quadratic Assignment Problems, SIAM Review, 14, 2 , 324342 (1972). ( 4 ) Karp, R. M., and Held, M., "FiniteState Processes and Dynamic Programming," SIAM Journal o f Applied Mathematics, 15, 3,693718 (1967). ( 5 ) Lowe, T. J., "Activity Assignment on the LineA Minisum Approach Involving Weighted MaximalDistances between Sets" Research Report No. 748, Department of Industrial and Svstems Engineering, The University of Florida, Gainesville , ~ i o r i d a3261 1. ( 6 ) Newman, D. J., "A Parking Lot Design," SZAM Review, 6, 1, 6266 (1964). ( 7 ) Papineau, R. L., and Francis, R. L., "A Minimax Planar Facility Layout Problem," Research Report No. 741,Department of Industrial and Systems Engineering, The University of Florida, Gainesville, Florida 3261 1. ( 8 ) Pierce, J. F., and Crowston, W. B., "TreeSearch Algorithms for Quadratic Assignment Problems," Naval Research Logistics Quarterly,l8,1, 136 (1971). ( 9 ) Simmons, D. M., "OneDimensional Space Allocation: An Ordering Algorithm," Operations Research,l7,5,81226 (1969). ( 1 0 ) Simmons, D. M., "A Further Note on OneDimensional Space Allocation," Operations Research, 19, 1,249 (1971). Dr. Robert L. Papineau is a professor in the Engineering De art ment of the Universitd du Quebec TroisRivihu, hoisr(ivi8rei Qudbec. A portion of this work is based on his PhD dissertation work at the University of Florida. He holds a BSME and MSME degrees from the UniversitB de Sherbrooke, and MSc and PhD degrees from the University of Florida. He is a registered professional engineer in the province of Qudbec, and a member of Alpha Pi Mu, AIIE, ORSA, and TIMS. Dr. Richard L. Francis is a professor in the Department of Industrial and Systems Engineering at the University of Florida. His research interests include facility design, location theory, and the application of optimization theory. He is coauthor with John A. White of Facility Layout and Location: An Analytical Approach. He holds a BSIE from Virginia Polytechnic Institute, an MSIE from Georgia Institute of Technology, and a PhD from Northwestern University. He is a member of AIIE, ASEE,ORSA, and TIMS, and is a Senior Editor of AIIE 77ansactions and on the Editorial Board of Operations Research. AIIE TRANSACTIONS, Volume 6, No. 3 I