Solving a Single-Row Facility Layout Problem of 30 Facilities of Heragu and Kusiak

Jsun Yui Wong

Adapting to the computer program in Wong [14], the following computer program seeks to solve the single-row facility layout problem of 30 facilities in Heragu and Kusiak [9, Page 9, Problem 8, Table 1].  The lengths are specified below in line 17 through line 30.  The 30x30 matrix of line 42 through line 71 below is based on a matrix in Nugent, Vollmann, and Ruml [12].

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(33), J44(2002), J(99), AA(99), HR(32), HHR(32), Y(33), C(33), CC(33)

3 DIM HS(49, 49)

4 DIM PE(49, 49)

5 DIM SD(49, 49)

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


18 HR(10) = 5: HR(11) = 3: HR(12) = 9: HR(13) = 3: HR(14) = 7: HR(15) = 3: HR(16) = 7: HR(17) = 5: HR(18) = 9: HR(19) = 6: HR(20) = 5


29 HR(21) = 3: HR(22) = 9: HR(23) = 3


30 HR(24) = 7: HR(25) = 3: HR(26) = 7: HR(27) = 5: HR(28) = 9: HR(29) = 6: HR(30) = 5


31 FOR IL = 1 TO 30

    32 FOR JL = 1 TO 30

        33 READ HS(IL, JL)

    34 NEXT JL

35 NEXT IL
36 REM

42 DATA 9999,3,2,0,0,2,10,5,0,5,2,5,0,0,2,0,5,6,3,0,1,10,0,10,2,1,1,1,0,1

43 DATA 3,9999,4,0,10,4,0,0,2,2,1,0,5,0,0,0,0,2,0,1,6,1,0,1,2,2,5,1,10,5

44 DATA 2,4,9999,3,4,0,5,5,5,1,4,1,0,4,0,4,0,6,3,2,5,5,2,1,0,0,3,1,0,2

45 DATA 0,0,3,9999,0,0,0,2,2,0,6,0,2,5,2,5,1,1,1,1,2,2,4,0,2,0,2,2,5,5

46 DATA 0,10,4,0,9999,5,2,0,0,0,0,2,0,0,0,0,2,1,0,0,2,0,5,1,0,2,1,0,2,1

47 DATA 2,4,0,0,5,9999,1,2,2,1,4,10,10,2,5,5,0,5,0,0,0,10,0,0,0,4,0,10,1,1

48 DATA 10,0,5,0,2,1,9999,10,10,5,10,10,6,0,0,10,2,1,10,1,5,5,2,3,5,0,2,0,1,3

49 DATA 5,0,5,2,0,2,10,9999,1,3,5,0,0,0,2,4,5,2,10,6,0,5,5,2,5,0,5,5,0,2

50 DATA 0,2,5,2,0,2,10,1,9999,10,2,1,5,2,0,3,0,2,0,0,4,0,5,2,0,5,2,2,5,2

51 DATA 5,2,1,0,0,1,5,3,10,9999,5,5,6,0,1,5,5,0,5,2,3,5,0,5,2,10,10,1,5,2

52 DATA 2,1,4,6,0,4,10,5,2,5,9999,0,0,1,2,1,0,2,0,0,0,6,6,0,4,5,3,2,2,10

53 DATA 5,0,1,0,2,10,10,0,1,5,0,9999,5,5,2,0,0,0,0,2,0,4,5,10,1,0,0,0,0,1

54 DATA 0,5,0,2,0,10,6,0,5,6,0,5,9999,2,0,4,2,2,1,0,6,2,1,5,5,0,0,1,5,5

55 DATA 0,0,4,5,0,2,0,0,2,0,1,5,2,9999,2,1,0,5,3,10,0,0,4,2,0,0,4,2,5,5

56 DATA 2,0,0,2,0,5,0,2,0,1,2,2,0,2,9999,4,5,1,0,1,0,5,0,2,0,0,5,1,1,0

