Jsun Yui Wong
Adapting to the computer program in Wong [14], the following computer program seeks to solve a k-parallel row ordering problem (k-PROP) of 36 facilities. Each row of the 18 rows has 2 facilities. See Amaral [5]. The data for flows and lengths used here can be found in Yen [15, pages 101-105 for flows and page 106 for lengths]. One notes that these lengths are the lengths of C.4.6 STE36-8 in Yen [15, p. 106].
0 REM DEFDBL A-Z
1 DEFINT I, J, K, X
2 DIM B(99), N(99), A(2002), H(99), L(99), U(99), X(2002), D(111), P(111), PS(39), J44(2002), J(99), AA(99), HR(39), HHR(39), Y(39), C(39), CC(39), RA(99)
3 DIM HS(49, 49)
4 DIM PE(49, 49)
5 DIM SD(49, 49)
17 HR(1) = 4: HR(2) = 2: HR(3) = 3: HR(4) = 2: HR(5) = 3: HR(6) = 1: HR(7) = 3: HR(8) = 1: HR(9) = 3
18 HR(10) = 4: HR(11) = 5: HR(12) = 2: HR(13) = 2: HR(14) = 3: HR(15) = 3: HR(16) = 3: HR(17) = 5: HR(18) = 3: HR(19) = 3: HR(20) = 5
19 HR(21) = 2: HR(22) = 5: HR(23) = 3
20 HR(24) = 3: HR(25) = 5: HR(26) = 4: HR(27) = 4: HR(28) = 3: HR(29) = 4: HR(30) = 3
29 HR(31) = 2: HR(32) = 2: HR(33) = 3: HR(34) = 2: HR(35) = 5: HR(36) = 3
31 FOR IL = 1 TO 36
32 FOR JL = 1 TO 36
33 READ HS(IL, JL)
34 NEXT JL
35 NEXT IL
41 DATA 9999,0,0,2,1,7,9,0,4,75,7,12,22,7,1,0,0,0,0,23,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
42 DATA 0,9999,0,0,0,0,4,16,0,8,0,0,16,0,0,0,0,6,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
43 DATA 0,0,9999,0,0,4,16,20,0,0,0,0,20,0,0,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
44 DATA 2,0,0,9999,29,5,18,47,23,2,4,0,48,0,4,0,0,0,0,25,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
45 DATA 1,0,0,29,9999,18,12,25,0,0,4,0,25,0,3,0,0,0,0,18,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0
46 DATA 7,0,4,5,18,9999,4,2,0,1,23,2,19,0,0,0,0,0,2,19,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
47 DATA 9,4,16,18,12,4,9999,0,14,72,7,8,39,8,40,8,0,8,4,7,0,0,0,0,0,0,0,28,8,0,0,0,0,0,0,0
48 DATA 0,16,20,47,25,2,0,9999,10,71,2,0,0,0,0,0,0,41,0,0,0,0,0,0,0,0,7,8,0,0,0,0,0,0,0,0
49 DATA 4,0,0,23,0,0,14,10,9999,14,0,0,18,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
50 DATA 75,8,0,2,0,1,72,71,14,9999,11,1,17,0,1,0,0,17,0,15,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
51 DATA 7,0,0,4,4,23,7,2,0,11,9999,316,33,8,2,0,0,0,8,34,0,0,6,0,0,0,10,0,0,6,0,0,0,0,0,0
52 DATA 12,0,0,0,0,2,8,0,0,1,316,9999,157,25,4,0,0,1,0,0,0,0,0,0,22,0,1,0,0,0,0,0,0,0,0,0
53 DATA 22,16,20,48,25,19,39,0,18,17,33,157,9999,11,6,0,0,6,0,5,8,3,10,0,0,0,9,11,2,0,0,1,0,0,0,0
54 DATA 7,0,0,0,0,0,8,0,0,0,8,25,11,9999,3,0,0,1,1,21,0,1,0,2,0,0,5,0,0,3,2,5,5,4,0,0
55 DATA 1,0,0,4,3,0,40,0,0,1,2,4,6,3,9999,19,0,2,2,12,0,0,0,0,0,0,0,7,3,0,0,0,0,0,0,0
56 DATA 0,0,0,0,0,0,8,0,0,0,0,0,0,0,19,9999,0,6,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
57 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,9999,40,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
58 DATA 0,6,0,0,0,0,8,41,0,17,0,1,6,1,2,6,40,9999,0,26,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
59 DATA 0,0,0,0,0,2,4,0,0,0,8,0,0,1,2,0,0,0,9999,13,9,0,7,0,0,0,0,27,16,3,0,20,0,4,0,0
60 DATA 23,4,4,25,18,19,7,0,0,15,34,0,5,21,12,1,0,26,13,9999,11,4,36,0,0,0,16,18,9,10,1,28,6,2,0,0
61 DATA 0,0,0,0,0,0,0,0,0,0,0,0,8,0,0,0,0,0,9,11,9999,36,6,0,8,0,2,0,0,0,0,0,0,0,0,0
62 DATA 0,0,0,0,3,0,0,0,0,0,0,0,3,1,0,0,0,0,0,4,36,9999,0,0,0,0,4,0,0,0,0,0,0,0,0,0
63 DATA 0,0,0,0,0,0,0,0,0,0,6,0,10,0,0,0,0,0,7,36,6,0,9999,0,0,12,9,0,0,0,0,0,0,0,0,0
64 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,9999,26,0,5,0,0,0,0,0,0,0,0,0
65 DATA 0,0,0,0,0,0,0,0,0,0,0,22,0,0,0,0,0,0,0,0,8,0,0,26,9999,35,2,0,0,0,0,0,0,0,0,0
66 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,12,0,35,9999,4,0,0,0,0,0,0,0,0,0
67 DATA 0,0,0,0,0,0,0,7,0,0,10,1,9,5,0,0,0,0,0,16,2,4,9,5,2,4,9999,0,0,0,0,0,0,0,0,0
68 DATA 0,0,0,0,0,0,28,8,0,0,0,0,11,0,7,0,0,0,27,18,0,0,0,0,0,0,0,9999,10,22,4,6,4,12,0,0
69 DATA 0,0,0,0,0,0,8,0,0,0,0,0,2,0,3,0,0,0,16,9,0,0,0,0,0,0,0,10,9999,19,12,0,0,0,0,0
70 DATA 0,0,0,0,0,0,0,0,0,0,6,0,0,3,0,0,0,0,3,10,0,0,0,0,0,0,0,22,19,9999,19,4,5,8,0,0
71 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,1,0,0,0,0,0,0,0,4,12,19,9999,0,3,13,0,0
72 DATA 0,0,0,0,0,0,0,0,0,0,0,0,1,5,0,0,0,0,20,28,0,0,0,0,0,0,0,6,0,4,0,9999,18,24,0,0
73 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,0,0,0,0,6,0,0,0,0,0,0,0,4,0,5,3,18,9999,20,0,0
74 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,4,0,0,0,0,4,2,0,0,0,0,0,0,0,12,0,8,13,24,20,9999,0,0
75 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,9999,0
76 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,9999
88 FOR JJJJ = -32000 TO 32000
89 RANDOMIZE JJJJ
90 M = -1D+37
91 FOR J44 = 1 TO 36
93 A(J44) = J44
94 NEXT J44
128 FOR I = 1 TO 1000
129 FOR KKQQ = 1 TO 36
130 X(KKQQ) = A(KKQQ)
131 NEXT KKQQ
133 III = 1 + FIX(RND * 36)
134 JJJ = 1 + FIX(RND * 36)
137 X(III) = A(JJJ)
139 X(JJJ) = A(III)
231 FOR J44 = 1 TO 36
233 FOR J45 = 1 TO 36
234 IF X(J44) = J45 THEN HHR(J44) = HR(J44) ELSE GOTO 238
237 Y(J45) = J44
238 NEXT J45
244 FOR RN = 1 TO 18
251 FOR ISE20 = (RN - 1) * 2 + 1 TO RN * 2
254 C(ISE20) = .5 * HHR(Y(ISE20))
258 FOR ISE2000 = ISE20 + 1 TO RN * 2
259 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))
263 NEXT ISE2000
269 NEXT ISE20
299 NEXT RN
499 NEXT J44
551 FOR RN = 1 TO 18
601 FOR J77 = (RN - 1) * 2 + 1 TO RN * 2
605 IF X(J77) > RN * 2 THEN 1670
609 NEXT J77
610 NEXT RN
811 PROD = 0
812 FOR J44 = 1 TO 36
813 FOR J45 = J44 + 1 TO 36
814 PROD = PROD - HS(Y(J44), Y(J45)) * ABS(C(J44) - C(J45))
815 NEXT J45
816 NEXT J44
822 P = PROD
1111 IF P <= M THEN 1670
1452 M = P
1453 FOR KLX = 1 TO 36
1454 CC(KLX) = C(KLX)
1455 A(KLX) = X(KLX)
1456 NEXT KLX
1657 GOTO 128
1670 NEXT I
1889 REM IF M < -999999 THEN 1999
1891 PRINT A(1), A(2), A(3), A(4), A(5)
1892 PRINT A(6), A(7), A(8), A(9), A(10)
1893 PRINT A(11), A(12), A(13), A(14), A(15)
1894 PRINT A(16), A(17), A(18), A(19), A(20)
1896 PRINT A(21), A(22), A(23), A(24), A(25)
1897 PRINT A(26), A(27), A(28), A(29), A(30)
1898 PRINT A(31), A(32), A(33), A(34), A(35), A(36), M, JJJJ
1999 NEXT JJJJ
1999 NEXT JJJJ
This computer program was run with qb64v1000-win [13]. The complete output through JJJJ=-31996 is shown below:
2 1 4 3 6
5 8 7 9 10
12 11 13 14 16
15 17 18 19 20
21 22 24 23 25
26 27 28 29 30
32 31 33 34 35
36 -5032 -32000
2 1 3 4 6
5 8 7 9 10
11 12 14 13 16
15 17 18 19 20
22 21 23 24 26
25 27 28 29 30
32 31 33 34 36
35 -4844 -31999
2 1 3 4 6
5 8 7 9 10
11 12 14 13 16
15 17 18 19 20
22 21 23 24 26
25 27 28 29 30
32 31 33 34 35
36 -4844 -31998
2 1 3 4 6
5 7 8 9 10
11 12 14 13 16
15 17 18 19 20
22 21 23 24 26
25 27 28 29 30
32 31 33 34 35
36 -4920 -31997
2 1 3 4 6
5 7 8 9 10
12 11 13 14 15
16 17 18 19 20
21 22 24 23 25
26 27 28 29 30
32 31 33 34 35
36 -5230 -31996
Above there is no rounding by hand; it is just straight copying by hand from the monitor screen.
On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [13], the wall-clock time for obtaining the output through JJJJ=-31996 was 10 seconds.
Acknowledgment
I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.
References
[1] Andre R. S. Amaral (2006), On the Exact Solution of a Facility Layout Problem. European Journal of Operational Research 173 (2006), pp. 508-518.
[2] Andre R. S. Amaral (2008), An Exact Approach to the One-Dimensional Facility Layout Problem. Operations Research, Vol. 56, No. 4 (July-August, 2008), pp. 1026-1033.
[3] Andre R. S. Amaral (2011), Optimal Solutions for the Double Row Layout Problem. Optimization Letters, DOI 10.1007/s11590-011-0426-8, published on line 30 November 2011, Springer-Verlag 2011.
[4] Andre R. S. Amaral (2012), The Corridor Allocation Problem. Computers and Operations Research 39 (2012), pp. 3325-3330.
[5] Andre R. S. Amaral (2013), A Parallel Ordering Problem in Facilities Layout. Computers and Operations Research, Vol. 40, Issue 12, December 2013, pp. 2930-2939.
[6] Miguel F. Anjos, Anthony Vannelli, Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes. INFORMS Journal on Computing, Vol. 20, No. 4, Fall 2008, pp. 611-617.
[7] Miguel F. Anjos (2012), FLPLIB–Facility Layout Database. Retrieved on September 25 2012 from http://www.gerad.ca/files/Sites/Anjos/indexFR.html
[8] Miguel F. Anjos, FLPLIB–Facility Layout Database. http://www.miguelanjos.com.
[9] S. S. Heragu, A. Kusiak. Efficient Models for the Facility Layout Problem. European Journal of Operational Research 53 (1), 1991, pp. 1-13.
[10] Philipp Hungerlaender, Miguel F. Anjos (January 2012), A Semidefinite Optimization Approach to Free-Space Multi-Row Facility Layout. Les Cahiers du GERAD. Retrieved from http://www.gerad.ca/fichiers/cahiers/G-2012-03.pdf
[11] Microsoft Corp., BASIC, Second Edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C, Boca Raton, Florida 33432, 1981.
[12] C. E. Nugent, T. E Vollmann, J. Ruml (1968), An Experimental Comparison of Techniques for the Assignment of Facilities to Locations. Operations Research, Vol. 16, pp. 150-173.
[13] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64
[14] Jsun Yui Wong (2012, September 17). A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the Corridor Allocation Problem with Eleven Facilities, Third Edition. https://myblogsubstance.typepad.com/substance/2012/09/index.html/
[15] Ginger Yen (2008). Cutting-Plane Separation Strategies for Semidefinite Programming Models to Solve Single-Row Facility Layout Problems. A Master Thesis Presented to the University of Waterloo. UWSpace. http://hdl.handle.net/10012/4104.
No comments:
Post a Comment