A Computer Program and Its Output for a Small Space Allocation Problem

Jsun Yui Wong

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),TL(11,11)
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*160)
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*160)
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 ABH378 GOTO 388
379 IF ABV388 NEXT J
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)
1596 SUMTL=SUMTL+TL(K+4,J+4)
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 7.6 hours of running are presented below. What immediately follows is a manual copy from the computer screen.

74 57 57 57 96
71 98 136 -43926 -27754

128 128 128 128 99
124 84 49 -43375 -26218

A solution from the computer program above can have overlaps of facilities, and hence it is not acceptable.

Among the candidate solutions presented above, the one at JJJJ=-26218 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=-26218 was produced during the first 7.6 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).

A Computer Program and Its Output for a Small Space Allocation Problem

Jsun Yui Wong

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),TL(11,11)
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*130)
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*130)
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 ABH378 GOTO 388
379 IF ABV388 NEXT J
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)
1596 SUMTL=SUMTL+TL(K+4,J+4)
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 hours of running are presented below. What immediately follows is a manual copy from the computer screen.

70 70 70 70 31
6 46 82 -43995 -31433

90 90 90 90 31
6 46 81 -43375 -28549

79 79 79 80 26
1 41 76 -43995 -28486

An outputted candidate solution can have overlaps of facilities, and hence it is not acceptable. Among the candidate solutions presented above, the one at
JJJJ=-28549 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=-28486 was produced during the first 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).

ERRATA

Jsun Yui Wong

Line 377, line 378, line 379, and line 388 of the September 16 post of the present blog should read as follows:

377 IF ABH less than T(K,J,4) THEN IF ABH less than T(K,J,3) THEN IF ABH less than T(K,J,2) THEN IF ABH less than T(K,J,1) THEN 379 ELSE TZ(K,J,V)=0
378 GOTO 388
379 IF ABV less than T(K+4,J+4,4) THEN IF ABV less than T(K+4,J+4,3) THEN IF ABV less than T(K+4,J+4,2) THEN IF ABV less than T(K+4,J+4,1) THEN TL(K+4,J+4,V)=999999! ELSE TL(K+4,J+4,V)=0
388 NEXT J

Each "less than" above should be replaced by <.

A Computer Program and Its Output for a Small Space Allocation Problem

Jsun Yui Wong

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 ABH378 GOTO 388
379 IF ABV388 NEXT J
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).

ERRATA

Jsun Yui wong

Line 364 and line 366 of the September 7 post of the present blog should read as

follows:

364 IF ABS(X(K)-X(J))less than TBM(K,J) THEN TZ(K,J)=9999 ELSE TZ(K,J)=0

366 NEXT J

The "less than" above should be replaced by <.

Scheduling Fifty-Six Activities among Six Facilities

Jsun Yui Wong

The complete computer program listed below illustrates an algorithm for solving the Carlson and Nemhauser (1966) scheduling problem. Modeled after that of the July 24 post of the present blog, the following computer program has 56 activities and 6 facilities. The interaction costs in line 51 through line 219 are from Skorin-Kapov (1990, Figure 11C).

