Substance: May 2017

Solving a k-Parallel Row Ordering Problem in Layout of 36 Facilities in 6 Rows, Short Edition

Jsun Yui Wong

The computer program here is much shorter than the computer program of the preceding paper mainly because of line 244 and line 455 of the following computer program.

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

29 HR(21) = 2: HR(22) = 5: HR(23) = 3

30 HR(24) = 3: HR(25) = 5: HR(26) = 4: HR(27) = 4: HR(28) = 3: HR(29) = 4: HR(30) = 3

31 HR(31) = 2: HR(32) = 2: HR(33) = 3: HR(34) = 2: HR(35) = 5: HR(36) = 3

32 FOR IL = 1 TO 36

33 FOR JL = 1 TO 36
34 READ HS(IL, JL)

35 NEXT JL

36 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 10000

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 6

253 FOR ISE20 = (RN - 1) * 6 + 1 TO RN * 6

254 C(ISE20) = .5 * HHR(Y(ISE20))

258 FOR ISE2000 = ISE20 + 1 TO RN * 6

259 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

263 NEXT ISE2000

269 NEXT ISE20

355 NEXT RN

499 NEXT J44

455 FOR RN = 1 TO 6

601 FOR J77 = (RN - 1) * 6 + 1 TO RN * 6

605 IF X(J77) > RN * 6 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 IF M < -9160 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

This computer program was run with qb64v1000-win [13]. The complete output through JJJJ=-31864 is shown below:

5 4 6 3 2
1 9 10 12 11
7 8 15 14 16
13 18 17 22 21
23 24 20 19 26
25 27 28 30 29
35 33 32 34 36
31 -9160 -31949

5 4 6 3 2
1 9 10 12 11
7 8 15 14 16
13 18 17 22 21
23 24 20 19 26
25 27 28 30 29
35 33 32 34 36
31 -9160 -31902

5 4 6 3 2
1 9 10 12 11
7 8 15 14 16
13 18 17 22 21
23 24 20 19 26
25 27 28 30 29
35 33 32 34 36
31 -9160 -31864

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=-31864 was 7 minutes and forty 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.

Posted at 05:03 PM | Permalink | Comments (0)

Solving a k-Parallel Row Ordering Problem in Layout of 36 Facilities in 6 Rows

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 6 rows has 6 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

29 HR(21) = 2: HR(22) = 5: HR(23) = 3

30 HR(24) = 3: HR(25) = 5: HR(26) = 4: HR(27) = 4: HR(28) = 3: HR(29) = 4: HR(30) = 3

31 HR(31) = 2: HR(32) = 2: HR(33) = 3: HR(34) = 2: HR(35) = 5: HR(36) = 3

32 FOR IL = 1 TO 36

33 FOR JL = 1 TO 36
34 READ HS(IL, JL)

35 NEXT JL

36 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
121 REM IF RND < 1 / 4 THEN IMAX = 17 ELSE IF RND < 1 / 3 THEN IMAX = 17 ELSE IF RND < 1 / 2 THEN IMAX = 17 ELSE IMAX = 17

128 FOR I = 1 TO 10000
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
253 FOR ISE20 = 1 TO 6

254 C(ISE20) = .5 * HHR(Y(ISE20))

258 FOR ISE2000 = ISE20 + 1 TO 6

259 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

263 NEXT ISE2000

269 NEXT ISE20

386 FOR ISE20 = 7 TO 12

387 C(ISE20) = .5 * HHR(Y(ISE20))

388 FOR ISE2000 = ISE20 + 1 TO 12

389 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

390 NEXT ISE2000

391 NEXT ISE20
396 FOR ISE20 = 13 TO 18

397 C(ISE20) = .5 * HHR(Y(ISE20))

398 FOR ISE2000 = ISE20 + 1 TO 18

399 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

400 NEXT ISE2000

401 NEXT ISE20

403 FOR ISE20 = 19 TO 24
404 C(ISE20) = .5 * HHR(Y(ISE20))

405 FOR ISE2000 = ISE20 + 1 TO 24

406 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

407 NEXT ISE2000

408 NEXT ISE20
413 FOR ISE20 = 25 TO 30
414 C(ISE20) = .5 * HHR(Y(ISE20))

415 FOR ISE2000 = ISE20 + 1 TO 30

416 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

417 NEXT ISE2000

418 NEXT ISE20

423 FOR ISE20 = 31 TO 36
424 C(ISE20) = .5 * HHR(Y(ISE20))