57 DATA 0,0,4,5,0,5,10,4,3,5,1,0,4,1,4,9999,0,3,0,2,2,0,2,0,5,0,5,2,5,10

58 DATA 5,0,0,1,2,0,2,5,0,5,0,0,2,0,5,0,9999,2,2,0,0,0,6,5,3,5,0,0,5,1

59 DATA 6,2,6,1,1,5,1,2,2,0,2,0,2,5,1,3,2,9999,5,1,2,10,10,4,0,0,5,0,0,0

60 DATA 3,0,3,1,0,0,10,10,0,5,0,0,1,3,0,0,2,5,9999,0,5,5,1,0,5,2,1,2,10,10

61 DATA 0,1,2,1,0,0,1,6,0,2,0,2,0,10,1,2,0,1,0,9999,5,2,1,3,1,5,6,5,5,3

62 DATA 1,6,5,2,2,0,5,0,4,3,0,0,6,0,0,2,0,2,5,5,9999,4,0,1,0,0,0,5,0,0

63 DATA 10,1,5,2,0,10,5,5,0,5,6,4,2,0,5,0,0,10,5,2,4,9999,5,0,4,4,5,0,2,5

64 DATA 0,0,2,4,5,0,2,5,5,0,6,5,1,4,0,2,6,10,1,1,0,5,9999,0,4,4,1,0,2,2

65 DATA 10,1,1,0,1,0,3,2,2,5,0,10,5,2,2,0,5,4,0,3,1,0,0,9999,5,5,0,1,0,0

66 DATA 2,2,0,2,0,0,5,5,0,2,4,1,5,0,0,5,3,0,5,1,0,4,4,5,9999,1,0,10,1,0

67 DATA 1,2,0,0,2,4,0,0,5,10,5,0,0,0,0,0,5,0,2,5,0,4,4,5,1,9999,0,0,0,0

68 DATA 1,5,3,2,1,0,2,5,2,10,3,0,0,4,5,5,0,5,1,6,0,5,1,0,0,0,9999,0,0,10

69 DATA 1,1,1,2,0,10,0,5,2,1,2,0,1,2,1,2,0,0,2,5,5,0,0,1,10,0,0,9999,2,2

70 DATA 0,10,0,5,2,1,1,0,5,5,2,0,5,5,1,5,5,0,10,5,0,2,2,0,1,0,0,2,9999,2

71 DATA 1,5,2,5,1,1,3,2,2,2,10,1,5,5,0,10,1,0,10,3,0,5,2,0,0,0,10,2,2,9999


87 REM

88 FOR JJJJ = -32000 TO 32000


    89 RANDOMIZE JJJJ

    90 M = -1D+37

    91 FOR J44 = 1 TO 30

        93 A(J44) = J44

    94 NEXT J44


    111 IF RND < 1 / 4 THEN IMAX = 30 ELSE IF RND < 1 / 3 THEN IMAX = 30 ELSE IF RND < 1 / 2 THEN IMAX = 30 ELSE IMAX = 30


    128 FOR I = 1 TO 10000


        129 FOR KKQQ = 1 TO 30

            130 X(KKQQ) = A(KKQQ)

        131 NEXT KKQQ

        133 III = 1 + FIX(RND * 30)

        134 JJJ = 1 + FIX(RND * 30)

        137 X(III) = A(JJJ)

        139 X(JJJ) = A(III)

        231 FOR J44 = 1 TO 30

            233 FOR J45 = 1 TO 30

                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 IMAX

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

                258 FOR ISE2000 = ISE20 + 1 TO IMAX

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

                263 NEXT ISE2000

            269 NEXT ISE20

            386 FOR ISE20N = IMAX + 1 TO 30

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

                388 FOR ISE2000N = ISE20N + 1 TO 30

                    389 C(ISE20N) = C(ISE20N) + HHR(Y(ISE2000N))

                390 NEXT ISE2000N

            391 NEXT ISE20N

        395 NEXT J44

        401 FOR J77 = 1 TO 30


            405 IF X(J77) > 30 THEN 1670



        409 NEXT J77


        411 PROD = 0

        412 FOR J44 = 1 TO 30

            413 FOR J45 = J44 + 1 TO 30

                414 PROD = PROD - HS(Y(J44), Y(J45)) * ABS(C(J44) - C(J45))

            415 NEXT J45

        416 NEXT J44

        422 P = PROD

        1111 IF P <= M THEN 1670

        1452 M = P

        1453 FOR KLX = 1 TO 30

            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 < -44970 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)


    1929 PRINT M, JJJJ, A(1), A(2), A(3)

