Jsun Yui Wong
The computer program listed below tries to solve the 12-department problem in Hillier (1963) and in Nugent, Vollmann, and Ruml (1968).
0 DEFINT A-Z
3 DEFSNG M,P,S,T
5 DIM X(66),A(66)
6 DIM TM(24,24),HR(24,24),HS(24,24)
41 FOR IZ=1 TO 11
43 FOR JZ=IZ+1 TO 12
46 READ HS(IZ,JZ)
48 NEXT JZ
49 NEXT IZ
53 DATA 5,2,4,1,0,0,6,2,1,1,1,3,0,2,2,2,0,4,5,0,0,0,0,0,0,5,5,2,2,2,5,2,2,10,0,0,5,5,10,0,0,0,5,1,1,5,1,1,5,4,0,10,5,2,3,3,0,0,5,0,0,10,10,5,0,2
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-999999!
77 A(1)=0:A(13)=0
78 A(2)=1:A(14)=0
79 A(3)=2:A(15)=0
80 A(4)=3:A(16)=0
81 A(5)=0:A(17)=1
82 A(6)=1:A(18)=1
83 A(7)=2:A(19)=1
84 A(8)=3:A(20)=1
85 A(9)=0:A(21)=2
86 A(10)=1:A(22)=2
87 A(11)=2:A(23)=2
88 A(12)=3:A(24)=2
126 IMAR=10+RND*100
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 24
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*12)
224 IJM=1+FIX(RND*12)
236 X(IJL)=A(IJM):X(IJM)=A(IJL):X(IJL+12)=A(IJM+12):X(IJM+12)=A(IJL+12)
1631 SUMUL=0
1632 FOR IS1=1 TO 11
1634 FOR IS2=IS1+1 TO 12
1636 SUMUL=SUMUL+HS(IS1,IS2)*(ABS(X(IS1)-X(IS2))+ABS(X(IS1+12)-X(IS2+12)))
1637 NEXT IS2
1639 NEXT IS1
1646 P=-SUMUL
1656 IF P<=M THEN 1670
1657 FOR KEW=1 TO 24
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-292 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)
1916 PRINT A(16),A(17),A(18),A(19),A(20)
1917 PRINT A(21),A(22),A(23),A(24)
1919 PRINT M,JJJJ
1999 NEXT JJJJ
The BASIC computer program above was run with Microsoft's GW BASIC 3.11 interpreter, and the output produced during the first five minutes of running is presented below. What follows is a manual copy from the computer monitor.
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 -31453
3 3 3 0 0
1 2 2 1 2
1 0 1 0 2
1 0 0 2 1
2 0 1 2
-291 -30883
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 -29610
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 -29081
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 -28266
289 is optimal. Interpreted in accordance with line 1912 through line 1919, the output above was produced during the first five minutes of running on a personal computer with speed of 2.66 GHz. and with the IBM basica/D interpreter, which is not a compiler.
References
Hillier, F. S. (1963), "Quantitative tools for plant layout analysis," J. Indust.Eng. 14, 33-40.
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.
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.(1969).
