The problem considered is the 12-department problem considered by Hillier [1] and by Nugent, Vollmann, and Ruml [2]. In line 561 through line 626 the computer program listed below uses the mathematical formulation appearing on page 6 of Heragu and Kusiak [3] and on page 140 of Heragu [4]. The plant shape is 3 by 4. The locations and the interdepartmental flows are given in Hillier [1] and Nugent et al. [2]. These flows are used in line 1321 through line 1374 of the computer program below.
The following computer program benefits from the computer programs of the present blog and the computer program of Conley [5, pp. 229-232].
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
43 FOR IOC=1 TO 24
45 B(IOC)=0
47 NEXT IOC
51 FOR IOCTT=1 TO 24
53 N(IOCTT)=5
57 NEXT IOCTT
61 FOR KLQ=1 TO 24
62 A(KLQ)=B(KLQ)+RND*(N(KLQ)-B(KLQ))
63 NEXT KLQ
71 FOR KLR=1 TO 24
72 H(KLR)=3
73 NEXT KLR
88 FOR JJJ=1 TO 1000 STEP 10
90 FOR INEW=1 TO 8
94 FOR J=INEW*2 TO 0 STEP -1
102 FOR JJ=0 TO 24
128 FOR I=1 TO 1
129 FOR KKQQ=1 TO 24
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
132 FOR K=1 TO 24
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*72)
307 FOR KLA1=1 TO KLPS
308 KLA2=FIX(1+24*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 24
364 X(I222)=FIX(X(I222))
368 NEXT I222
461 IF RND>.1 GOTO 561
465 IF RND<.5 THEN 471 ELSE 491
471 IOCT1=1+FIX(RND*12)
474 IOCT2=1+FIX(RND*12)
477 X(IOCT1)=A(IOCT2)
480 X(IOCT2)=A(IOCT1)
481 GOTO 561
491 IOCT6=13+FIX(RND*12)
494 IOCT7=13+FIX(RND*12)
497 X(IOCT6)=A(IOCT7)
500 X(IOCT7)=A(IOCT6)
561 P(11)=ABS(X(1)-X(2))+ABS(X(13)-X(14))-1
562 P(12)=ABS(X(1)-X(3))+ABS(X(13)-X(15))-1
563 P(13)=ABS(X(1)-X(4))+ABS(X(13)-X(16))-1
564 P(14)=ABS(X(1)-X(5))+ABS(X(13)-X(17))-1
565 P(15)=ABS(X(1)-X(6))+ABS(X(13)-X(18))-1
566 P(16)=ABS(X(1)-X(7))+ABS(X(13)-X(19))-1
567 P(17)=ABS(X(1)-X(8))+ABS(X(13)-X(20))-1
568 P(18)=ABS(X(1)-X(9))+ABS(X(13)-X(21))-1
569 P(19)=ABS(X(1)-X(10))+ABS(X(13)-X(22))-1
570 P(20)=ABS(X(1)-X(11))+ABS(X(13)-X(23))-1
571 P(21)=ABS(X(1)-X(12))+ABS(X(13)-X(24))-1
572 P(22)=ABS(X(2)-X(3))+ABS(X(14)-X(15))-1
573 P(23)=ABS(X(2)-X(4))+ABS(X(14)-X(16))-1
574 P(24)=ABS(X(2)-X(5))+ABS(X(14)-X(17))-1
575 P(25)=ABS(X(2)-X(6))+ABS(X(14)-X(18))-1
576 P(26)=ABS(X(2)-X(7))+ABS(X(14)-X(19))-1
577 P(27)=ABS(X(2)-X(8))+ABS(X(14)-X(20))-1
578 P(28)=ABS(X(2)-X(9))+ABS(X(14)-X(21))-1
579 P(29)=ABS(X(2)-X(10))+ABS(X(14)-X(22))-1
580 P(30)=ABS(X(2)-X(11))+ABS(X(14)-X(23))-1
581 P(31)=ABS(X(2)-X(12))+ABS(X(14)-X(24))-1
582 P(32)=ABS(X(3)-X(4))+ABS(X(15)-X(16))-1
583 P(33)=ABS(X(3)-X(5))+ABS(X(15)-X(17))-1
584 P(34)=ABS(X(3)-X(6))+ABS(X(15)-X(18))-1
585 P(35)=ABS(X(3)-X(7))+ABS(X(15)-X(19))-1
586 P(36)=ABS(X(3)-X(8))+ABS(X(15)-X(20))-1
587 P(37)=ABS(X(3)-X(9))+ABS(X(15)-X(21))-1
588 P(38)=ABS(X(3)-X(10))+ABS(X(15)-X(22))-1
589 P(39)=ABS(X(3)-X(11))+ABS(X(15)-X(23))-1
590 P(40)=ABS(X(3)-X(12))+ABS(X(15)-X(24))-1
591 P(41)=ABS(X(4)-X(5))+ABS(X(16)-X(17))-1
592 P(42)=ABS(X(4)-X(6))+ABS(X(16)-X(18))-1
593 P(43)=ABS(X(4)-X(7))+ABS(X(16)-X(19))-1
594 P(44)=ABS(X(4)-X(8))+ABS(X(16)-X(20))-1
595 P(45)=ABS(X(4)-X(9))+ABS(X(16)-X(21))-1
596 P(46)=ABS(X(4)-X(10))+ABS(X(16)-X(22))-1
597 P(47)=ABS(X(4)-X(11))+ABS(X(16)-X(23))-1
598 P(48)=ABS(X(4)-X(12))+ABS(X(16)-X(24))-1
599 P(49)=ABS(X(5)-X(6))+ABS(X(17)-X(18))-1
600 P(50)=ABS(X(5)-X(7))+ABS(X(17)-X(19))-1
601 P(51)=ABS(X(5)-X(8))+ABS(X(17)-X(20))-1
602 P(52)=ABS(X(5)-X(9))+ABS(X(17)-X(21))-1
603 P(53)=ABS(X(5)-X(10))+ABS(X(17)-X(22))-1
604 P(54)=ABS(X(5)-X(11))+ABS(X(17)-X(23))-1
605 P(55)=ABS(X(5)-X(12))+ABS(X(17)-X(24))-1
606 P(56)=ABS(X(6)-X(7))+ABS(X(18)-X(19))-1
607 P(57)=ABS(X(6)-X(8))+ABS(X(18)-X(20))-1
608 P(58)=ABS(X(6)-X(9))+ABS(X(18)-X(21))-1
609 P(59)=ABS(X(6)-X(10))+ABS(X(18)-X(22))-1
610 P(60)=ABS(X(6)-X(11))+ABS(X(18)-X(23))-1
611 P(61)=ABS(X(6)-X(12))+ABS(X(18)-X(24))-1
612 P(62)=ABS(X(7)-X(8))+ABS(X(19)-X(20))-1
613 P(63)=ABS(X(7)-X(9))+ABS(X(19)-X(21))-1
614 P(64)=ABS(X(7)-X(10))+ABS(X(19)-X(22))-1
615 P(65)=ABS(X(7)-X(11))+ABS(X(19)-X(23))-1
616 P(66)=ABS(X(7)-X(12))+ABS(X(19)-X(24))-1
617 P(67)=ABS(X(8)-X(9))+ABS(X(20)-X(21))-1
618 P(68)=ABS(X(8)-X(10))+ABS(X(20)-X(22))-1
619 P(69)=ABS(X(8)-X(11))+ABS(X(20)-X(23))-1
620 P(70)=ABS(X(8)-X(12))+ABS(X(20)-X(24))-1
621 P(71)=ABS(X(9)-X(10))+ABS(X(21)-X(22))-1
622 P(72)=ABS(X(9)-X(11))+ABS(X(21)-X(23))-1
623 P(73)=ABS(X(9)-X(12))+ABS(X(21)-X(24))-1
624 P(74)=ABS(X(10)-X(11))+ABS(X(22)-X(23))-1
625 P(75)=ABS(X(10)-X(12))+ABS(X(22)-X(24))-1
626 P(76)=ABS(X(11)-X(12))+ABS(X(23)-X(24))-1
788 FOR INSI=11 TO 76
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 76
1118 PSUM=PSUM+P(IOCT)
1121 NEXT IOCT
1131 PS1=99*555555!*PSUM
1321 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))
1322 P12B=0*ABS(X(1)-X(7))+6*ABS(X(1)-X(8))+2*ABS(X(1)-X(9))+1*ABS(X(1)-X(10))+1*ABS(X(1)-X(11))+1*ABS(X(1)-X(12))
1323 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))+2*ABS(X(2)-X(7))
1324 P14B=0*ABS(X(2)-X(8))+4*ABS(X(2)-X(9))+5*ABS(X(2)-X(10))+0*ABS(X(2)-X(11))+0*ABS(X(2)-X(12))
1325 P15B=0*ABS(X(3)-X(4))+0*ABS(X(3)-X(5))+0*ABS(X(3)-X(6))+0*ABS(X(3)-X(7))+5*ABS(X(3)-X(8))
1326 P16B=5*ABS(X(3)-X(9))+2*ABS(X(3)-X(10))+2*ABS(X(3)-X(11))+2*ABS(X(3)-X(12))
1327 P17B=5*ABS(X(4)-X(5))+2*ABS(X(4)-X(6))+2*ABS(X(4)-X(7))+10*ABS(X(4)-X(8))+0*ABS(X(4)-X(9))+0*ABS(X(4)-X(10))+5*ABS(X(4)-X(11))+5*ABS(X(4)-X(12))
1328 P18B=10*ABS(X(5)-X(6))+0*ABS(X(5)-X(7))+0*ABS(X(5)-X(8))+0*ABS(X(5)-X(9))+5*ABS(X(5)-X(10))+1*ABS(X(5)-X(11))+1*ABS(X(5)-X(12))
1329 P19B=5*ABS(X(6)-X(7))+1*ABS(X(6)-X(8))+1*ABS(X(6)-X(9))+5*ABS(X(6)-X(10))+4*ABS(X(6)-X(11))+0*ABS(X(6)-X(12))
1330 P20B=10*ABS(X(7)-X(8))+5*ABS(X(7)-X(9))+2*ABS(X(7)-X(10))+3*ABS(X(7)-X(11))+3*ABS(X(7)-X(12))
1331 P21B=0*ABS(X(8)-X(9))+0*ABS(X(8)-X(10))+5*ABS(X(8)-X(11))+0*ABS(X(8)-X(12))
1332 P22B=0*ABS(X(9)-X(10))+10*ABS(X(9)-X(11))+10*ABS(X(9)-X(12))
1333 P23B=5*ABS(X(10)-X(11))+0*ABS(X(10)-X(12))
1334 P24B=2*ABS(X(11)-X(12))
1351 P25B=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))
1352 P26B=0*ABS(X(13)-X(19))+6*ABS(X(13)-X(20))+2*ABS(X(13)-X(21))+1*ABS(X(13)-X(22))+1*ABS(X(13)-X(23))+1*ABS(X(13)-X(24))
1353 P27B=3*ABS(X(14)-X(15))+0*ABS(X(14)-X(16))+2*ABS(X(14)-X(17))+2*ABS(X(14)-X(18))+2*ABS(X(14)-X(19))
1354 P28B=0*ABS(X(14)-X(20))+4*ABS(X(14)-X(21))+5*ABS(X(14)-X(22))+0*ABS(X(14)-X(23))+0*ABS(X(14)-X(24))
1355 P29B=0*ABS(X(15)-X(16))+0*ABS(X(15)-X(17))+0*ABS(X(15)-X(18))+0*ABS(X(15)-X(19))+5*ABS(X(15)-X(20))
1356 P30B=5*ABS(X(15)-X(21))+2*ABS(X(15)-X(22))+2*ABS(X(15)-X(23))+2*ABS(X(15)-X(24))
1367 P31B=5*ABS(X(16)-X(17))+2*ABS(X(16)-X(18))+2*ABS(X(16)-X(19))+10*ABS(X(16)-X(20))+0*ABS(X(16)-X(21))+0*ABS(X(16)-X(22))+5*ABS(X(16)-X(23))+5*ABS(X(16)-X(24))
1368 P32B=10*ABS(X(17)-X(18))+0*ABS(X(17)-X(19))+0*ABS(X(17)-X(20))+0*ABS(X(17)-X(21))+5*ABS(X(17)-X(22))+1*ABS(X(17)-X(23))+1*ABS(X(17)-X(24))
1369 P33B=5*ABS(X(18)-X(19))+1*ABS(X(18)-X(20))+1*ABS(X(18)-X(21))+5*ABS(X(18)-X(22))+4*ABS(X(18)-X(23))+0*ABS(X(18)-X(24))
1370 P34B=10*ABS(X(19)-X(20))+5*ABS(X(19)-X(21))+2*ABS(X(19)-X(22))+3*ABS(X(19)-X(23))+3*ABS(X(19)-X(24))
1371 P35B=0*ABS(X(20)-X(21))+0*ABS(X(20)-X(22))+5*ABS(X(20)-X(23))+0*ABS(X(20)-X(24))
1372 P36B=0*ABS(X(21)-X(22))+10*ABS(X(21)-X(23))+10*ABS(X(21)-X(24))
1373 P37B=5*ABS(X(22)-X(23))+0*ABS(X(22)-X(24))
1374 P38B=2*ABS(X(23)-X(24))
1443 P1=P11B+P12B+P13B+P14B+P15B+P16B+P17B+P18B+P19B+P20B
1444 P2=P21B+P22B+P23B+P24B+P25B+P26B+P27B+P28B+P29B+P30B
1445 P3=P31B+P32B+P33B+P34B+P35B+P36B+P37B+P38B
1448 P4=P1+P2+P3
1450 P=-P4+PS1
1451 IF P<=M THEN 1670
1452 M=P
1453 PP1=P4
1454 FOR KLX=1 TO 24
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>-300 THEN 1916 ELSE 1999
1916 PRINT JJJJ,M,PP1
1917 PRINT A(1),A(2),A(3),A(4),A(5)
1918 PRINT A(6),A(7),A(8),A(9),A(10)
1920 PRINT A(11),A(12)
1922 PRINT A(13),A(14),A(15),A(16),A(17)
1924 PRINT A(18),A(19),A(20),A(21),A(22)
1926 PRINT A(23),A(24)
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and its output through JJJJ=-31968 (in compressed form and to be interpreted in accordance with line 1916 through line 1926; copied manually from the computer monitor) is presented below.
-31985 -295 295
0 2 2 0 2
1 1 0 1 2
1 0
1 1 0 3 3
3 2 2 0 2
1 0
-31974 -295 -295
0 0 0 3 3
2 2 2 1 1
1 1
1 0 2 1 0
0 2 1 2 0
1 3
-31968 -289 289
3 3 3 0 0
1 1 1 2 2
2 0
1 2 0 1 2
2 0 1 0 2
1 0
The best candidate solution above is at JJJJ=-31968 with the objective function value of 289.
The output above was obtained in 2.6 hours on a personal computer with an Intel 2.66 GHz. chip and the IBM interpreter, which is slower than the corresponding compiler.
References
[1] F.S. Hillier, Quantitative tools for plant layout analysis, J. Indust. Eng. 14 (1963) 33-40.
[2] 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.
[3] S.S. Heragu, A. Kusiak, Efficient models for the facility layut problem, European Journal of Operational Research 53 (1991) 1-13.
[4] S.S. Heragu, Recent models and techniques for solving the layout problem, European Journal of Operational Research 57 (1992) 136-144.
[5] W.C. Conley, Optimization: A Simplified Approach, Petrocelli, Princeton, New Jersey, 1981.