1999 NEXT JJJJ

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

10             1       18          29         2
6             17       25          15         14
19             4       13          28          8
22             7        9           24         27
16            11       12          5          20
3              21        30         26        23
-44965     -31886      10      1       18

10             1       18          29         2
6             17       25          15         14
19             4       13          28          8
22             7        9           24         27
16            11       12          5          20
3              21        30         26        23
-44965     -31710      10      1       18

10             1       18          29         2
6             17       25          15         14
19             4       13          28          8
22             7        9           24         27
16            11       12          5          20
3              21        30         26        23
-44965     -31705      10      1       18

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=-31705 was 38 minutes.

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 www.gerad.ca/files/Sites/Anjos/indexFR.html

[8] Miguel F. Anjos, FLPLIB--Facility Layout Database.  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 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/

Solving Another Instance of a Parallel Ordering Problem of 23-Facility Layout

Jsun Yui Wong

Adapting to the computer program in Wong [12], the following computer program seeks to solve the parallel row ordering problem (PROP) of 23 facilities with the first row of 4 facilities and the second row of 19 facilities in Amaral [5, p. 2938, Table A4].  The data can be found in Amaral [5] and Anjos [8].  This is the instance {P23_c, L n/5 ]}, Amaral [5, p. 2938].

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(33), J44(2002), J(99), AA(99), HR(32), HHR(32), Y(33), C(33), CC(33)

3 DIM HS(49, 49)

4 DIM PE(49, 49)

5 DIM SD(49, 49)

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


18 HR(10) = 5: HR(11) = 8: HR(12) = 12: HR(13) = 8: HR(14) = 11: HR(15) = 11: HR(16) = 8: HR(17) = 10: HR(18) = 6: HR(19) = 8: HR(20) = 14


29 HR(21) = 12: HR(22) = 8: HR(23) = 11


31 FOR IL = 1 TO 23

    32 FOR JL = 1 TO 23

        33 READ HS(IL, JL)

    34 NEXT JL

35 NEXT IL


42 DATA 9999,3,2,0,0,2,10,5,0,5,2,5,0,0,2,0,5,6,3,0,1,10,0


43 DATA 3,9999,4,0,10,4,0,0,2,2,1,0,5,0,0,0,0,2,0,1,6,1,0


44 DATA 2,4,9999,3,4,0,5,5,5,1,4,1,0,4,0,4,0,6,3,2,5,5,2


45 DATA 0,0,3,9999,0,0,0,2,2,0,6,0,2,5,2,5,1,1,1,1,2,2,4


46 DATA 0,10,4,0,9999,5,2,0,0,0,0,2,0,0,0,0,2,1,0,0,2,0,5


47 DATA 2,4,0,0,5,9999,1,2,2,1,4,10,10,2,5,5,0,5,0,0,0,10,0


48 DATA 10,0,5,0,2,1,9999,10,10,5,10,10,6,0,0,10,2,1,10,1,5,5,2


49 DATA 5,0,5,2,0,2,10,9999,1,3,5,0,0,0,2,4,5,2,10,6,0,5,5


50 DATA 0,2,5,2,0,2,10,1,9999,10,2,1,5,2,0,3,0,2,0,0,4,0,5


51 DATA 5,2,1,0,0,1,5,3,10,9999,5,5,6,0,1,5,5,0,5,2,3,5,0


52 DATA 2,1,4,6,0,4,10,5,2,5,9999,0,0,1,2,1,0,2,0,0,0,6,6


