Jsun Yui Wong
The computer program listed below tries to solve a problem that is a modification of the 8-department problem of Nugent, Vollmann, and Ruml (1968). With L01 standing for location 01, the plant shape is as follows:
L02
LO4 L05 L06 L07 L08
L03
And L01 is directly behind L04; the third dimension has L01 only.
The distance between L01 and L04 is one, the (rectangular) distance between L01 and L02 is two, the distance between L01 and L03 is two, the distance between L01 and L05 is two, the distance between L04 and L05 is one, the distance between L05 and L06 is one, the distance between between L06 and L07 is one, and the distance between L07 and L08 is one.
These rectangular distances are used in line 24 through line 31. The flows are shown in line 54 through line 60; these flows have been obtained from Nugent et al. (1968).
0 DEFINT A-Z
3 DEFSNG H,S,P,M
5 DIM X(66),A(66)
8 DIM HS(33,33),HR(22,22)
11 FOR IZ=1 TO 8
14 FOR JZ=1 TO 8
16 READ HR(IZ,JZ)
18 NEXT JZ
19 NEXT IZ
24 DATA 999,2,2,1,2,3,4,5
25 DATA 2,999,2,1,2,3,4,5
26 DATA 2,2,999,1,2,3,4,5
27 DATA 1,1,1,999,1,2,3,4
28 DATA 2,2,2,1,999,1,2,3
29 DATA 3,3,3,2,1,999,1,2
30 DATA 4,4,4,3,2,1,999,1
31 DATA 5,5,5,4,3,2,1,999
49 FOR IZ=1 TO 7
50 FOR JZ=IZ+1 TO 8
51 READ HS(IZ,JZ)
52 NEXT JZ
53 NEXT IZ
54 DATA 5,2,4,1,0,0,6
55 DATA 3,0,2,2,2,0
56 DATA 0,0,0,0,5
57 DATA 5,2,2,10
58 DATA 10,0,0
59 DATA 5,1
60 DATA 10
74 FOR JJJJ=-32000 TO 32000
75 RANDOMIZE JJJJ
76 M=-999999999999#
81 FOR ZI=1 TO 8
82 A(ZI)=ZI
83 NEXT ZI
126 IMAR=10+RND*1
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 8
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*8)
224 IJM=1+FIX(RND*8)
236 X(IJL)=A(IJM):X(IJM)=A(IJL)
1631 SUMUL=0
1632 FOR IS1=1 TO 7
1634 FOR IS2=IS1+1 TO 8
1637 SUMUL=SUMUL+HS(IS1,IS2)*HR(X(IS1),X(IS2))
1638 NEXT IS2
1639 NEXT IS1
1646 P=-SUMUL
1656 IF P<=M THEN 1670
1657 FOR KEW=1 TO 8
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-139 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1929 PRINT A(6),A(7),A(8),M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, which is not a compiler. Its output through JJJJ=-31936 is presented below.
2 3 1 6 8
7 5 4 -137 -32000
1 2 3 5 8
7 6 4 -137 -31976
1 2 3 6 8
7 5 4 -137 -31960
1 2 3 5 8
7 6 4 -137 -31936
Interpreted in accordance with line 1912 through line 1929, the output above was obtained in about two seconds on a personal computer with speed of 2.66 GHz. and with the IBM basica/D interpreter.
References
Hillier, F. S., "Quantitative Tools for Plant Layout Analysis," Journal of Industrial Engineering, 14, 1 (1963), 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., R. E. Vollmann, and J. Ruml, "An Experimental Comparison of Techniques for the Assignment of Facilities to Locations," Operations Research, 16 (1968), 150-173.
Skorin-Kapov, J., "Tabu Search Applied to the Quadratic Assignment Problem," ORSA Journal on Computing, 2 (1990), 33-45.
