Jsun Yui Wong
The computer program listed below seeks to solve the 7-department problem in Nugent, Vollmann, and Ruml (1968).
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),T(111)
6 DIM TBM(33,33)
11 TBM(1,1)=999:TBM(1,2)=1:TBM(1,3)=2:TBM(1,4)=3:TBM(1,5)=2:TBM(1,6)=3:TBM(1,7)=4
13 TBM(2,1)=1:TBM(2,2)=999:TBM(2,3)=1:TBM(2,4)=2:TBM(2,5)=1:TBM(2,6)=2:TBM(2,7)=3
15 TBM(3,1)=2:TBM(3,2)=1:TBM(3,3)=999:TBM(3,4)=1:TBM(3,5)=2:TBM(3,6)=1:TBM(3,7)=2
17 TBM(4,1)=3:TBM(4,2)=2:TBM(4,3)=1:TBM(4,4)=999:TBM(4,5)=3:TBM(4,6)=2:TBM(4,7)=1
19 TBM(5,1)=2:TBM(5,2)=1:TBM(5,3)=2:TBM(5,4)=3:TBM(5,5)=999:TBM(5,6)=1:TBM(5,7)=2
21 TBM(6,1)=3:TBM(6,2)=2:TBM(6,3)=1:TBM(6,4)=2:TBM(6,5)=1:TBM(6,6)=999:TBM(6,7)=1
23 TBM(7,1)=4:TBM(7,2)=3:TBM(7,3)=2:TBM(7,4)=1:TBM(7,5)=2:TBM(7,6)=1:TBM(7,7)=999
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
81 A(1)=1:A(2)=2:A(3)=3:A(4)=4:A(5)=5:A(6)=6:A(7)=7
126 IMAR=10+FIX(RND*100)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 7
131 X(KK)=A(KK)
132 NEXT KK
330 IJM=1+FIX(RND*7)
331 IJN=1+FIX(RND*7)
333 X(IJM)=A(IJN):X(IJN)=A(IJM)
401 T(1)=5*TBM(X(1),X(2))
402 T(2)=2*TBM(X(1),X(3))
403 T(3)=4*TBM(X(1),X(4))
404 T(4)=1*TBM(X(1),X(5))
405 T(5)=0*TBM(X(1),X(6))
406 T(6)=0*TBM(X(1),X(7))
415 T(12)=3*TBM(X(2),X(3))
416 T(13)=0*TBM(X(2),X(4))
417 T(14)=2*TBM(X(2),X(5))
418 T(15)=2*TBM(X(2),X(6))
419 T(16)=2*TBM(X(2),X(7))
426 T(22)=1*TBM(X(3),X(4))
427 T(23)=0*TBM(X(3),X(5))
428 T(24)=2*TBM(X(3),X(6))
429 T(25)=5*TBM(X(3),X(7))
437 T(31)=5*TBM(X(4),X(5))
438 T(32)=2*TBM(X(4),X(6))
439 T(33)=2*TBM(X(4),X(7))
445 T(39)=10*TBM(X(5),X(6))
446 T(40)=0*TBM(X(5),X(7))
452 T(46)=5*TBM(X(6),X(7))
651 P1NEW=0
652 FOR KAU7=1 TO 46
653 P1NEW=P1NEW+T(KAU7)
654 NEXT KAU7
750 P=-P1NEW
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 7
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-76 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7)
1927 PRINT M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced during the first 3 seconds of running is presented below. (What immediately follows is a manual copy from the computer screen.)
1 2 5 3 4
7 6
-74 -31977
4 3 1 7 6
5 2
-74 -31970
4 3 1 7 6
5 2
-74 -31946
4 3 1 7 6
5 2
-74 -31944
7 6 5 4 3
2 1
-75 -31931
Interpreted in accordance with line 1912 through line 1927, the output through JJJJ=-31931 was produced during the first 3 seconds of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Elshafei, A. N., "Hospital Layout as a Quadratic Assignment Problem," Operational Research Quarterly 28, 167-179 (1977).
Gavett. J. W. and N. V. Plyter, "The Optimal Assignment of Facilities to Locations by Branch and Bound," Operations Research 14, 210-232 (Mar.-Apr., 1966).
Heragu, S. S. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.
Land, A. H., "A Problem of Assignment with Inter-Related Costs," Operational Research Quarterly 14, 185-199 (June 1963).
Nugent,C. E., T. E. Vollmann, and J. Ruml, "An Experimental Comparison of Techniques for the Assignment of Facilities to Locations," Operations Research 16, 150-173 (Jan.-Feb., 1968).
Pierce, J. F. and W. B. Crowston, "Tree-Search Algorithms for Quadratic Assignment Problems," Naval Research Logistics Quarterly 18, 1-36 (1971).