53 DATA 5,0,1,0,2,10,10,0,1,5,0,9999,5,5,2,0,0,0,0,2,0,4,5


54 DATA 0,5,0,2,0,10,6,0,5,6,0,5,9999,2,0,4,2,2,1,0,6,2,1


55 DATA 0,0,4,5,0,2,0,0,2,0,1,5,2,9999,2,1,0,5,3,10,0,0,4


56 DATA 2,0,0,2,0,5,0,2,0,1,2,2,0,2,9999,4,5,1,0,1,0,5,0


57 DATA 0,0,4,5,0,5,10,4,3,5,1,0,4,1,4,9999,0,3,0,2,2,0,2


58 DATA 5,0,0,1,2,0,2,5,0,5,0,0,2,0,5,0,9999,2,2,0,0,0,6


59 DATA 6,2,6,1,1,5,1,2,2,0,2,0,2,5,1,3,2,9999,5,1,2,10,10


60 DATA 3,0,3,1,0,0,10,10,0,5,0,0,1,3,0,0,2,5,9999,0,5,5,1


61 DATA 0,1,2,1,0,0,1,6,0,2,0,2,0,10,1,2,0,1,0,9999,5,2,1


62 DATA 1,6,5,2,2,0,5,0,4,3,0,0,6,0,0,2,0,2,5,5,9999,4,0


63 DATA 10,1,5,2,0,10,5,5,0,5,6,4,2,0,5,0,0,10,5,2,4,9999,5


64 DATA 0,0,2,4,5,0,2,5,5,0,6,5,1,4,0,2,6,10,1,1,0,5,9999


88 FOR JJJJ = -32000 TO 32033


    89 RANDOMIZE JJJJ

    90 M = -1D+37

    91 FOR J44 = 1 TO 23

        93 A(J44) = J44

    94 NEXT J44


    111 IF RND < 1 / 4 THEN IMAX = 4 ELSE IF RND < 1 / 3 THEN IMAX = 4 ELSE IF RND < 1 / 2 THEN IMAX = 4 ELSE IMAX = 4


    128 FOR I = 1 TO 5000


        129 FOR KKQQ = 1 TO 23

            130 X(KKQQ) = A(KKQQ)

        131 NEXT KKQQ

        133 III = 1 + FIX(RND * 23)

        134 JJJ = 1 + FIX(RND * 23)

        137 X(III) = A(JJJ)

        139 X(JJJ) = A(III)

        231 FOR J44 = 1 TO 23

            233 FOR J45 = 1 TO 23

                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 IMAX

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

                258 FOR ISE2000 = ISE20 + 1 TO IMAX

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

                263 NEXT ISE2000

            269 NEXT ISE20

            386 FOR ISE20N = IMAX + 1 TO 23

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

                388 FOR ISE2000N = ISE20N + 1 TO 23

                    389 C(ISE20N) = C(ISE20N) + HHR(Y(ISE2000N))

                390 NEXT ISE2000N

            391 NEXT ISE20N

        395 NEXT J44

        401 FOR J77 = 1 TO 4


            405 IF X(J77) > 4 THEN 1670


        409 NEXT J77


        411 PROD = 0

        412 FOR J44 = 1 TO 23

            413 FOR J45 = J44 + 1 TO 23

                414 PROD = PROD - HS(Y(J44), Y(J45)) * ABS(C(J44) - C(J45))

            415 NEXT J45

        416 NEXT J44

        422 P = PROD

        1111 IF P <= M THEN 1670

        1452 M = P

        1453 FOR KLX = 1 TO 23

            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 < -27563 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), A(21), A(22), A(23)

    1895 GOTO 1919

    1896 PRINT A(26), A(27), A(28), A(29), A(30)

    1905 PRINT CC(1), CC(2), CC(3), CC(4), CC(5)

    1906 PRINT CC(6), CC(7), CC(8), CC(9)

    1919 PRINT M, JJJJ, IIMAX, A(1), A(2)

