This paper considers an extension to three dimensions of the formulation on page 6 of Heragu and Kusiak [1] and on page 140 of Heragu [2]. The specific problem used by the computer program listed here is a three-dimensional version of the 6-department problem of Nugent et al. [3]; the inter-departmental flows of the 6-department case of Nugent et al. [3, p. 168] are used in line 1238 through line 1349. The following computer program benefits from the computer program of Conley [4, pp. 229-232] and the computer programs of the present blog; its output is also presented here.
2 DEFINT I,J,K
5 DIM B(99),N(99),A(99),H(99),L(99),U(99),X(1111),D(111),P(222)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
44 FOR IO=1 TO 18
45 B(IO)=0
46 NEXT IO
51 FOR IOCTT=1 TO 18
53 N(IOCTT)=5
57 NEXT IOCTT
61 FOR KLQ=1 TO 18
62 A(KLQ)=B(KLQ)+RND*(N(KLQ)-B(KLQ))
63 NEXT KLQ
71 FOR KLR=1 TO 18
72 H(KLR)=3
73 NEXT KLR
88 FOR JJJ=1 TO 1000 STEP 10
90 FOR INEW=1 TO 2
94 FOR J=INEW*2 TO 0 STEP -1
102 FOR JJ=0 TO 18
128 FOR I=1 TO 1
129 FOR KKQQ=1 TO 18
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
132 FOR K=1 TO 18
133 IF RND<=.5 THEN 298 ELSE 230
230 IF A(K)-(N(K)-B(K))/H(K)^J
255 GOTO 265
260 L(K)=A(K)-(N(K)-B(K))/H(K)^J
265 IF A(K)+(N(K)-B(K))/H(K)^J>N(K) THEN 266 ELSE 268
266 U(K)=N(K)-L(K)
267 GOTO 272
268 U(K)=A(K)+(N(K)-B(K))/H(K)^J-L(K)
272 GOTO 300
298 X(K)=A(K)+2*RND*(2*RND-1)*(1/(1+RND*JJJ))*.05*A(K)
299 GOTO 302
300 X(K)=(L(K)+2*RND*RND*U(K))
302 NEXT K
304 X(JJ)=A(JJ)
306 KLPS=FIX(1+RND*54)
307 FOR KLA1=1 TO KLPS
308 KLA2=FIX(1+18*RND)
309 X(KLA2)=A(KLA2)
310 NEXT KLA1
343 IF RND>.1 GOTO 361
352 IF RND<=.9 THEN 353 ELSE 355
353 X(JJ)=B(JJ)
354 GOTO 361
355 X(JJ)=N(JJ)
361 FOR I222=1 TO 18
364 X(I222)=FIX(X(I222))
368 NEXT I222
461 IF RND>.1 GOTO 561
465 IF RND<1/3 THEN 471 ELSE IF RND<2/3 THEN 491 ELSE 521
471 IOCT1=1+FIX(RND*6)
474 IOCT2=1+FIX(RND*6)
477 X(IOCT1)=A(IOCT2)
480 X(IOCT2)=A(IOCT1)
481 GOTO 561
491 IOCT6=7+FIX(RND*6)
494 IOCT7=7+FIX(RND*6)
497 X(IOCT6)=A(IOCT7)
500 X(IOCT7)=A(IOCT6)
511 GOTO 561
521 IOCT13=13+FIX(RND*6)
524 IOCT14=13+FIX(RND*6)
537 X(IOCT13)=A(IOCT14)
540 X(IOCT14)=A(IOCT13)
561 P(11)=ABS(X(1)-X(2))+ABS(X(7)-X(8))+ABS(X(13)-X(14))-1
562 P(12)=ABS(X(1)-X(3))+ABS(X(7)-X(9))+ABS(X(13)-X(15))-1
563 P(13)=ABS(X(1)-X(4))+ABS(X(7)-X(10))+ABS(X(13)-X(16))-1
564 P(14)=ABS(X(1)-X(5))+ABS(X(7)-X(11))+ABS(X(13)-X(17))-1
565 P(15)=ABS(X(1)-X(6))+ABS(X(7)-X(12))+ABS(X(13)-X(18))-1
566 P(16)=ABS(X(2)-X(3))+ABS(X(8)-X(9))+ABS(X(14)-X(15))-1
567 P(17)=ABS(X(2)-X(4))+ABS(X(8)-X(10))+ABS(X(14)-X(16))-1
568 P(18)=ABS(X(2)-X(5))+ABS(X(8)-X(11))+ABS(X(14)-X(17))-1
569 P(19)=ABS(X(2)-X(6))+ABS(X(8)-X(12))+ABS(X(14)-X(18))-1
570 P(20)=ABS(X(3)-X(4))+ABS(X(9)-X(10))+ABS(X(15)-X(16))-1
571 P(21)=ABS(X(3)-X(5))+ABS(X(9)-X(11))+ABS(X(15)-X(17))-1
572 P(22)=ABS(X(3)-X(6))+ABS(X(9)-X(12))+ABS(X(15)-X(18))-1
573 P(23)=ABS(X(4)-X(5))+ABS(X(10)-X(11))+ABS(X(16)-X(17))-1
574 P(24)=ABS(X(4)-X(6))+ABS(X(10)-X(12))+ABS(X(16)-X(18))-1
575 P(25)=ABS(X(5)-X(6))+ABS(X(11)-X(12))+ABS(X(17)-X(18))-1
788 FOR INSI=11 TO 25
791 IF P(INSI)<0 THEN P(INSI)=P(INSI) ELSE P(INSI)=0
795 NEXT INSI
1111 PSUM=0
1115 FOR IOCT=11 TO 25
1118 PSUM=PSUM+P(IOCT)
1121 NEXT IOCT
1131 PS1=99*555555!*PSUM
1238 P11B=5*ABS(X(1)-X(2))+2*ABS(X(1)-X(3))+4*ABS(X(1)-X(4))+1*ABS(X(1)-X(5))+0*ABS(X(1)-X(6))
1239 P12B=5*ABS(X(7)-X(8))+2*ABS(X(7)-X(9))+4*ABS(X(7)-X(10))+1*ABS(X(7)-X(11))+0*ABS(X(7)-X(12))
1240 P13B=3*ABS(X(2)-X(3))+0*ABS(X(2)-X(4))+2*ABS(X(2)-X(5))+2*ABS(X(2)-X(6))
1241 P14B=3*ABS(X(8)-X(9))+0*ABS(X(8)-X(10))+2*ABS(X(8)-X(11))+2*ABS(X(8)-X(12))
1243 P15B=0*ABS(X(3)-X(4))+0*ABS(X(3)-X(5))+0*ABS(X(3)-X(6))
1244 P16B=0*ABS(X(9)-X(10))+0*ABS(X(9)-X(11))+0*ABS(X(9)-X(12))
1245 P17B=5*ABS(X(4)-X(5))+2*ABS(X(4)-X(6))
1246 P18B=5*ABS(X(10)-X(11))+2*ABS(X(10)-X(12))
1247 P19B=10*ABS(X(5)-X(6))
1248 P20B=10*ABS(X(11)-X(12))
1340 P21B=5*ABS(X(13)-X(14))+2*ABS(X(13)-X(15))+4*ABS(X(13)-X(16))+1*ABS(X(13)-X(17))+0*ABS(X(13)-X(18))
1342 P22B=3*ABS(X(14)-X(15))+0*ABS(X(14)-X(16))+2*ABS(X(14)-X(17))+2*ABS(X(14)-X(18))
1345 P23B=0*ABS(X(15)-X(16))+0*ABS(X(15)-X(17))+0*ABS(X(15)-X(18))
1347 P24B=5*ABS(X(16)-X(17))+2*ABS(X(16)-X(18))
1349 P25B=10*ABS(X(17)-X(18))
1445 p1=P11B+P12B+P13B+P14B+P15B+P16B+P17B+P18B+P19B+P20B+P21B+P22B+P23B+P24B+P25B
1447 P2=0
1448 P3=P1+P2
1450 P=-P3+PS1
1451 IF P<=M THEN 1670
1452 M=P
1453 PP1=P3
1454 FOR KLX=1 TO 18
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1457 GOTO 128
1670 NEXT I
1702 NEXT JJ
1706 NEXT J
1777 NEXT INEW
1888 NEXT JJJ
1890 IF M>-55 THEN 1916 ELSE 1999
1916 PRINT JJJJ,M,PP1
1917 PRINT A(1),A(2),A(3),A(4),A(5),A(6)
1918 PRINT A(7),A(8),A(9),A(10),A(11),A(12)
1920 PRINT A(13),A(14),A(15),A(16),A(17),A(18)
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the candidate solutions produced from JJJJ=-32000 through JJJJ=-31996 (in compressed form and to be interpreted in accordance with line 1916 through line 1920; copied manually from the computer monitor) are presented below.
-32000 -43 43
0 0 1 0 0
1
1 0 0 1 0
0
0 0 0 1 1
1
-31999 -43 43
0 0 0 0 0
0
0 1 1 0 1
2
1 1 2 0 0
0
-31998 -43 43
1 0 0 1 0
0
0 0 0 1 1
2
0 0 1 0 0
0
-31997 -43 43
0 0 1 0 0
1
1 0 0 1 0
0
1 1 1 0 0
0
-31996 -46 46
1 0 1 1 0
0
1 0 0 2 2
1
0 0 0 0 0
0
The best candidate solutions above are at JJJJ=-32000, -31999, -31998, and -31997 with 43 as the objective function value. The output above was obtained in 2 minutes on a personal computer with an Intel 2.66 GHz. chip and the IBM interpreter.
References
[1] S.S. Heragu, A. Kusiak, Efficient models for the facility layut problem, European Journal of Operational Research 53 (1991) 1-13.
[2] S.S. Heragu, Recent models and techniques for solving the layout problem, European Journal of Operational Research 57 (1992) 136-144.
[3] C.E. Nugent, T.E. Vollmann, J. Ruml, An experimental comparison of techniques for the assignment of facilities to locations, Operations Research 16 (1968) 150-173.
[4] W. C. Conley, Optimization: A Simplified Approach. Petrocelli, Princeton, New Jersey, 1981, pp. 229-232.