425 FOR ISE2000 = ISE20 + 1 TO 36

426 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

427 NEXT ISE2000

428 NEXT ISE20

499 NEXT J44

601 FOR J77 = 1 TO 6
605 IF X(J77) > 6 THEN 1670
609 NEXT J77

611 FOR J77 = 7 TO 12
615 IF X(J77) > 12 THEN 1670
619 NEXT J77

621 FOR J77 = 13 TO 18
622 IF X(J77) > 18 THEN 1670
629 NEXT J77

631 FOR J77 = 19 TO 24

635 IF X(J77) > 24 THEN 1670
639 NEXT J77

641 FOR J77 = 25 TO 30

645 IF X(J77) > 30 THEN 1670
649 NEXT J77
651 FOR J77 = 31 TO 36

655 IF X(J77) > 36 THEN 1670
659 NEXT J77
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

1559 IIMAX = IMAX

1657 GOTO 128

1670 NEXT I

1889 IF M < -9200 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

This computer program was run with qb64v1000-win [13]. The complete output through JJJJ=-31864 is shown below:

5 4 6 3 2
1 9 10 12 11
7 8 15 14 16
13 18 17 22 21
23 24 20 19 26
25 27 28 30 29
35 33 32 34 36
31 -9160 -31949

5 4 6 3 2
1 9 10 12 11
7 8 15 14 16
13 18 17 22 21
23 24 20 19 26
25 27 28 30 29
35 33 32 34 36
31 -9160 -31902

5 4 6 3 2
1 9 10 12 11
7 8 15 14 16
13 18 17 22 21
23 24 20 19 26
25 27 28 30 29
35 33 32 34 36
31 -9160 -31864

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=-31864 was 7 minutes and 20 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.

Posted at 01:06 AM | Permalink | Comments (0)

Solving a k-Parallel Row Ordering Problem in Layout of 36 Facilities in 9 Rows

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 9 rows has 4 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

29 HR(21) = 2: HR(22) = 5: HR(23) = 3

30 HR(24) = 3: HR(25) = 5: HR(26) = 4: HR(27) = 4: HR(28) = 3: HR(29) = 4: HR(30) = 3

31 HR(31) = 2: HR(32) = 2: HR(33) = 3: HR(34) = 2: HR(35) = 5: HR(36) = 3

33 FOR IL = 1 TO 36

34 FOR JL = 1 TO 36

35 READ HS(IL, JL)

36 NEXT JL

37 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 10000

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
253 FOR ISE20 = 1 TO 4

254 C(ISE20) = .5 * HHR(Y(ISE20))

258 FOR ISE2000 = ISE20 + 1 TO 4

259 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

263 NEXT ISE2000

269 NEXT ISE20

386 FOR ISE20 = 5 TO 8

387 C(ISE20) = .5 * HHR(Y(ISE20))

388 FOR ISE2000 = ISE20 + 1 TO 8

389 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

390 NEXT ISE2000

391 NEXT ISE20

396 FOR ISE20 = 9 TO 12

397 C(ISE20) = .5 * HHR(Y(ISE20))

398 FOR ISE2000 = ISE20 + 1 TO 12

399 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

400 NEXT ISE2000

401 NEXT ISE20

403 FOR ISE20 = 13 TO 16

404 C(ISE20) = .5 * HHR(Y(ISE20))

405 FOR ISE2000 = ISE20 + 1 TO 16

406 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

407 NEXT ISE2000

408 NEXT ISE20
413 FOR ISE20 = 17 TO 20

414 C(ISE20) = .5 * HHR(Y(ISE20))

415 FOR ISE2000 = ISE20 + 1 TO 20

416 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

417 NEXT ISE2000

418 NEXT ISE20

423 FOR ISE20 = 21 TO 24

424 C(ISE20) = .5 * HHR(Y(ISE20))

425 FOR ISE2000 = ISE20 + 1 TO 24

426 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

427 NEXT ISE2000

428 NEXT ISE20

433 FOR ISE20 = 25 TO 28

434 C(ISE20) = .5 * HHR(Y(ISE20))

435 FOR ISE2000 = ISE20 + 1 TO 28

436 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

437 NEXT ISE2000

438 NEXT ISE20

443 FOR ISE20 = 29 TO 32

444 C(ISE20) = .5 * HHR(Y(ISE20))

445 FOR ISE2000 = ISE20 + 1 TO 32