1999 NEXT JJJJ

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

1        4         3         2        22
11      17      14         21      18
16      9        20         6        7
19      8        12        15       5
23      13      10
-27553         -31990       4       1      4

1          4          3          2         22
11       17         14       21        18
16        9        20        6        7
19        8         12         15         5
23        13         10
-27553           -31979         4        1        4

1       4        3       2        22
11     17       15         21       18
14       9       20       6       7
19       8        12        16        5
23       13        10
-27563         -31959        4        1        4

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 [11], the wall-clock time for obtaining the output through JJJJ=-31959 was 65 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 www.gerad.ca/files/Sites/Anjos/indexFR.html

[8] Miguel F. Anjos, FLPLIB--Facility Layout Database.  www.miguelanjos.com.

[9] Philipp Hungerlaender, Miguel F. Anjos (January 2012), A Semidefinite Optimization Approach to Free-Space Multi-Row Facility Layout.  Les Cahiers du GERAD.  Retrieved from www.gerad.ca/fichiers/cahiers/G-2012-03.pdf

[10] 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.

[11] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64

[12] 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/

Solving a Parallel Ordering Problem of 23-Facility Layout

Jsun Yui Wong

Adapting to the computer program in Wong [12], the following computer program seeks to solve the parallel row ordering problem (PROP) of 23 facilities with the first row of 4 facilities and the second row of 19 facilities from Amaral [5, p. 2938, Table A4].  The data can be found from Amaral [5] and Anjos [8].  This is the instance {P23_a, L n/5 ]}, Amaral [5, p. 2938].

0 REM DEFDBL A-Z

1 DEFINT I, J, K, X, A

2 DIM B(99), N(99), A(2002), H(99), L(99), U(99), X(2002), D(111), P(111), PS(33), J44(2002), J(99), AA(99), HR(32), HHR(32), Y(33), C(33), CC(33)

3 DIM HS(49, 49)

4 DIM PE(49, 49)

5 DIM SD(49, 49)

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


18 HR(10) = 5: HR(11) = 3: HR(12) = 9: HR(13) = 3: HR(14) = 7: HR(15) = 3: HR(16) = 7: HR(17) = 5: HR(18) = 9: HR(19) = 6: HR(20) = 5


29 HR(21) = 3: HR(22) = 9: HR(23) = 3


31 FOR IL = 1 TO 23

    32 FOR JL = 1 TO 23

        33 READ HS(IL, JL)

    34 NEXT JL

35 NEXT IL


42 DATA 9999,3,2,0,0,2,10,5,0,5,2,5,0,0,2,0,5,6,3,0,1,10,0


43 DATA 3,9999,4,0,10,4,0,0,2,2,1,0,5,0,0,0,0,2,0,1,6,1,0


44 DATA 2,4,9999,3,4,0,5,5,5,1,4,1,0,4,0,4,0,6,3,2,5,5,2


45 DATA 0,0,3,9999,0,0,0,2,2,0,6,0,2,5,2,5,1,1,1,1,2,2,4


46 DATA 0,10,4,0,9999,5,2,0,0,0,0,2,0,0,0,0,2,1,0,0,2,0,5


47 DATA 2,4,0,0,5,9999,1,2,2,1,4,10,10,2,5,5,0,5,0,0,0,10,0


48 DATA 10,0,5,0,2,1,9999,10,10,5,10,10,6,0,0,10,2,1,10,1,5,5,2


49 DATA 5,0,5,2,0,2,10,9999,1,3,5,0,0,0,2,4,5,2,10,6,0,5,5


50 DATA 0,2,5,2,0,2,10,1,9999,10,2,1,5,2,0,3,0,2,0,0,4,0,5


51 DATA 5,2,1,0,0,1,5,3,10,9999,5,5,6,0,1,5,5,0,5,2,3,5,0


52 DATA 2,1,4,6,0,4,10,5,2,5,9999,0,0,1,2,1,0,2,0,0,0,6,6