0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(80),A(80),L(80),K(80),P(80),B(80),S(80)
6 DIM T(70,70),TZ(70,70)
51 T(1,2)=1:T(1,4)=4:T(1,6)=3:T(1,7)=5:T(1,8)=2:T(1,9)=4:T(1,12)=1:T(1,5)=1:T(1,16)=5
52 T(1,17)=2:T(1,18)=2:T(1,20)=5:T(1,21)=4:T(1,16)=1:T(1,27)=5:T(1,28)=10:T(1,29)=5:T(1,30)=1:T(1,32)=5
53 T(1,33)=2:T(1,36)=5:T(1,37)=10:T(1,39)=4:T(1,40)=5:T(1,41)=2:T(1,42)=1:T(1,43)=2:T(1,44)=1:T(1,45)=5
54 T(1,46)=2:T(1,47)=5:T(1,48)=10:T(1,49)=5:T(1,50)=10:T(1,52)=2:T(1,53)=1:T(1,55)=1:T(1,56)=1
63 T(2,4)=5:T(2,6)=10:T(2,8)=5:T(2,9)=10:T(2,10)=5:T(2,11)=5:T(2,12)=10: T(2,15)=1
64 T(2,16)=2:T(2,18)=5:T(2,21)=2:T(2,23)=2:T(2,24)=1:T(2,25)=1:T(2,26)=2:T(2,27)=10:T(2,28)=5:T(2,30)=10
65 T(2,31)=1:T(2,33)=3:T(2,36)=1:T(2,37)=2:T(2,38)=5:T(2,39)=2:T(2,40)=1:T(2,42)=1:T(2,43)=1:T(2,44)=1
66 T(2,45)=5:T(2,46)=6:T(2,47)=3:T(2,48)=2:T(2,56)=5
67 T(3,4)=1:T(3,5)=5:T(3,6)=2:T(3,12)=6:T(3,13)=1:T(3,15)=1:T(3,16)=1
68 T(3,17)=1:T(3,19)=2:T(3,21)=2:T(3,22)=1:T(3,23)=1:T(3,24)=2:T(3,25)=1:T(3,26)=3:T(3,27)=2:T(3,28)=5
69 T(3,30)=10:T(3,31)=2:T(3,32)=10:T(3,38)=5:T(3,39)=1:T(3,41)=3:T(3,42)=5:T(3,44)=5:T(3,46)=5:T(3,47)=5
70 T(3,49)=10:T(3,51)=2:T(3,52)=5:T(3,55)=10:T(3,56)=2
77 T(4,5)=5:T(4,6)=4:T(4,7)=10:T(4,8)=4:T(4,9)=3:T(4,10)=5
78 T(4,12)=5:T(4,15)=10:T(4,16)=5:T(4,18)=2:T(4,19)=2:T(4,20)=10:T(4,21)=2:T(4,22)=1:T(4,23)=2:T(4,25)=10
79 T(4,27)=1:T(4,29)=6:T(4,30)=2:T(4,32)=5:T(4,33)=1:T(4,34)=5:T(4,35)=2:T(4,36)=5:T(4,37)=1:T(4,39)=1
80 T(4,41)=2:T(4,42)=2:T(4,45)=4:T(4,46)=10:T(4,48)=5:T(4,52)=2:T(4,53)=10:T(4,54)=1:T(4,55)=10:T(4,56)=5
81 T(5,6)=1:T(5,7)=1:T(5,8)=1:T(5,9)=2:T(5,11)=10:T(5,12)=5:T(5,13)=2:T(5,14)=5:T(5,15)=5:T(5,16)=2
82 T(5,18)=5:T(5,19)=5:T(5,20)=10:T(5,22)=1:T(5,23)=2:T(5,24)=1:T(5,25)=2:T(5,26)=2:T(5,27)=5:T(5,28)=6
83 T(5,29)=10:T(5,30)=2:T(5,31)=5:T(5,32)=10:T(5,33)=10:T(5,34)=10:T(5,35)=1:T(5,36)=2:T(5,37)=2:T(5,38)=2
84 T(5,39)=2:T(5,40)=5:T(5,41)=4:T(5,44)=5:T(5,45)=5:T(5,46)=2:T(5,47)=5:T(5,48)=10:T(5,50)=5:T(5,51)=5
85 T(5,52)=5:T(5,54)=2:T(5,55)=3:T(5,56)=10
93 T(6,7)=1:T(6,8)=1:T(6,11)=2:T(6,12)=2
94 T(6,17)=1:T(6,19)=5:T(6,20)=10:T(6,21)=5:T(6,22)=10:T(6,23)=1:T(6,24)=10:T(6,25)=2:T(6,26)=10:T(6,27)=2
95 T(6,28)=5:T(6,29)=5:T(6,31)=2:T(6,32)=2:T(6,33)=1:T(6,35)=1:T(6,36)=5:T(6,37)=5:T(6,38)=10:T(6,40)=2
96 T(6,41)=1:T(6,42)=2:T(6,43)=1:T(6,44)=1:T(6,45)=10:T(6,46)=10:T(6,49)=5:T(6,52)=1:T(6,53)=2:T(6,54)=5:T(6,55)=10:T(6,56)=1
97 T(7,8)=6:T(7,9)=2:T(7,10)=2
98 T(7,11)=10:T(7,12)=2:T(7,13)=10:T(7,14)=2:T(7,15)=4:T(7,16)=6:T(7,19)=1:T(7,20)=4:T(7,21)=4:T(7,22)=2
99 T(7,23)=5:T(7,24)=5:T(7,25)=2:T(7,26)=1:T(7,29)=10:T(7,30)=2:T(7,31)=6:T(7,32)=2:T(7,33)=2:T(7,34)=6
100 T(7,36)=5:T(7,37)=4:T(7,38)=2:T(7,40)=2:T(7,41)=2:T(7,43)=1:T(7,44)=5:T(7,45)=2:T(7,47)=2:T(7,49)=1:T(7,51)=2:T(7,52)=10
101 T(8,9)=5:T(8,11)=10
102 T(8,12)=5:T(8,15)=2:T(8,16)=4:T(8,19)=5:T(8,20)=5:T(8,21)=2:T(8,22)=5:T(8,23)=2:T(8,24)=5:T(8,25)=5
103 T(8,28)=2:T(8,29)=2:T(8,30)=5:T(8,31)=1:T(8,36)=5:T(8,37)=5:T(8,39)=1:T(8,40)=1:T(8,41)=3:T(8,43)=1
104 T(8,44)=5:T(8,45)=2:T(8,46)=3:T(8,47)=2:T(8,48)=5:T(8,50)=10:T(8,52)=4:T(8,53)=5:T(8,54)=5:T(8,55)=5:T(8,56)=10
105 T(9,10)=4
106 T(9,12)=5:T(9,14)=5:T(9,16)=2:T(9,18)=2:T(9,19)=1:T(9,20)=2:T(9,23)=5:T(9,24)=10:T(9,25)=10:T(9,26)=1
107 T(9,27)=5:T(9,28)=2:T(9,29)=1:T(9,30)=10:T(9,31)=1:T(9,33)=10:T(9,34)=1:T(9,35)=2:T(9,36)=5:T(9,37)=5
108 T(9,38)=4:T(9,39)=3:T(9,40)=10:T(9,41)=1:T(9,42)=10:T(9,43)=1:T(9,44)=5:T(9,46)=1:T(9,50)=10:T(9,51)=6:T(9,52)=5:T(9,55)=2:T(9,56)=5
110 T(10,12)=2:T(10,13)=5:T(10,15)=5:T(10,17)=1:T(10,20)=10:T(10,21)=1:T(10,22)=3:T(10,26)=2:T(10,27)=3:T(10,29)=3
111 T(10,30)=2:T(10,33)=5:T(10,34)=3:T(10,35)=5:T(10,36)=10:T(10,39)=5:T(10,40)=10:T(10,42)=2:T(10,44)=5:T(10,45)=2
112 T(10,46)=2:T(10,47)=2:T(10,48)=1:T(10,49)=6:T(10,50)=10:T(10,51)=5:T(10,52)=6:T(10,53)=2:T(10,54)=2:T(10,55)=1
114 T(11,13)=1:T(11,14)=5:T(11,18)=5:T(11,19)=1:T(11,20)=1:T(11,21)=10:T(11,22)=10:T(11,23)=4:T(11,26)=2
115 T(11,27)=5:T(11,29)=4:T(11,30)=10
116 T(11,32)=5:T(11,35)=1:T(11,36)=5:T(11,37)=10:T(11,40)=2:T(11,41)=1:T(11,42)=1:T(11,43)=2:T(11,44)=5:T(11,45)=2
117 T(11,46)=1:T(11,48)=1:T(11,49)=10:T(11,50)=5:T(11,51)=1:T(11,53)=2:T(11,54)=1:T(11,55)=4:T(11,56)=5
118 T(12,13)=10:T(12,14)=10:T(12,15)=3:T(12,17)=1:T(12,18)=5:T(12,19)=1:T(12,20)=5:T(12,21)=2
119 T(12,22)=1:T(12,25)=1:T(12,27)=10:T(12,28)=3:T(12,30)=1:T(12,31)=5:T(12,32)=1:T(12,33)=5:T(12,34)=2:T(12,35)=2
120 T(12,37)=6:T(12,38)=1:T(12,39)=5:T(12,41)=5:T(12,42)=5:T(12,45)=5:T(12,46)=3:T(12,47)=1:T(12,48)=10:T(12,50)=5
121 T(12,51)=2:T(12,52)=1:T(12,53)=5:T(12,55)=5:T(12,56)=5
122 T(13,14)=1:T(13,17)=2:T(13,18)=10:T(13,19)=1:T(13,20)=1:T(13,21)=5:T(13,23)=2
123 T(13,24)=5:T(13,25)=5:T(13,27)=5:T(13,28)=1:T(13,29)=2:T(13,30)=4:T(13,32)=2:T(13,33)=2:T(13,34)=6:T(13,35)=5
124 T(13,36)=5:T(13,37)=5:T(13,38)=5:T(13,40)=10:T(13,41)=2:T(13,42)=5:T(13,44)=10:T(13,46)=1:T(13,48)=4:T(13,51)=2
125 T(13,53)=1:T(13,55)=5:T(13,56)=10
126 T(14,15)=1:T(14,16)=2:T(14,18)=3:T(14,19)=1:T(14,20)=1:T(14,21)=2
127 T(14,22)=2:T(14,23)=2:T(14,24)=10:T(14,25)=4:T(14,26)=2:T(14,27)=4:T(14,28)=10:T(14,29)=2:T(14,31)=4:T(14,33)=2
128 T(14,35)=5:T(14,36)=10:T(14,37)=3:T(14,38)=1:T(14,40)=2:T(14,41)=10:T(14,42)=5:T(14,44)=5:T(14,46)=2:T(14,47)=5
129 T(14,48)=2:T(14,49)=10:T(14,51)=1:T(14,52)=5:T(14,53)=10:T(14,54)=5:T(14,55)=5
136 T(15,17)=10:T(15,18)=10:T(15,21)=2:T(15,22)=5:T(15,24)=2
137 T(15,25)=5:T(15,26)=6:T(15,28)=5:T(15,29)=2:T(15,31)=5:T(15,32)=2:T(15,35)=2:T(15,36)=2:T(15,37)=2:T(15,38)=1
138 T(15,40)=5:T(15,41)=1:T(15,42)=4:T(15,46)=10:T(15,49)=2:T(15,50)=1:T(15,54)=5:T(15,55)=1:T(15,56)=1
140 T(16,20)=5:T(16,21)=10:T(16,22)=2:T(16,23)=2
141 T(16,24)=2:T(16,25)=5:T(16,26)=4:T(16,27)=10:T(16,28)=1:T(16,31)=2:T(16,32)=3:T(16,33)=4:T(16,34)=2:T(16,36)=1
143 T(16,38)=1:T(16,42)=1:T(16,43)=2:T(16,44)=5:T(16,46)=4:T(16,47)=5:T(16,48)=2:T(16,49)=2:T(16,50)=5:T(16,51)=2:T(16,52)=1:T(16,53)=3:T(16,54)=1:T(16,55)=5:T(16,56)=5
144 T(17,18)=1:T(17,19)=5:T(17,20)=10
145 T(17,21)=1:T(17,22)=5:T(17,23)=10:T(17,24)=6:T(17,26)=5:T(17,27)=10:T(17,28)=5:T(17,30)=5:T(17,31)=5:T(17,33)=4
146 T(17,35)=1:T(17,36)=3:T(17,37)=1:T(17,38)=2:T(17,39)=5:T(17,40)=2:T(17,41)=1:T(17,42)=3:T(17,43)=1:T(17,44)=1
147 T(17,45)=5:T(17,46)=6:T(17,47)=1:T(17,48)=10:T(17,49)=2:T(17,51)=10:T(17,53)=1:T(17,54)=2
148 T(18,19)=6:T(18,23)=10
149 T(18,24)=2:T(18,25)=2:T(18,26)=4:T(18,30)=3:T(18,31)=5:T(18,32)=6:T(18,33)=3:T(18,35)=10:T(18,36)=6:T(18,37)=5
150 T(18,39)=5:T(18,40)=5:T(18,41)=1:T(18,42)=2:T(18,43)=3:T(18,44)=10:T(18,45)=1:T(18,47)=10:T(18,48)=5:T(18,49)=5
151 T(18,51)=1:T(18,52)=1:T(18,53)=1:T(18,55)=2:T(18,56)=2
152 T(19,20)=2
153 T(19,22)=5:T(19,24)=4:T(19,25)=1:T(19,26)=2:T(19,27)=5:T(19,31)=1:T(19,33)=5:T(19,34)=5:T(19,35)=10:T(19,39)=2
154 T(19,40)=1:T(19,42)=2:T(19,44)=1:T(19,45)=1:T(19,47)=5:T(19,49)=6:T(19,50)=1:T(19,51)=2:T(19,52)=2:T(19,53)=2
155 T(19,54)=10:T(19,55)=5:T(19,56)=1
157 T(20,21)=1:T(20,22)=2:T(20,26)=10:T(20,27)=10:T(20,29)=10:T(20,30)=5:T(20,32)=10:T(20,34)=5:T(20,35)=5
158 T(20,36)=2:T(20,37)=4:T(20,39)=1:T(20,40)=2:T(20,41)=4:T(20,45)=4:T(20,47)=5:T(20,48)=5:T(20,50)=5
159 T(20,52)=5:T(20,53)=5:T(20,55)=1
160 T(21,23)=2:T(21,24)=3:T(21,25)=10:T(21,26)=5:T(21,28)=5:T(21,30)=1:T(21,31)=5:T(21,34)=1:T(21,36)=2
163 T(21,37)=5:T(21,42)=1:T(21,44)=1:T(21,45)=3:T(21,46)=5:T(21,49)=1:T(21,51)=2:T(21,53)=4:T(21,54)=3
164 T(21,55)=2:T(21,56)=5
167 T(22,23)=10:T(22,24)=2:T(22,25)=4:T(22,27)=5:T(22,28)=5:T(22,29)=2:T(22,30)=5:T(22,31)=5
168 T(22,32)=5:T(22,33)=5:T(22,34)=5:T(22,38)=4:T(22,41)=5:T(22,43)=5:T(22,45)=10:T(22,49)=5
169 T(22,50)=5:T(22,51)=1:T(22,52)=10:T(22,53)=10:T(22,55)=2:T(22,56)=2
171 T(23,24)=10:T(23,25)=2:T(23,26)=5:T(23,27)=1:T(23,28)=6:T(23,29)=10:T(23,30)=10
172 T(23,32)=1:T(23,33)=5:T(23,34)=2:T(23,35)=5:T(23,37)=2:T(23,38)=10:T(23,40)=5
173 T(23,41)=1:T(23,42)=2:T(23,45)=2:T(23,47)=1:T(23,48)=5:T(23,50)=1:T(23,51)=10
174 T(23,52)=5:T(23,54)=1:T(23,55)=4:T(23,56)=2
175 T(24,25)=5:T(24,26)=10:T(24,27)=2:T(24,28)=10:T(24,29)=2:T(24,30)=2
176 T(24,31)=1:T(24,33)=5:T(24,36)=3:T(24,38)=5:T(24,42)=2:T(24,43)=2
177 T(24,44)=2:T(24,45)=2:T(24,46)=2:T(24,48)=2:T(24,49)=1:T(24,50)=10
178 T(24,52)=2:T(24,53)=5:T(24,54)=10:T(24,55)=10:T(24,56)=5
179 T(25,29)=1:T(25,31)=5:T(25,32)=4:T(25,33)=2:T(25,34)=5
180 T(25,36)=2:T(25,37)=2:T(25,38)=2:T(25,39)=2:T(25,42)=5
181 T(25,44)=5:T(25,45)=5:T(25,46)=5:T(25,48)=2:T(25,50)=5
182 T(25,52)=3:T(25,53)=1:T(25,54)=10:T(25,56)=1
183 T(26,27)=5:T(26,28)=5:T(26,29)=5:T(26,30)=1
184 T(26,32)=1:T(26,33)=2:T(26,34)=4:T(26,36)=2
185 T(26,37)=2:T(26,38)=2:T(26,39)=5:T(26,41)=2
186 T(26,43)=10:T(26,46)=5:T(26,50)=2:T(26,51)=2:T(26,52)=1:T(26,53)=3:T(26,54)=2:T(26,55)=2:T(26,56)=2
187 T(27,29)=3:T(27,30)=1:T(27,31)=1
188 T(27,32)=5:T(27,33)=2:T(27,34)=1
189 T(27,36)=5:T(27,37)=5:T(27,39)=6
190 T(27,41)=6:T(27,43)=5:T(27,44)=5:T(27,45)=10:T(27,46)=1:T(27,47)=6:T(27,49)=10:T(27,50)=2:T(27,52)=5:T(27,53)=10:T(27,55)=2
191 T(28,29)=5:T(28,30)=5
192 T(28,32)=10:T(28,34)=1:T(28,36)=2:T(28,37)=5:T(28,40)=6:T(28,41)=5:T(28,42)=1:T(28,43)=2:T(28,44)=5:T(28,46)=1:T(28,47)=10
193 T(28,49)=5:T(28,50)=5:T(28,55)=2:T(28,56)=5
195 T(29,30)=10
196 T(29,33)=10:T(29,35)=10:T(29,36)=10:T(29,37)=10:T(29,38)=5:T(29,39)=3:T(29,41)=4:T(29,42)=1:T(29,43)=3:T(29,44)=10:T(29,47)=10
197 T(29,48)=5:T(29,49)=1:T(29,50)=1:T(29,51)=5:T(29,52)=5:T(29,53)=3:T(29,54)=2:T(29,55)=3:T(29,56)=1
198 T(30,32)=10:T(30,33)=5:T(30,34)=5:T(30,36)=2:T(30,37)=4:T(30,39)=1:T(30,42)=10:T(30,49)=6:T(30,51)=2:T(30,52)=3:T(30,54)=1:T(30,55)=1:T(30,56)=5
199 T(31,32)=1:T(31,33)=2:T(31,34)=3:T(31,35)=2:T(31,36)=5:T(31,37)=5:T(31,40)=2:T(31,41)=2:T(31,42)=5:T(31,43)=10:T(31,44)=10:T(31,45)=10:T(31,47)=5:T(31,50)=3:T(31,53)=1:T(31,54)=1
200 T(32,33)=4:T(32,34)=2:T(32,35)=5:T(32,36)=5:T(32,38)=2:T(32,39)=2:T(32,42)=2:T(32,43)=2:T(32,44)=2:T(32,45)=1:T(32,46)=5:T(32,48)=5:T(32,50)=5:T(32,51)=1:T(32,53)=4:T(32,54)=1:T(32,55)=5
201 T(33,35)=1:T(33,36)=1:T(33,37)=1:T(33,38)=5:T(33,39)=2:T(33,40)=2:T(33,42)=5:T(33,43)=10:T(33,46)=2:T(33,47)=5:T(33,48)=6:T(33,49)=5:T(33,50)=5:T(33,51)=1:T(33,52)=1:T(33,53)=5:T(33,54)=10:T(33,55)=1:T(33,56)=2
202 T(34,35)=5:T(34,37)=10:T(34,39)=5:T(34,41)=5:T(34,42)=3:T(34,43)=2:T(34,44)=3:T(34,46)=10:T(34,47)=5:T(34,48)=10:T(34,50)=6:T(34,51)=2:T(34,53)=6:T(34,54)=1:T(34,55)=4
203 T(35,36)=10:T(35,38)=2:T(35,40)=5:T(35,42)=1:T(35,43)=4:T(35,44)=4:T(35,45)=6:T(35,47)=5:T(35,48)=2:T(35,51)=1:T(35,52)=2:T(35,53)=1:T(35,54)=1:T(35,55)=5:T(35,56)=4
204 T(36,37)=1:T(36,38)=5:T(36,41)=1:T(36,42)=3:T(36,43)=2:T(36,44)=5:T(36,45)=4:T(36,47)=2:T(36,49)=1:T(36,50)=1:T(36,51)=10:T(36,52)=1:T(36,53)=10:T(36,54)=5:T(36,56)=5
205 T(37,38)=5:T(37,39)=3:T(37,42)=3:T(37,43)=1:T(37,45)=5:T(37,47)=5:T(37,50)=2:T(37,51)=5:T(37,52)=5:T(37,53)=5:T(37,54)=2:T(37,55)=2:T(37,56)=1
206 T(38,39)=2:T(38,44)=1:T(38,45)=4:T(38,47)=1:T(38,50)=3:T(38,51)=1:T(38,53)=10:T(38,54)=3:T(38,55)=5:T(38,56)=1
207 T(39,40)=5:T(39,41)=3:T(39,45)=2:T(39,46)=2:T(39,47)=2:T(39,48)=5:T(39,49)=2:T(39,50)=2:T(39,52)=4:T(39,55)=5:T(39,56)=5
208 T(40,41)=5:T(40,43)=5:T(40,44)=5:T(40,45)=2:T(40,46)=2:T(40,48)=2:T(40,49)=5:T(40,50)=2:T(40,51)=2:T(40,52)=10:T(40,53)=5:T(40,54)=2
209 T(41,42)=5:T(41,43)=2:T(41,44)=5:T(41,45)=2:T(41,46)=5:T(41,47)=5:T(41,48)=5:T(41,49)=2:T(41,50)=5:T(41,51)=10:T(41,54)=3:T(41,55)=1
210 T(42,44)=5:T(42,47)=2:T(42,48)=2:T(42,49)=6:T(42,50)=2:T(42,51)=2:T(42,52)=2:T(42,53)=5:T(42,54)=2:T(42,55)=5:T(42,56)=10
211 T(43,45)=10:T(43,46)=5:T(43,47)=4:T(43,49)=1:T(43,50)=2:T(43,51)=1:T(43,54)=2:T(43,55)=10:T(43,56)=3
212 T(44,46)=5:T(44,47)=2:T(44,48)=1:T(44,52)=10:T(44,55)=2:T(44,56)=2
213 T(45,46)=10:T(45,48)=2:T(45,50)=3:T(45,51)=1:T(45,53)=5:T(45,54)=3: T(45,56)=10
214 T(46,47)=5:T(46,48)=2:T(46,49)=1:T(46,50)=5:T(46,51)=6:T(46,54)=5:T(46,55)=1:T(46,56)=2
215 T(47,48)=2:T(47,49)=3:T(47,50)=2:T(47,52)=2:T(47,55)=1:T(47,56)=1
216 T(48,50)=2:T(48,51)=2:T(48,52)=5:T(48,54)=5
217 T(49,51)=5:T(49,53)=4:T(49,56)=5
218 T(50,51)=6:T(50,52)=5:T(50,53)=6:T(50,55)=5:T(50,56)=3
219 T(51,52)=5:T(51,53)=2:T(51,54)=4:T(51,55)=2:T(51,56)=2:T(52,53)=2:T(52,55)=5:T(52,56)=5:T(53,54)=1:T(53,55)=1:T(54,55)=1:T(54,56)=5:T(55,56)=5
220 FOR JJJJ=-32000 TO 32000
221 RANDOMIZE JJJJ
222 M=-1D+17
223 FOR I=1 TO 58
224 A(I)=1+FIX(RND*6)
225 NEXT I
226 IMAR=10+FIX(RND*2000)
228 FOR I=1 TO IMAR
229 FOR KK=1 TO 58
231 X(KK)=A(KK)
232 NEXT KK
242 IJL=1+FIX(RND*58):IJM=1+FIX(RND*58):IJN=1+FIX(RND*58)
253 IF RND<.7 THEN X(IJL)=1+FIX(RND*6) ELSE IF RND<.05 THEN X(IJL)=A(IJL) ELSE GOTO 264
255 GOTO 351
264 X(IJM)=A(IJN):X(IJN)=A(IJM)
301 IF RND<.5 GOTO 351
302 IJM=1+FIX(RND*58):IJN=1+FIX(RND*58)
304 X(IJM)=A(IJN):X(IJN)=A(IJM)
351 FOR K=1 TO 58
361 FOR J=K+1 TO 58
363 IF X(K)=X(J) THEN TZ(K,J)=T(K,J) ELSE TZ(K,J)=0
366 NEXT J
399 NEXT K
1590 SUMTZ=0
1591 FOR K=1 TO 58
1594 FOR J=K+1 TO 58
1596 SUMTZ=SUMTZ+TZ(K,J)
1597 NEXT J
1598 NEXT K
1609 P=-SUMTZ
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 58
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 228
1670 NEXT I
1890 IF M>-240 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)
1915 PRINT A(16),A(17),A(18),A(19),A(20)
1916 PRINT A(21),A(22),A(23),A(24),A(25)
1917 PRINT A(26),A(27),A(28),A(29),A(30)
1918 PRINT A(31),A(32),A(33),A(34),A(35)
1919 PRINT A(36),A(37),A(38),A(39),A(40)
1920 PRINT A(41),A(42),A(43),A(44),A(45)
1921 PRINT A(46),A(47),A(48),A(49),A(50)
1922 PRINT A(51),A(52),A(53),A(54),A(55)
1927 PRINT A(56),M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the best candidate solutions produced during the first 4.1 hours of running are presented below. What immediately follows is a manual copy from the computer screen.

