Jsun Yui Wong
The computer program listed below seeks to solve the 12-department problem in Hillier (1963) and in Nugent, Vollmann, and Ruml (1968).
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(166),A(166),L(166),K(166),P(166),B(166),S(166)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 12
113 A(K)=FIX(RND*5)
115 NEXT K
117 FOR KKK=13 TO 24
118 A(KKK)=FIX(RND*3)
119 NEXT KKK
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 24
131 X(KK)=A(KK)
132 NEXT KK
139 IF RND<.5 GOTO 222 ELSE 330
222 IJL=1+FIX(RND*12)
234 X(IJL)=FIX(RND*5)
242 IJM=13+FIX(RND*12)
244 X(IJM)=FIX(RND*3)
246 GOTO 501
330 IJM=1+FIX(RND*12)
331 IJN=1+FIX(RND*12)
333 X(IJM)=A(IJN):X(IJN)=A(IJM)
335 X(IJM+12)=A(IJN+12):X(IJN+12)=A(IJM+12)
501 B(1)=ABS(X(1)-X(2))+ABS(X(13)-X(14))
502 B(2)=ABS(X(1)-X(3))+ABS(X(13)-X(15))
503 B(3)=ABS(X(1)-X(4))+ABS(X(13)-X(16))
504 B(4)=ABS(X(1)-X(5))+ABS(X(13)-X(17))
505 B(5)=ABS(X(1)-X(6))+ABS(X(13)-X(18))
506 B(6)=ABS(X(1)-X(7))+ABS(X(13)-X(19))
507 B(7)=ABS(X(1)-X(8))+ABS(X(13)-X(20))
508 B(8)=ABS(X(1)-X(9))+ABS(X(13)-X(21))
509 B(9)=ABS(X(1)-X(10))+ABS(X(13)-X(22))
510 B(10)=ABS(X(1)-X(11))+ABS(X(13)-X(23))
511 B(11)=ABS(X(1)-X(12))+ABS(X(13)-X(24))
512 B(12)=ABS(X(2)-X(3))+ABS(X(14)-X(15))
513 B(13)=ABS(X(2)-X(4))+ABS(X(14)-X(16))
514 B(14)=ABS(X(2)-X(5))+ABS(X(14)-X(17))
515 B(15)=ABS(X(2)-X(6))+ABS(X(14)-X(18))
516 B(16)=ABS(X(2)-X(7))+ABS(X(14)-X(19))
517 B(17)=ABS(X(2)-X(8))+ABS(X(14)-X(20))
518 B(18)=ABS(X(2)-X(9))+ABS(X(14)-X(21))
519 B(19)=ABS(X(2)-X(10))+ABS(X(14)-X(22))
520 B(20)=ABS(X(2)-X(11))+ABS(X(14)-X(23))
521 B(21)=ABS(X(2)-X(12))+ABS(X(14)-X(24))
522 B(22)=ABS(X(3)-X(4))+ABS(X(15)-X(16))
523 B(23)=ABS(X(3)-X(5))+ABS(X(15)-X(17))
524 B(24)=ABS(X(3)-X(6))+ABS(X(15)-X(18))
525 B(25)=ABS(X(3)-X(7))+ABS(X(15)-X(19))
526 B(26)=ABS(X(3)-X(8))+ABS(X(15)-X(20))
527 B(27)=ABS(X(3)-X(9))+ABS(X(15)-X(21))
528 B(28)=ABS(X(3)-X(10))+ABS(X(15)-X(22))
529 B(29)=ABS(X(3)-X(11))+ABS(X(15)-X(23))
530 B(30)=ABS(X(3)-X(12))+ABS(X(15)-X(24))
531 B(31)=ABS(X(4)-X(5))+ABS(X(16)-X(17))
532 B(32)=ABS(X(4)-X(6))+ABS(X(16)-X(18))
533 B(33)=ABS(X(4)-X(7))+ABS(X(16)-X(19))
534 B(34)=ABS(X(4)-X(8))+ABS(X(16)-X(20))
535 B(35)=ABS(X(4)-X(9))+ABS(X(16)-X(21))
536 B(36)=ABS(X(4)-X(10))+ABS(X(16)-X(22))
537 B(37)=ABS(X(4)-X(11))+ABS(X(16)-X(23))
538 B(38)=ABS(X(4)-X(12))+ABS(X(16)-X(24))
539 B(39)=ABS(X(5)-X(6))+ABS(X(17)-X(18))
540 B(40)=ABS(X(5)-X(7))+ABS(X(17)-X(19))
541 B(41)=ABS(X(5)-X(8))+ABS(X(17)-X(20))
542 B(42)=ABS(X(5)-X(9))+ABS(X(17)-X(21))
543 B(43)=ABS(X(5)-X(10))+ABS(X(17)-X(22))
544 B(44)=ABS(X(5)-X(11))+ABS(X(17)-X(23))
545 B(45)=ABS(X(5)-X(12))+ABS(X(17)-X(24))
546 B(46)=ABS(X(6)-X(7))+ABS(X(18)-X(19))
547 B(47)=ABS(X(6)-X(8))+ABS(X(18)-X(20))
548 B(48)=ABS(X(6)-X(9))+ABS(X(18)-X(21))
549 B(49)=ABS(X(6)-X(10))+ABS(X(18)-X(22))
550 B(50)=ABS(X(6)-X(11))+ABS(X(18)-X(23))
551 B(51)=ABS(X(6)-X(12))+ABS(X(18)-X(24))
552 B(52)=ABS(X(7)-X(8))+ABS(X(19)-X(20))
553 B(53)=ABS(X(7)-X(9))+ABS(X(19)-X(21))
554 B(54)=ABS(X(7)-X(10))+ABS(X(19)-X(22))
555 B(55)=ABS(X(7)-X(11))+ABS(X(19)-X(23))
556 B(56)=ABS(X(7)-X(12))+ABS(X(19)-X(24))
557 B(57)=ABS(X(8)-X(9))+ABS(X(20)-X(21))
558 B(58)=ABS(X(8)-X(10))+ABS(X(20)-X(22))
559 B(59)=ABS(X(8)-X(11))+ABS(X(20)-X(23))
560 B(60)=ABS(X(8)-X(12))+ABS(X(20)-X(24))
561 B(61)=ABS(X(9)-X(10))+ABS(X(21)-X(22))
562 B(62)=ABS(X(9)-X(11))+ABS(X(21)-X(23))
563 B(63)=ABS(X(9)-X(12))+ABS(X(21)-X(24))
564 B(64)=ABS(X(10)-X(11))+ABS(X(22)-X(23))
565 B(65)=ABS(X(10)-X(12))+ABS(X(22)-X(24))
566 B(66)=ABS(X(11)-X(12))+ABS(X(23)-X(24))
1107 FOR IJUL=1 TO 66
1111 IF B(IJUL)=0 THEN B(IJUL)=333333!
1115 NEXT IJUL
1380 PH=-5*B(1)-2*B(2)-4*B(3)-1*B(4)-.001*B(5)-.001*B(6)-6*B(7)-2*B(8)-1*B(9)
1381 PI=-1*B(10)-1*B(11)-3*B(12)-.001*B(13)-2*B(14)-2*B(15)-2*B(16)-.001*B(17)-4*B(18)
1382 PJ=-5*B(19)-.001*B(20)-.001*B(21)-.001*B(22)-.001*B(23)-.001*B(24)-.001*B(25)-5*B(26)-5*B(27)
1383 PK=-2*B(28)-2*B(29)-2*B(30)-5*B(31)-2*B(32)-2*B(33)-10*B(34)-.001*B(35)-.001*B(36)
1384 PL=-5*B(37)-5*B(38)-10*B(39)-.001*B(40)-.001*B(41)-.001*B(42)-5*B(43)-1*B(44)-1*B(45)
1385 PM=-5*B(46)-1*B(47)-1*B(48)-5*B(49)-4*B(50)-.001*B(51)-10*B(52)-5*B(53)-2*B(54)
1386 PN=-3*B(55)-3*B(56)-.001*B(57)-.001*B(58)-5*B(59)-.001*B(60)-.001*B(61)-10*B(62)-10*B(63)
1387 PO=-5*B(64)-.001*B(65)-2*B(66)
1588 P=PH+PI+PJ+PK+PL+PM+PN+PO
1599 REM PR=PK
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 24
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-290 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9),A(10)
1914 PRINT A(11),A(12),A(13),A(14),A(15)
1915 PRINT A(16),A(17),A(18),A(19),A(20)
1916 PRINT A(21),A(22),A(23),A(24)
1917 PRINT M,JJJJ
1999 NEXT JJJJ
One notes that the artificial .001 flows of lines like line 1380 replace the original 0 flows.
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced during the first 17 minutes of running is presented below. (What immediately follows is a manual copy from the computer screen.)
1 1 1 4 4
3 3 3 2 2
2 4 1 2 0
1 2 2 0 1
0 2 1 0
-289.065 -31454
3 3 3 0 0
1 1 1 2 2
2 0 1 2 0
1 2 2 0 1
0 2 1 0
-289.065 -30596
0 0 0 3 3
2 2 2 1 1
1 3 1 0 2
1 0 0 2 1
2 0 1 2
-289.065 -29705
Interpreted in accordance with line 1912 through line 1917, the output through JJJJ=-29705 was produced during the first 17 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Hillier, F. S. (1963), "Quantitative tools for plant layout analysis," J. Indust. Eng. 14, 33-40.
Nugent, C. E., Vollmann, T. E., and Ruml, J. (1968), "An experimental comparisons of techniques for the assignment of facilities to locations," Operations Research 16, 150-173.
Heragu, S. S., and Kusiak, A. (1991), "Efficient models for the facility layout problem," European Journal of Operational Research 53, 1-13.