53 DATA 5,0,1,0,2,10,10,0,1,5,0,9999,5,5,2,0,0,0,0,2,0,4,5


54 DATA 0,5,0,2,0,10,6,0,5,6,0,5,9999,2,0,4,2,2,1,0,6,2,1


55 DATA 0,0,4,5,0,2,0,0,2,0,1,5,2,9999,2,1,0,5,3,10,0,0,4


56 DATA 2,0,0,2,0,5,0,2,0,1,2,2,0,2,9999,4,5,1,0,1,0,5,0


57 DATA 0,0,4,5,0,5,10,4,3,5,1,0,4,1,4,9999,0,3,0,2,2,0,2


58 DATA 5,0,0,1,2,0,2,5,0,5,0,0,2,0,5,0,9999,2,2,0,0,0,6



59 DATA 6,2,6,1,1,5,1,2,2,0,2,0,2,5,1,3,2,9999,5,1,2,10,10


60 DATA 3,0,3,1,0,0,10,10,0,5,0,0,1,3,0,0,2,5,9999,0,5,5,1


61 DATA 0,1,2,1,0,0,1,6,0,2,0,2,0,10,1,2,0,1,0,9999,5,2,1


62 DATA 1,6,5,2,2,0,5,0,4,3,0,0,6,0,0,2,0,2,5,5,9999,4,0


63 DATA 10,1,5,2,0,10,5,5,0,5,6,4,2,0,5,0,0,10,5,2,4,9999,5


64 DATA 0,0,2,4,5,0,2,5,5,0,6,5,1,4,0,2,6,10,1,1,0,5,9999


88 FOR JJJJ = -32000 TO 32000

    89 RANDOMIZE JJJJ

    90 M = -1D+37

    91 FOR J44 = 1 TO 23

        93 A(J44) = J44

    94 NEXT J44

    111 IF RND < 1 / 4 THEN IMAX = 4 ELSE IF RND < 1 / 3 THEN IMAX = 4 ELSE IF RND < 1 / 2 THEN IMAX = 4 ELSE IMAX = 4



    128 FOR I = 1 TO 5000



        129 FOR KKQQ = 1 TO 23

            130 X(KKQQ) = A(KKQQ)

        131 NEXT KKQQ

        133 III = 1 + FIX(RND * 23)

        134 JJJ = 1 + FIX(RND * 23)

        137 X(III) = A(JJJ)

        139 X(JJJ) = A(III)

        231 FOR J44 = 1 TO 23

            233 FOR J45 = 1 TO 23

                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 IMAX

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

                258 FOR ISE2000 = ISE20 + 1 TO IMAX

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

                263 NEXT ISE2000

            269 NEXT ISE20

            386 FOR ISE20N = IMAX + 1 TO 23

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

                388 FOR ISE2000N = ISE20N + 1 TO 23

                    389 C(ISE20N) = C(ISE20N) + HHR(Y(ISE2000N))

                390 NEXT ISE2000N

            391 NEXT ISE20N

        395 NEXT J44

        401 FOR J77 = 1 TO 4


            405 IF X(J77) > 4 THEN 1670


        409 NEXT J77


        411 PROD = 0

        412 FOR J44 = 1 TO 23

            413 FOR J45 = J44 + 1 TO 23

                414 PROD = PROD - HS(Y(J44), Y(J45)) * ABS(C(J44) - C(J45))

            415 NEXT J45

        416 NEXT J44

        422 P = PROD

        1111 IF P <= M THEN 1670

        1452 M = P

        1453 FOR KLX = 1 TO 23


            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 < -18730 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), A(21), A(22), A(23)

    1895 GOTO 1919

    1896 PRINT A(26), A(27), A(28), A(29), A(30)

    1905 PRINT CC(1), CC(2), CC(3), CC(4), CC(5)

    1906 PRINT CC(6), CC(7), CC(8), CC(9)

    1919 PRINT M, JJJJ, IIMAX, A(1), A(2)

