The computer program listed below seeks to solve a small space allocation problem (Armour and Buffa, 1963). The departmment sizes for department 1 through department 4 are 20x50, 30x40, 10x20, and 60x70, respectively; the interdepartmental flows are shown in line 1624 of the following program.
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),J(466)
6 DIM T(11,11,5),TZ(11,11,5),TL(11,11,5)
7 T(1,2,1)=25:T(1,2,2)=30:T(1,2,3)=40:T(1,2,4)=45
8 T(1,3,1)=15:T(1,3,2)=20:T(1,3,3)=30:T(1,3,4)=35
9 T(1,4,1)=40:T(1,4,2)=45:T(1,4,3)=55:T(1,4,4)=60
19 T(2,3,1)=20:T(2,3,2)=25:T(2,3,3)=25:T(2,3,4)=30
20 T(2,4,1)=45:T(2,4,2)=50:T(2,4,3)=50:T(2,4,4)=55
33 T(3,4,1)=35:T(3,4,2)=40:T(3,4,3)=40:T(3,4,4)=45
37 T(5,6,1)=25:T(5,6,2)=30:T(5,6,3)=40:T(5,6,4)=45
38 T(5,7,1)=15:T(5,7,2)=20:T(5,7,3)=30:T(5,7,4)=35
39 T(5,8,1)=40:T(5,8,2)=45:T(5,8,3)=55:T(5,8,4)=60
49 T(6,7,1)=20:T(6,7,2)=25:T(6,7,3)=25:T(6,7,4)=30
50 T(6,8,1)=45:T(6,8,2)=50:T(6,8,3)=50:T(6,8,4)=55
63 T(7,8,1)=35:T(7,8,2)=40:T(7,8,3)=40:T(7,8,4)=45
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 8
88 A(I)=FIX(RND*120)
89 NEXT I
126 IMAR=10+FIX(RND*32000)
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)
234 X(IJL)=FIX(RND*120)
370 FOR K=1 TO 3
371 FOR J=K+1 TO 4
373 ABH=ABS(X(K)-X(J))
374 ABV=ABS(X(K+4)-X(J+4))
377 IF ABH
379 IF ABV
399 NEXT K
1580 SUMTZ=0
1585 SUMTL=0
1591 FOR K=1 TO 3
1594 FOR J=K+1 TO 4
1595 SUMTZ=SUMTZ+TZ(K,J,V)
1596 SUMTL=SUMTL+TL(K+4,J+4,V)
1597 NEXT J
1598 NEXT K
1624 PR1=-111*ABS(X(1)-X(2))-222*ABS(X(1)-X(3))-110*ABS(X(1)-X(4))-88*ABS(X(2)-X(3))-260*ABS(X(2)-X(4))-250*ABS(X(3)-X(4))-111*ABS(X(5)-X(6))-222*ABS(X(5)-X(7))-110*ABS(X(5)-X(8))-88*ABS(X(6)-X(7))-260*ABS(X(6)-X(8))-250*ABS(X(7)-X(8))
1650 P=PR1-SUMTZ-SUMTL
1651 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>-45000! THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the best (with respect to the objective function values) candidate solutions produced during the first 5.5 hours of running are presented below. What immediately follows is a manual copy from the computer screen.
36 22 21 22 66
39 67 106 -44015 -30733
81 81 81 81 89
114 74 38 -43995 -28077
92 92 92 92 94
119 79 44 -43375 -27933
3 17 18 17 91
117 89 51 -43616 -27825
90 91 90 90 52
77 37 2 -43834 -27775
An outputted candidate solution can have overlaps of facilities, and hence it is not acceptable. For example, the candidate solution at JJJJ=-27825 has overlaps. Among the candidate solutions presented above, the one at JJJJ=-27933 is the best because it has the best objective function value (-43375) and does not have any facility overlap.
Interpreted in accordance with line 1912 and line 1914, the output through
JJJJ=-27775 was produced during the first 5.5 hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
Reference
G. C. Armour and E. S. Buffa, "A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities," Management Science 9, 294-309 (1963).