446 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

447 NEXT ISE2000

448 NEXT ISE20

453 FOR ISE20 = 33 TO 36

454 C(ISE20) = .5 * HHR(Y(ISE20))

455 FOR ISE2000 = ISE20 + 1 TO 36

456 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

457 NEXT ISE2000

458 NEXT ISE20

499 NEXT J44

601 FOR J77 = 1 TO 4

605 IF X(J77) > 4 THEN 1670

609 NEXT J77

611 FOR J77 = 5 TO 8

615 IF X(J77) > 8 THEN 1670

619 NEXT J77

621 FOR J77 = 9 TO 12

622 IF X(J77) > 12 THEN 1670

629 NEXT J77

631 FOR J77 = 13 TO 16

635 IF X(J77) > 16 THEN 1670

639 NEXT J77

641 FOR J77 = 17 TO 20

645 IF X(J77) > 20 THEN 1670

649 NEXT J77
651 FOR J77 = 21 TO 24

655 IF X(J77) > 24 THEN 1670

659 NEXT J77

671 FOR J77 = 25 TO 28

675 IF X(J77) > 28 THEN 1670

679 NEXT J77

681 FOR J77 = 29 TO 32

685 IF X(J77) > 32 THEN 1670

689 NEXT J77

691 FOR J77 = 33 TO 36

695 IF X(J77) > 36 THEN 1670

699 NEXT J77

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

1559 IIMAX = IMAX

1657 GOTO 128

1670 NEXT I

1889 IF M < -7440 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

This computer program was run with qb64v1000-win [13]. The complete output through JJJJ=-31990 is shown below:

1 2 4 3 8
7 6 5 9 10
12 11 15 16 14
13 17 18 19 20
23 22 24 21 26
25 28 27 29 30
32 31 36 35 34
33 -7435 -31999

1 2 4 3 8
7 6 5 9 10
12 11 15 16 14
13 17 18 19 20
23 22 24 21 26
25 28 27 29 30
32 31 36 35 33
34 -7435 -31996

1 2 4 3 8
7 6 5 9 10
12 11 15 16 14
13 17 18 19 20
23 22 24 21 26
25 28 27 29 30
32 31 36 35 33
34 -7435 -31990

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=-31990 was 40 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.

Posted at 12:11 PM | Permalink | Comments (0)

Solving a k-Parallel Row Ordering Problem in Facility Layout of 36 Facilities in 12 Rows

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 12 rows has 3 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].

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)

9 HR(31) = 2: HR(32) = 2: HR(33) = 2: HR(34) = 1: HR(35) = 2: HR(36) = 2

17 HR(1) = 2: HR(2) = 1: HR(3) = 2: HR(4) = 1: HR(5) = 2: HR(6) = 3: HR(7) = 2: HR(8) = 2: HR(9) = 2

18 HR(10) = 2: HR(11) = 2: HR(12) = 2: HR(13) = 3: HR(14) = 2: HR(15) = 3: HR(16) = 3: HR(17) = 2: HR(18) = 2: HR(19) = 2: HR(20) = 2

29 HR(21) = 2: HR(22) = 2: HR(23) = 1

30 HR(24) = 3: HR(25) = 2: HR(26) = 2: HR(27) = 2: HR(28) = 1: HR(29) = 2: HR(30) = 2

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

121 REM IF RND < 1 / 4 THEN IMAX = 17 ELSE IF RND < 1 / 3 THEN IMAX = 17 ELSE IF RND < 1 / 2 THEN IMAX = 17 ELSE IMAX = 17

128 FOR I = 1 TO 10000

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
253 FOR ISE20 = 1 TO 3

254 C(ISE20) = .5 * HHR(Y(ISE20))

258 FOR ISE2000 = ISE20 + 1 TO 3

259 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

263 NEXT ISE2000

269 NEXT ISE20

386 FOR ISE20 = 4 TO 6

387 C(ISE20) = .5 * HHR(Y(ISE20))

388 FOR ISE2000 = ISE20 + 1 TO 6

389 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

390 NEXT ISE2000

391 NEXT ISE20

396 FOR ISE20 = 7 TO 9

397 C(ISE20) = .5 * HHR(Y(ISE20))

398 FOR ISE2000 = ISE20 + 1 TO 9

399 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

400 NEXT ISE2000

401 NEXT ISE20

403 FOR ISE20 = 10 TO 12

404 C(ISE20) = .5 * HHR(Y(ISE20))