1999 NEXT JJJJ

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

1       4      2       3        22
8      15     21     12      13
16      7     11      5        9
10      23    19     20      6
14      17     18
-18725      -31996     4     1     4

1     4     2        3     22
8    15    17     12     13
18    7    11      5       9
10    23    21     16     6
14    19    20
-18619      -31988      4     1     4

1      4      2       3     22
8     15     17     12   13
18     7     11      5      9
10    23    21     16     6
14    19    20
-18619      -31973      4     1     4

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 [11], the wall-clock time for obtaining the output through JJJJ=-31973 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.

[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 www.gerad.ca/files/Sites/Anjos/indexFR.html

[8] Miguel F. Anjos, FLPLIB--Facility Layout Database.  www.miguelanjos.com.

[9] Philipp Hungerlaender, Miguel F. Anjos (January 2012), A Semidefinite Optimization Approach to Free-Space Multi-Row Facility Layout.  Les Cahiers du GERAD.  Retrieved from www.gerad.ca/fichiers/cahiers/G-2012-03.pdf

[10] 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.

[11] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64

[12] 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/

Solving a Parallel Ordering Problem of 15-Facility Layout

Jsun Yui Wong

Adapting to the computer program in Wong [11], the following computer program seeks to solve the parallel row ordering problem (PROP) of 15 facilities with the first row of 7 facilities and the second row of 8 facilities from Amaral [5].          

One notes lines 401, 405, and 408, which are 401 FOR J55 = 1 TO 7, 405 IF X(J55) > 7 THEN GOTO 1670, and 408 NEXT J55.
     
0 REM DEFDBL A-Z
1 DEFINT I, J, K, X, A
2 DIM B(99), N(99), A(2002), H(99), L(99), U(99), X(2002), D(111), P(111), PS(33), J44(2002), J(99), AA(99), HR(32), HHR(32), Y(33), C(33), CC(33)
3 DIM HS(49, 49)
4 DIM PE(49, 49)
5 DIM SD(49, 49)
27 HR(1) = 20: HR(2) = 3: HR(3) = 9: HR(4) = 3: HR(5) = 7
28 REM   HR(6)=4:HR(7)=6:HR(8)=8:HR(9)=9
29 HR(6) = 3: HR(7) = 7: HR(8) = 5: HR(9) = 9: HR(10) = 6
30 HR(11) = 5: HR(12) = 3: HR(13) = 9: HR(14) = 3: HR(15) = 7
31 FOR IL = 1 TO 15
    32 FOR JL = 1 TO 15
        33 READ HS(IL, JL)
    34 NEXT JL
35 NEXT IL
61 DATA 999,10,0,5,1,0,1,2,2,2,2,0,4,0,0
62 DATA 10,999,1,3,2,2,2,3,2,0,2,0,10,5,0
63 DATA 0,1,999,10,2,0,2,5,4,5,2,2,5,5,5
64 DATA 5,3,10,999,1,1,5,0,0,2,1,0,2,5,0
66 DATA 1,2,2,1,999,3,5,5,5,1,0,3,0,5,5
67 DATA 0,2,0,1,3,999,2,2,1,5,0,0,2,5,10
68 DATA 1,2,2,5,5,2,999,6,0,1,5,5,5,1,0
69 DATA 2,3,5,0,5,2,6,999,5,2,10,0,5,0,0
70 DATA 2,2,4,0,5,1,0,5,999,0,10,5,10,0,2
71 DATA 2,0,5,2,1,5,1,2,0,999,0,4,0,0,5
72 DATA 2,2,2,1,0,0,5,10,10,0,999,5,0,5,0
73 DATA 0,0,2,0,3,0,5,0,5,4,3,999,3,3,0
74 DATA 4,10,5,2,0,2,5,5,10,0,0,3,999,10,2
75 DATA 0,5,5,5,5,5,1,0,0,0,5,3,10,999,4
76 DATA 0,0,5,0,5,10,0,0,2,5,0,0,2,4,999
78 FOR JJJJ = -32000 TO 32000
    79 RANDOMIZE JJJJ
    80 M = -1D+37
    81 FOR J44 = 1 TO 15
        83 A(J44) = J44
    84 NEXT J44
    111 IF RND < 1 / 4 THEN IMAX = 7 ELSE IF RND < 1 / 3 THEN IMAX = 7 ELSE IF RND < 1 / 2 THEN IMAX = 7 ELSE IMAX = 7

    126 REM IMAR=10+FIX(RND*1000)
    128 FOR I = 1 TO 500
        129 FOR KKQQ = 1 TO 15
            130 X(KKQQ) = A(KKQQ)
        131 NEXT KKQQ
        133 III = 1 + FIX(RND * 15)
        134 JJJ = 1 + FIX(RND * 15)
        221 X(III) = A(JJJ)
        223 X(JJJ) = A(III)
        231 FOR J44 = 1 TO 15
            233 FOR J45 = 1 TO 15
                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 IMAX
                254 C(ISE20) = .5 * HHR(Y(ISE20))
                258 FOR ISE2000 = ISE20 + 1 TO IMAX
                    259 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))
                263 NEXT ISE2000
            269 NEXT ISE20
            386 FOR ISE20N = IMAX + 1 TO 15
                387 C(ISE20N) = .5 * HHR(Y(ISE20N))
                388 FOR ISE2000N = ISE20N + 1 TO 15
                    389 C(ISE20N) = C(ISE20N) + HHR(Y(ISE2000N))
                390 NEXT ISE2000N
            391 NEXT ISE20N
        395 NEXT J44

        401 FOR J55 = 1 TO 7


            405 IF X(J55) > 7 THEN GOTO 1670


        408 NEXT J55

        411 PROD = 0
        412 FOR J44 = 1 TO 15
            413 FOR J45 = J44 + 1 TO 15
                414 PROD = PROD - HS(Y(J44), Y(J45)) * ABS(C(J44) - C(J45))
            415 NEXT J45
        416 NEXT J44
        422 P = PROD
        1111 IF P <= M THEN 1670
        1452 M = P
        1453 FOR KLX = 1 TO 15
            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 < -3555 THEN 1999

    1901 PRINT A(1), A(2), A(3), A(4), A(5)
    1902 PRINT A(6), A(7), A(8), A(9), A(10)
    1903 PRINT A(11), A(12), A(13), A(14), A(15)
    1905 REM PRINT CC(1), CC(2), CC(3), CC(4), CC(5)
    1906 REM PRINT CC(6), CC(7), CC(8), CC(9), CC(10)
    1907 REM PRINT CC(11), CC(12), CC(13), CC(14), CC(15)
    1919 PRINT M, JJJJ, IIMAX
1999 NEXT JJJJ

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

1     3     7     5     4
6     2     10    8    15
9    12     11      13     14
-3448      -32000        7

1     2     5     4    7
6     3    10     8    14
9      12      11    13     15
-3435     -31999      7

1    2     5     4    7
6    3    10     8    14
9      12      11    13     15
-3435     -31998      7

1    2     5    4    7
6    3    10    8    14
9      12      11    13     15
-3435     -31997      7

1     2    7    5    4
6     3     10    8    15
9    12     11      13     14
-3448      -31996        7

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 [10], the wall-clock time for obtaining the output through JJJJ=-31996 was 15 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 www.gerad.ca/files/Sites/Anjos/indexFR.html

[8] Philipp Hungerlaender, Miguel F. Anjos (January 2012), A Semidefinite Optimization Approach to Free-Space Multi-Row Facility Layout.  Les Cahiers du GERAD.  Retrieved from www.gerad.ca/fichiers/cahiers/G-2012-03.pdf

[9] 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.

[10] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64

[11] Jsun Yui Wong (2012, September 20).  A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the Corridor Allocation Problem with Fifteen Facilities, Fifth Edition. https://myblogsubstance.typepad.com/substance/2012/09/index.html/