Jsun Yui Wong
The computer program listed below tries to solve the 8-department problem of Nugent, Vollmann, and Ruml (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,1,2,3,1,2,3,4
25 DATA 1,999,1,2,2,1,2,3
26 DATA 2,1,999,1,3,2,1,2
27 DATA 3,2,1,999,4,3,2,1
28 DATA 1,2,3,4,999,1,2,3
29 DATA 2,1,2,3,1,999,1,2
30 DATA 3,2,1,2,2,1,999,1
31 DATA 4,3,2,1,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*50
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>-110 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=-31938 is presented below. What follows is a manual copy from the computer monitor.
6 5 1 3 7
8 4 2 -109 -31997
6 5 1 7 8
4 3 2 -107 -31995
7 8 4 2 6
5 1 3 -109 -31963
7 8 4 2 6
5 1 3 -109 -31961
3 4 8 2 1
5 6 7 -107 -31960
2 1 5 3 4
8 7 6 -107 -31957
7 8 4 6 5
1 2 3 -107 -31952
6 5 1 7 8
4 3 2 -107 -31938
107 is optimal, Nugent et al. (1968). Interpreted in accordance with line 1912 and line 1929, the output above was obtained in three seconds of running on a personal computer with an Intel 2.66 GHz. chip and with the IBM basica/D interpreter.
References
Hillier, F. S. (1963), "Quantitative tools for plant layout analysis," J. Indust. Eng. 14, 33-40.
Loiola, E. M., N. M. M. de Abreu, P. O. Boaventura-Netto, P. Hahn, and T. Querido
(2007), "A survey for the quadratic assignment problem," European Journal of Operational Research 176, 657-690.
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., T. E. Vollmann, and J. Ruml (1968), "An experimental comparisons of techniques for the assignment of facilities to locations," Operations Research 16, 150-173.
Subscribe to:
Posts (Atom)