44234
15215
16121
12253
24346
65526
51224
63546
14332
56533
41136
5 -218 -31457

15345
25461
11622
15423
43215
64412
16415
33423
54226
36362
46565
3 -213 -31397

213 may be or may not be optimal. Interpreted in accordance with line 1912 through line 1927, the candidate solutions presented above were produced during the first 4.1 hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

References

Carlson, R. C., and G. L. Nemhauser, "Scheduling to Minimize Interaction Cost," Operations Research 14, 52-58 (Jan.-Feb., 1966).

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).

Skorin-Kapov, J., "Tabu Search Applied to the Quadratic Assignment Problem," ORSA Journal on Computing 2, 33-45 (1990).

Vredeveld, T., and J. K. Lenstra, "On Local Search for the Generalized Graph Coloring Problem,"Operations Research Letters 31, 28-34 (2003).

An Integer-Programming Computer Program Applied to a One-Dimensional Space Allocation Problem

Jsun Yui Wong

The computer program listed below seeks to solve Problem S8 of Amaral (2006), which is a problem from Simmons (1969). In order to have integer locations, the department lengths used in the computer program below have been made twice as long as the given department lengths.

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 TBM(33,33),TZ(33,33)
11 TBM(1,2)=5:TBM(1,3)=6:TBM(1,4)=7:TBM(1,5)=8:TBM(1,6)=5:TBM(1,7)=9:TBM(1,8)=6
12 TBM(2,3)=7:TBM(2,4)=8:TBM(2,5)=9:TBM(2,6)=6:TBM(2,7)=10:TBM(2,8)=7
13 TBM(3,4)=9:TBM(3,5)=10:TBM(3,6)=7:TBM(3,7)=11:TBM(3,8)=8
14 TBM(4,5)=11:TBM(4,6)=8:TBM(4,7)=12:TBM(4,8)=9
15 TBM(5,6)=9:TBM(5,7)=13:TBM(5,8)=10
16 TBM(6,7)=10:TBM(6,8)=7
17 TBM(7,8)=11
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 8
88 A(I)=FIX(RND*99)
89 NEXT I
126 IMAR=10+FIX(RND*2000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 8
131 X(KK)=A(KK)
132 NEXT KK
151 JK=1+FIX(RND*8)
153 X(JK)=FIX(RND*99)
351 FOR K=1 TO 7
361 FOR J=K+1 TO 8
364 IF ABS(X(K)-X(J))366 NEXT J
399 NEXT K
1590 SUMTZ=0
1591 FOR K=1 TO 7
1594 FOR J=K+1 TO 8
1596 SUMTZ=SUMTZ+TZ(K,J)
1597 NEXT J
1598 NEXT K
1623 PR1=-6*ABS(X(1)-X(2))-4*ABS(X(1)-X(3))-1*ABS(X(1)-X(4))-7*ABS(X(1)-X(5))-3*ABS(X(1)-X(6))-5*ABS(X(1)-X(7))-0*ABS(X(1)-X(8))
1624 PR2=-1*ABS(X(2)-X(3))-2*ABS(X(2)-X(4))-5*ABS(X(2)-X(5))-2*ABS(X(2)-X(6))-4*ABS(X(2)-X(7))-3*ABS(X(2)-X(8))
1625 PR3=0*ABS(X(3)-X(4))-6*ABS(X(3)-X(5))-3*ABS(X(3)-X(6))-2*ABS(X(3)-X(7))-2*ABS(X(3)-X(8))
1626 PR4=-3*ABS(X(4)-X(5))-4*ABS(X(4)-X(6))-0*ABS(X(4)-X(7))-1*ABS(X(4)-X(8))
1627 PR5=-0*ABS(X(5)-X(6))-6*ABS(X(5)-X(7))-6*ABS(X(5)-X(8))-3*ABS(X(6)-X(7))-5*ABS(X(6)-X(8))-2*ABS(X(7)-X(8))
1650 P=PR1+PR2+PR3+PR4+PR5-SUMTZ
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>-1605 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 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 output produced during the first hour of running is presented below. What immediately follows is a manual copy from the computer screen.

48 53 30 7 40
15 63 22 -1602 -29841

44 39 62 85 52
77 29 70 -1602 -28965

65 70 47 24 57
32 80 39 -1602 -27466

1602 is optimal. Interpreted in accordance with line 1912 and line 1913, the output through JJJJ=-27466 was produced during the first hour of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

References

Amaral, A. R. S., "On the exact solution of a facility layout problem," European Journal of Operational Research 173, 508-518 (2006).

Simmons, D. M., "One-dimensional space allocation: an ordering algorithm," Operations Research 17, 812-826 (1969).