405 FOR ISE2000 = ISE20 + 1 TO 12

406 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

407 NEXT ISE2000

408 NEXT ISE20
413 FOR ISE20 = 13 TO 15

414 C(ISE20) = .5 * HHR(Y(ISE20))

415 FOR ISE2000 = ISE20 + 1 TO 15

416 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

417 NEXT ISE2000

418 NEXT ISE20

423 FOR ISE20 = 16 TO 18

424 C(ISE20) = .5 * HHR(Y(ISE20))

425 FOR ISE2000 = ISE20 + 1 TO 18

426 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

427 NEXT ISE2000

428 NEXT ISE20

433 FOR ISE20 = 19 TO 21

434 C(ISE20) = .5 * HHR(Y(ISE20))

435 FOR ISE2000 = ISE20 + 1 TO 21

436 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

437 NEXT ISE2000

438 NEXT ISE20

443 FOR ISE20 = 22 TO 24

444 C(ISE20) = .5 * HHR(Y(ISE20))

445 FOR ISE2000 = ISE20 + 1 TO 24

446 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

447 NEXT ISE2000

448 NEXT ISE20

453 FOR ISE20 = 25 TO 27

454 C(ISE20) = .5 * HHR(Y(ISE20))

455 FOR ISE2000 = ISE20 + 1 TO 27

456 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

457 NEXT ISE2000

458 NEXT ISE20

461 FOR ISE20 = 28 TO 30

462 C(ISE20) = .5 * HHR(Y(ISE20))

463 FOR ISE2000 = ISE20 + 1 TO 30

464 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

465 NEXT ISE2000

466 NEXT ISE20

471 FOR ISE20 = 31 TO 33

472 C(ISE20) = .5 * HHR(Y(ISE20))

473 FOR ISE2000 = ISE20 + 1 TO 33

474 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

475 NEXT ISE2000

476 NEXT ISE20

481 FOR ISE20 = 34 TO 36

482 C(ISE20) = .5 * HHR(Y(ISE20))

483 FOR ISE2000 = ISE20 + 1 TO 36

484 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))

485 NEXT ISE2000

486 NEXT ISE20

499 NEXT J44

601 FOR J77 = 1 TO 3

605 IF X(J77) > 3 THEN 1670

609 NEXT J77

611 FOR J77 = 4 TO 6

615 IF X(J77) > 6 THEN 1670

619 NEXT J77

621 FOR J77 = 7 TO 9

622 IF X(J77) > 9 THEN 1670

629 NEXT J77

631 FOR J77 = 10 TO 12

635 IF X(J77) > 12 THEN 1670

639 NEXT J77

641 FOR J77 = 13 TO 15

645 IF X(J77) > 15 THEN 1670

649 NEXT J77
651 FOR J77 = 16 TO 18

655 IF X(J77) > 18 THEN 1670

659 NEXT J77

671 FOR J77 = 19 TO 21

675 IF X(J77) > 21 THEN 1670

679 NEXT J77

681 FOR J77 = 22 TO 24

685 IF X(J77) > 24 THEN 1670

689 NEXT J77

691 FOR J77 = 25 TO 27

695 IF X(J77) > 27 THEN 1670

699 NEXT J77

711 FOR J77 = 28 TO 30

714 IF X(J77) > 30 THEN 1670

715 NEXT J77

722 FOR J77 = 31 TO 33

723 IF X(J77) > 33 THEN 1670

724 NEXT J77

731 FOR J77 = 34 TO 36

732 IF X(J77) > 36 THEN 1670

733 NEXT J77

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

1559 IIMAX = IMAX

1657 GOTO 128

1670 NEXT I

1889 IF M < -4010 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

This computer program was run with qb64v1000-win [13]. The complete output through JJJJ=-31975 is shown below:

1 2 3 5 4
6 7 8 9 10
12 11 14 15 13
16 18 17 21 20
19 22 23 24 26
25 27 29 28 30
33 32 31 35 34
36 -4004.5 -31999

1 2 3 5 4
6 7 8 9 10
12 11 14 15 13
16 18 17 21 20
19 22 23 24 26
25 27 29 28 30
33 32 31 35 34
36 -4004.5 -31982

1 2 3 5 4
6 7 8 9 10
12 11 14 15 13
16 18 17 21 20
19 22 23 24 26
25 27 29 28 30
33 32 31 35 34
36 -4004.5 -31975

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=-31975 was one minute.

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.