A Computer Program Illustrating an Ordering Algorithm for Eighteen Departments, Second Edition

Jsun Yui Wong

The complete computer program listed below seeks to solve Problem P18 of Amaral (2008), which is an instance of the allocation problem of Simmons (1969). In order to have integer locations, the department lengths used in the following computer program are twice as long as the original 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 T(33,33),TZ(33,33)
11 T(1,2)=23:T(1,3)=29:T(1,4)=23:T(1,5)=27:T(1,6)=23:T(1,7)=27:T(1,8)=25:T(1,9)=29:T(1,10)=26:T(1,11)=25:T(1,12)=23:T(1,13)=29:T(1,14)=23:T(1,15)=27
12 T(2,3)=12:T(2,4)=6:T(2,5)=10:T(2,6)=6:T(2,7)=10:T(2,8)=8:T(2,9)=12:T(2,10)=9:T(2,11)=8:T(2,12)=6:T(2,13)=12:T(2,14)=6:T(2,15)=10
13 T(3,4)=12:T(3,5)=16:T(3,6)=12:T(3,7)=16:T(3,8)=14:T(3,9)=18:T(3,10)=15:T(3,11)=14:T(3,12)=12:T(3,13)=18:T(3,14)=12:T(3,15)=16
14 T(4,5)=10:T(4,6)=6:T(4,7)=10:T(4,8)=8:T(4,9)=12:T(4,10)=9:T(4,11)=8:T(4,12)=6:T(4,13)=12:T(4,14)=6:T(4,15)=10
15 T(5,6)=10:T(5,7)=14:T(5,8)=12:T(5,9)=16:T(5,10)=13:T(5,11)=12:T(5,12)=10:T(5,13)=16:T(5,14)=10:T(5,15)=14
16 T(6,7)=10:T(6,8)=8:T(6,9)=12:T(6,10)=9:T(6,11)=8:T(6,12)=6:T(6,13)=12:T(6,14)=6:T(6,15)=10
17 T(7,8)=12:T(7,9)=16:T(7,10)=13:T(7,11)=12:T(7,12)=10:T(7,13)=16:T(7,14)=10:T(7,15)=14
18 T(8,9)=14:T(8,10)=11:T(8,11)=10:T(8,12)=8:T(8,13)=14:T(8,14)=8:T(8,15)=12
19 T(9,10)=15:T(9,11)=14:T(9,12)=12:T(9,13)=18:T(9,14)=12:T(9,15)=16
20 T(10,11)=11:T(10,12)=9:T(10,13)=15:T(10,14)=9:T(10,15)=13
21 T(11,12)=8:T(11,13)=14:T(11,14)=8:T(11,15)=12:T(12,13)=12:T(12,14)=6:T(12,15)=10:T(13,14)=12:T(13,15)=16:T(14,15)=10
31 T(1,16)=23:T(1,17)=27:T(1,18)=25:T(2,16)=6:T(2,17)=10:T(2,18)=8:T(3,16)=12:T(3,17)=16:T(3,18)=14:T(4,16)=6:T(4,17)=10:T(4,18)=8:T(5,16)=10:T(5,17)=14
32 T(5,18)=12:T(6,16)=6:T(6,17)=10:T(6,18)=8:T(7,16)=10:T(7,17)=14:T(7,18)=12:T(8,16)=8:T(8,17)=12:T(8,18)=10:T(9,16)=12:T(9,17)=16:T(9,18)=14:T(10,16)=9
33 T(10,17)=13:T(10,18)=11:T(11,16)=8:T(11,17)=12:T(11,18)=10:T(12,16)=6:T(12,17)=10:T(12,18)=8:T(13,16)=12:T(13,17)=16:T(13,18)=14:T(14,16)=6:T(14,17)=10
34 T(14,18)=8:T(15,16)=10:T(15,17)=14:T(15,18)=12:T(16,17)=10:T(16,18)=8:T(17,18)=12
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 18
88 A(I)=FIX(RND*699)
89 NEXT I
126 REM IMAR=10+FIX(RND*32000)
128 FOR I=1 TO 32000
129 FOR KK=1 TO 18
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*18):IJM=1+FIX(RND*18):IJN=1+FIX(RND*18)
233 IF RND<.7 THEN X(IJL)=FIX(RND*699) ELSE IF RND<.05 THEN X(IJL)=A(IJL)-1 ELSE GOTO 244
235 GOTO 351
244 X(IJM)=A(IJN):X(IJN)=A(IJM)
351 FOR K=1 TO 17
361 FOR J=K+1 TO 18
364 IF T(K,J)>ABS(X(K)-X(J)) THEN TZ(K,J)=99999! ELSE TZ(K,J)=0
366 NEXT J
399 NEXT K
1590 SUMTZ=0
1591 FOR K=1 TO 17
1594 FOR J=K+1 TO 18
1596 SUMTZ=SUMTZ+TZ(K,J)
1597 NEXT J
1598 NEXT K
1623 PR1=-0*ABS(X(1)-X(2))-5*ABS(X(1)-X(3))-0*ABS(X(1)-X(4))-5*ABS(X(1)-X(5))-2*ABS(X(1)-X(6))-10*ABS(X(1)-X(7))-3*ABS(X(1)-X(8))-1*ABS(X(1)-X(9))-5*ABS(X(1)-X(10))-5*ABS(X(1)-X(11))-5*ABS(X(1)-X(12))-0*ABS(X(1)-X(13))-0*ABS(X(1)-X(14))-5*ABS(X(1)-X(15))
1624 PR2=-3*ABS(X(2)-X(3))-10*ABS(X(2)-X(4))-5*ABS(X(2)-X(5))-1*ABS(X(2)-X(6))-5*ABS(X(2)-X(7))-1*ABS(X(2)-X(8))-2*ABS(X(2)-X(9))-4*ABS(X(2)-X(10))-2*ABS(X(2)-X(11))-5*ABS(X(2)-X(12))-0*ABS(X(2)-X(13))-10*ABS(X(2)-X(14))-10*ABS(X(2)-X(15))
1625 PR3=-2*ABS(X(3)-X(4))-0*ABS(X(3)-X(5))-5*ABS(X(3)-X(6))-2*ABS(X(3)-X(7))-4*ABS(X(3)-X(8))-4*ABS(X(3)-X(9))-5*ABS(X(3)-X(10))-0*ABS(X(3)-X(11))-0*ABS(X(3)-X(12))-0*ABS(X(3)-X(13))-5*ABS(X(3)-X(14))-1*ABS(X(3)-X(15))
1626 PR4=-1*ABS(X(4)-X(5))-0*ABS(X(4)-X(6))-5*ABS(X(4)-X(7))-2*ABS(X(4)-X(8))-1*ABS(X(4)-X(9))-0*ABS(X(4)-X(10))-10*ABS(X(4)-X(11))-2*ABS(X(4)-X(12))-2*ABS(X(4)-X(13))-0*ABS(X(4)-X(14))-2*ABS(X(4)-X(15))
1627 PR5=-5*ABS(X(5)-X(6))-6*ABS(X(5)-X(7))-5*ABS(X(5)-X(8))-2*ABS(X(5)-X(9))-5*ABS(X(5)-X(10))-2*ABS(X(5)-X(11))-0*ABS(X(5)-X(12))-5*ABS(X(5)-X(13))-1*ABS(X(5)-X(14))-1*ABS(X(5)-X(15))
1628 PR6=-5*ABS(X(6)-X(7))-2*ABS(X(6)-X(8))-1*ABS(X(6)-X(9))-6*ABS(X(6)-X(10))-0*ABS(X(6)-X(11))-0*ABS(X(6)-X(12))-10*ABS(X(6)-X(13))-0*ABS(X(6)-X(14))-2*ABS(X(6)-X(15))
1629 PR7=-0*ABS(X(7)-X(8))-0*ABS(X(7)-X(9))-0*ABS(X(7)-X(10))-5*ABS(X(7)-X(11))-10*ABS(X(7)-X(12))-2*ABS(X(7)-X(13))-2*ABS(X(7)-X(14))-5*ABS(X(7)-X(15))
1630 PR8=-1*ABS(X(8)-X(9))-1*ABS(X(8)-X(10))-10*ABS(X(8)-X(11))-10*ABS(X(8)-X(12))-2*ABS(X(8)-X(13))-0*ABS(X(8)-X(14))-10*ABS(X(8)-X(15))
1631 PR9=-2*ABS(X(9)-X(10))-0*ABS(X(9)-X(11))-3*ABS(X(9)-X(12))-5*ABS(X(9)-X(13))-5*ABS(X(9)-X(14))-0*ABS(X(9)-X(15))
1632 PR10=-5*ABS(X(10)-X(11))-5*ABS(X(10)-X(12))-0*ABS(X(10)-X(13))-5*ABS(X(10)-X(14))-1*ABS(X(10)-X(15))
1633 PR11=-5*ABS(X(11)-X(12))-2*ABS(X(11)-X(13))-5*ABS(X(11)-X(14))-1*ABS(X(11)-X(15))
1636 PR12=-2*ABS(X(12)-X(13))-10*ABS(X(12)-X(14))-5*ABS(X(12)-X(15))-2*ABS(X(13)-X(14))-2*ABS(X(13)-X(15))-5*ABS(X(14)-X(15))
1638 PR21=-4*ABS(X(1)-X(16))-4*ABS(X(1)-X(17))-0*ABS(X(1)-X(18))-3*ABS(X(2)-X(16))-0*ABS(X(2)-X(17))-5*ABS(X(2)-X(18))-0*ABS(X(3)-X(16))-0*ABS(X(3)-X(17))-5*ABS(X(3)-X(18))-1*ABS(X(4)-X(16))-5*ABS(X(4)-X(17))-2*ABS(X(4)-X(18))
1639 PR22=-1*ABS(X(5)-X(16))-5*ABS(X(5)-X(17))-2*ABS(X(5)-X(18))-0*ABS(X(6)-X(16))-1*ABS(X(6)-X(17))-0*ABS(X(6)-X(18))-1*ABS(X(7)-X(16))-2*ABS(X(7)-X(17))-1*ABS(X(7)-X(18))-2*ABS(X(8)-X(16))-5*ABS(X(8)-X(17))-2*ABS(X(8)-X(18))
1640 PR23=-5*ABS(X(9)-X(16))-0*ABS(X(9)-X(17))-0*ABS(X(9)-X(18))-0*ABS(X(10)-X(16))-0*ABS(X(10)-X(17))-5*ABS(X(10)-X(18))-10*ABS(X(11)-X(16))-0*ABS(X(11)-X(17))-2*ABS(X(11)-X(18))-0*ABS(X(12)-X(16))-1*ABS(X(12)-X(17))-1*ABS(X(12)-X(18))
1642 PR24=-1*ABS(X(13)-X(16))-0*ABS(X(13)-X(17))-0*ABS(X(13)-X(18))
1643 PR25=-5*ABS(X(14)-X(16))-1*ABS(X(14)-X(17))-5*ABS(X(14)-X(18))-3*ABS(X(15)-X(16))-0*ABS(X(15)-X(17))-5*ABS(X(15)-X(18))-0*ABS(X(16)-X(17))-0*ABS(X(16)-X(18))-5*ABS(X(17)-X(18))
1650 P=PR1+PR2+PR3+PR4+PR5+PR6+PR7+PR8+PR9+PR10+PR11+PR12+PR21+PR22+PR23+PR24+PR25-SUMTZ
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 18
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-21400 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),M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW-BASIC 3.11 interpreter, and the output produced in the first 27 hours of running is presented below. What immediately follows is a manual copy from the computer screen.

158 261 321 249 287
309 199 231 357 300
241 223 339 267 213
255 185 275 -21391 -31667

605 488 442 540 564
454 550 516 406 463
532 508 424 482 498
524 578 474 -21301 -31563

463 352 300 358 422
312 408 382 264 321
366 374 282 340 394
346 436 332 -21365 -31489

421 304 258 356 380
270 366 332 222 279
348 324 240 298 314
340 394 290 -21301 -31343

21301 is optimal, Amaral (2008, p. 1030). Interpreted in accordance with line 1912 through line 1915, the output through JJJJ=-31343 was produced in the first 27 hours of running on a personal computer with an Intel 2.66 GHz. chip and the Microsoft interpreter, which is not a compiler.

References

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

Amaral, A. R. S., 2008. An exact approach to the one-dimensional facility layout problem. Operations Research 56, 1026-1033.

Simmons, D. M., 1969. One-dimensioanl space allocation: An ordering algorithm. Operations Research 17, 812-826.

ERRATA in "A Computer Program Illustrating an Ordering Algorithm for Eighteen Departments"

ERRATA in "A Computer Program Illustrating an Ordering Algorithm for Eighteen Departments"

Jsun Yui Wong

Line 364 and line 366 of the September 22 post of the present blog should read as follows:

364 IF ABS(X(K)-X(J)) less than T(K,J) THEN TZ(K,J)=99999! ELSE TZ(K,J)=0
366 NEXT J

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

A Computer Program Illustrating an Ordering Algorithm for Eighteen Departments

Jsun Yui Wong

The complete computer program listed below seeks to solve Problem P18 of Amaral (2008), which is an instance of the allocation problem of Simmons (1969). In order to have integer locations, the department lengths used in the following computer program are twice as long as the original 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 T(33,33),TZ(33,33)
11 T(1,2)=23:T(1,3)=29:T(1,4)=23:T(1,5)=27:T(1,6)=23:T(1,7)=27:T(1,8)=25:T(1,9)=29:T(1,10)=26:T(1,11)=25:T(1,12)=23:T(1,13)=29:T(1,14)=23:T(1,15)=27
12 T(2,3)=12:T(2,4)=6:T(2,5)=10:T(2,6)=6:T(2,7)=10:T(2,8)=8:T(2,9)=12:T(2,10)=9:T(2,11)=8:T(2,12)=6:T(2,13)=12:T(2,14)=6:T(2,15)=10
13 T(3,4)=12:T(3,5)=16:T(3,6)=12:T(3,7)=16:T(3,8)=14:T(3,9)=18:T(3,10)=15:T(3,11)=14:T(3,12)=12:T(3,13)=18:T(3,14)=12:T(3,15)=16
14 T(4,5)=10:T(4,6)=6:T(4,7)=10:T(4,8)=8:T(4,9)=12:T(4,10)=9:T(4,11)=8:T(4,12)=6:T(4,13)=12:T(4,14)=6:T(4,15)=10
15 T(5,6)=10:T(5,7)=14:T(5,8)=12:T(5,9)=16:T(5,10)=13:T(5,11)=12:T(5,12)=10:T(5,13)=16:T(5,14)=10:T(5,15)=14
16 T(6,7)=10:T(6,8)=8:T(6,9)=12:T(6,10)=9:T(6,11)=8:T(6,12)=6:T(6,13)=12:T(6,14)=6:T(6,15)=10
17 T(7,8)=12:T(7,9)=16:T(7,10)=13:T(7,11)=12:T(7,12)=10:T(7,13)=16:T(7,14)=10:T(7,15)=14
18 T(8,9)=14:T(8,10)=11:T(8,11)=10:T(8,12)=8:T(8,13)=14:T(8,14)=8:T(8,15)=12
19 T(9,10)=15:T(9,11)=14:T(9,12)=12:T(9,13)=18:T(9,14)=12:T(9,15)=16
20 T(10,11)=11:T(10,12)=9:T(10,13)=15:T(10,14)=9:T(10,15)=13
21 T(11,12)=8:T(11,13)=14:T(11,14)=8:T(11,15)=12:T(12,13)=12:T(12,14)=6:T(12,15)=10:T(13,14)=12:T(13,15)=16:T(14,15)=10
31 T(1,16)=23:T(1,17)=27:T(1,18)=25:T(2,16)=6:T(2,17)=10:T(2,18)=8:T(3,16)=12:T(3,17)=16:T(3,18)=14:T(4,16)=6:T(4,17)=10:T(4,18)=8:T(5,16)=10:T(5,17)=14
32 T(5,18)=12:T(6,16)=6:T(6,17)=10:T(6,18)=8:T(7,16)=10:T(7,17)=14:T(7,18)=12:T(8,16)=8:T(8,17)=12:T(8,18)=10:T(9,16)=12:T(9,17)=16:T(9,18)=14:T(10,16)=9
33 T(10,17)=13:T(10,18)=11:T(11,16)=8:T(11,17)=12:T(11,18)=10:T(12,16)=6:T(12,17)=10:T(12,18)=8:T(13,16)=12:T(13,17)=16:T(13,18)=14:T(14,16)=6:T(14,17)=10
34 T(14,18)=8:T(15,16)=10:T(15,17)=14:T(15,18)=12:T(16,17)=10:T(16,18)=8:T(17,18)=12
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 18
88 A(I)=FIX(RND*699)
89 NEXT I
126 REM IMAR=10+FIX(RND*32000)
128 FOR I=1 TO 32000
129 FOR KK=1 TO 18
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*18):IJM=1+FIX(RND*18):IJN=1+FIX(RND*18)
233 IF RND<.7 THEN X(IJL)=FIX(RND*699) ELSE IF RND<.05 THEN X(IJL)=A(IJL)-1 ELSE GOTO 244
235 GOTO 351
244 X(IJM)=A(IJN):X(IJN)=A(IJM)
351 FOR K=1 TO 17
361 FOR J=K+1 TO 18
364 IF ABS(X(K)-X(J))366 NEXT J
399 NEXT K
1590 SUMTZ=0
1591 FOR K=1 TO 17
1594 FOR J=K+1 TO 18
1596 SUMTZ=SUMTZ+TZ(K,J)
1597 NEXT J
1598 NEXT K
1623 PR1=-0*ABS(X(1)-X(2))-5*ABS(X(1)-X(3))-0*ABS(X(1)-X(4))-5*ABS(X(1)-X(5))-2*ABS(X(1)-X(6))-10*ABS(X(1)-X(7))-3*ABS(X(1)-X(8))-1*ABS(X(1)-X(9))-5*ABS(X(1)-X(10))-5*ABS(X(1)-X(11))-5*ABS(X(1)-X(12))-0*ABS(X(1)-X(13))-0*ABS(X(1)-X(14))-5*ABS(X(1)-X(15))
1624 PR2=-3*ABS(X(2)-X(3))-10*ABS(X(2)-X(4))-5*ABS(X(2)-X(5))-1*ABS(X(2)-X(6))-5*ABS(X(2)-X(7))-1*ABS(X(2)-X(8))-2*ABS(X(2)-X(9))-4*ABS(X(2)-X(10))-2*ABS(X(2)-X(11))-5*ABS(X(2)-X(12))-0*ABS(X(2)-X(13))-10*ABS(X(2)-X(14))-10*ABS(X(2)-X(15))
1625 PR3=-2*ABS(X(3)-X(4))-0*ABS(X(3)-X(5))-5*ABS(X(3)-X(6))-2*ABS(X(3)-X(7))-4*ABS(X(3)-X(8))-4*ABS(X(3)-X(9))-5*ABS(X(3)-X(10))-0*ABS(X(3)-X(11))-0*ABS(X(3)-X(12))-0*ABS(X(3)-X(13))-5*ABS(X(3)-X(14))-1*ABS(X(3)-X(15))
1626 PR4=-1*ABS(X(4)-X(5))-0*ABS(X(4)-X(6))-5*ABS(X(4)-X(7))-2*ABS(X(4)-X(8))-1*ABS(X(4)-X(9))-0*ABS(X(4)-X(10))-10*ABS(X(4)-X(11))-2*ABS(X(4)-X(12))-2*ABS(X(4)-X(13))-0*ABS(X(4)-X(14))-2*ABS(X(4)-X(15))
1627 PR5=-5*ABS(X(5)-X(6))-6*ABS(X(5)-X(7))-5*ABS(X(5)-X(8))-2*ABS(X(5)-X(9))-5*ABS(X(5)-X(10))-2*ABS(X(5)-X(11))-0*ABS(X(5)-X(12))-5*ABS(X(5)-X(13))-1*ABS(X(5)-X(14))-1*ABS(X(5)-X(15))
1628 PR6=-5*ABS(X(6)-X(7))-2*ABS(X(6)-X(8))-1*ABS(X(6)-X(9))-6*ABS(X(6)-X(10))-0*ABS(X(6)-X(11))-0*ABS(X(6)-X(12))-10*ABS(X(6)-X(13))-0*ABS(X(6)-X(14))-2*ABS(X(6)-X(15))
1629 PR7=-0*ABS(X(7)-X(8))-0*ABS(X(7)-X(9))-0*ABS(X(7)-X(10))-5*ABS(X(7)-X(11))-10*ABS(X(7)-X(12))-2*ABS(X(7)-X(13))-2*ABS(X(7)-X(14))-5*ABS(X(7)-X(15))
1630 PR8=-1*ABS(X(8)-X(9))-1*ABS(X(8)-X(10))-10*ABS(X(8)-X(11))-10*ABS(X(8)-X(12))-2*ABS(X(8)-X(13))-0*ABS(X(8)-X(14))-10*ABS(X(8)-X(15))
1631 PR9=-2*ABS(X(9)-X(10))-0*ABS(X(9)-X(11))-3*ABS(X(9)-X(12))-5*ABS(X(9)-X(13))-5*ABS(X(9)-X(14))-0*ABS(X(9)-X(15))
1632 PR10=-5*ABS(X(10)-X(11))-5*ABS(X(10)-X(12))-0*ABS(X(10)-X(13))-5*ABS(X(10)-X(14))-1*ABS(X(10)-X(15))
1633 PR11=-5*ABS(X(11)-X(12))-2*ABS(X(11)-X(13))-5*ABS(X(11)-X(14))-1*ABS(X(11)-X(15))
1636 PR12=-2*ABS(X(12)-X(13))-10*ABS(X(12)-X(14))-5*ABS(X(12)-X(15))-2*ABS(X(13)-X(14))-2*ABS(X(13)-X(15))-5*ABS(X(14)-X(15))
1638 PR21=-4*ABS(X(1)-X(16))-4*ABS(X(1)-X(17))-0*ABS(X(1)-X(18))-3*ABS(X(2)-X(16))-0*ABS(X(2)-X(17))-5*ABS(X(2)-X(18))-0*ABS(X(3)-X(16))-0*ABS(X(3)-X(17))-5*ABS(X(3)-X(18))-1*ABS(X(4)-X(16))-5*ABS(X(4)-X(17))-2*ABS(X(4)-X(18))
1639 PR22=-1*ABS(X(5)-X(16))-5*ABS(X(5)-X(17))-2*ABS(X(5)-X(18))-0*ABS(X(6)-X(16))-1*ABS(X(6)-X(17))-0*ABS(X(6)-X(18))-1*ABS(X(7)-X(16))-2*ABS(X(7)-X(17))-1*ABS(X(7)-X(18))-2*ABS(X(8)-X(16))-5*ABS(X(8)-X(17))-2*ABS(X(8)-X(18))
1640 PR23=-5*ABS(X(9)-X(16))-0*ABS(X(9)-X(17))-0*ABS(X(9)-X(18))-0*ABS(X(10)-X(16))-0*ABS(X(10)-X(17))-5*ABS(X(10)-X(18))-10*ABS(X(11)-X(16))-0*ABS(X(11)-X(17))-2*ABS(X(11)-X(18))-0*ABS(X(12)-X(16))-1*ABS(X(12)-X(17))-1*ABS(X(12)-X(18))
1642 PR24=-1*ABS(X(13)-X(16))-0*ABS(X(13)-X(17))-0*ABS(X(13)-X(18))
1643 PR25=-5*ABS(X(14)-X(16))-1*ABS(X(14)-X(17))-5*ABS(X(14)-X(18))-3*ABS(X(15)-X(16))-0*ABS(X(15)-X(17))-5*ABS(X(15)-X(18))-0*ABS(X(16)-X(17))-0*ABS(X(16)-X(18))-5*ABS(X(17)-X(18))
1650 P=PR1+PR2+PR3+PR4+PR5+PR6+PR7+PR8+PR9+PR10+PR11+PR12+PR21+PR22+PR23+PR24+PR25-SUMTZ
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 18
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-21400 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),M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW-BASIC 3.11 interpreter, and the output produced within the first 24 hours of running is presented below. What immediately follows is a manual copy from the computer screen.

158 261 321 249 287
309 199 231 357 300
241 223 339 267 213
255 185 275 -21391 -31667

605 488 442 540 564
454 550 516 406 463
532 508 424 482 498
524 578 474 -21301 -31563

21301 is optimal, Amaral (2008, p. 1030). Interpreted in accordance with line 1912 through line 1915, the output above was produced within the first 24 hours of running on a personal computer with an Intel 2.66 GHz. chip and the Microsoft interpreter, which is not a compiler.

References

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

Amaral, A. R. S., 2008. An exact approach to the one-dimensional facility layout problem. Operations Research 56, 1026-1033.

Simmons, D. M., 1969. One-dimensioanl space allocation: An ordering algorithm. Operations Research 17, 812-826.

ERRATA in "A Computer Program Illustrating an Ordering Algorithm"

Jsun Yui Wong

Line 364 and line 366 of the September 19 post of the present blog should read as follows:

364 IF ABS(X(K)-X(J)) less than T(K,J) THEN TZ(K,J)=99999! ELSE TZ(K,J)=0
366 NEXT J

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

A Computer Program Illustrating an Ordering Algorithm

Jsun Yui Wong

The complete computer program listed below seeks to solve Problem P15 of Amaral (2006), which is an instance of the allocation problem of Simmons (1969). In order to have integer locations, the department lengths used in the following computer program are twice as long as the original 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 T(33,33),TZ(33,33)
11 T(1,2)=23:T(1,3)=29:T(1,4)=23:T(1,5)=27:T(1,6)=23:T(1,7)=27:T(1,8)=25:T(1,9)=29:T(1,10)=26:T(1,11)=25:T(1,12)=23:T(1,13)=29:T(1,14)=23:T(1,15)=27
12 T(2,3)=12:T(2,4)=6:T(2,5)=10:T(2,6)=6:T(2,7)=10:T(2,8)=8:T(2,9)=12:T(2,10)=9:T(2,11)=8:T(2,12)=6:T(2,13)=12:T(2,14)=6:T(2,15)=10
13 T(3,4)=12:T(3,5)=16:T(3,6)=12:T(3,7)=16:T(3,8)=14:T(3,9)=18:T(3,10)=15:T(3,11)=14:T(3,12)=12:T(3,13)=18:T(3,14)=12:T(3,15)=16
14 T(4,5)=10:T(4,6)=6:T(4,7)=10:T(4,8)=8:T(4,9)=12:T(4,10)=9:T(4,11)=8:T(4,12)=6:T(4,13)=12:T(4,14)=6:T(4,15)=10
15 T(5,6)=10:T(5,7)=14:T(5,8)=12:T(5,9)=16:T(5,10)=13:T(5,11)=12:T(5,12)=10:T(5,13)=16:T(5,14)=10:T(5,15)=14
16 T(6,7)=10:T(6,8)=8:T(6,9)=12:T(6,10)=9:T(6,11)=8:T(6,12)=6:T(6,13)=12:T(6,14)=6:T(6,15)=10
17 T(7,8)=12:T(7,9)=16:T(7,10)=13:T(7,11)=12:T(7,12)=10:T(7,13)=16:T(7,14)=10:T(7,15)=14
18 T(8,9)=14:T(8,10)=11:T(8,11)=10:T(8,12)=8:T(8,13)=14:T(8,14)=8:T(8,15)=12
19 T(9,10)=15:T(9,11)=14:T(9,12)=12:T(9,13)=18:T(9,14)=12:T(9,15)=16
20 T(10,11)=11:T(10,12)=9:T(10,13)=15:T(10,14)=9:T(10,15)=13
21 T(11,12)=8:T(11,13)=14:T(11,14)=8:T(11,15)=12:T(12,13)=12:T(12,14)=6:T(12,15)=10:T(13,14)=12:T(13,15)=16:T(14,15)=10
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 15
88 A(I)=FIX(RND*699)
89 NEXT I
126 IMAR=10+FIX(RND*25000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 15
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*15):IJM=1+FIX(RND*15):IJN=1+FIX(RND*15)
233 IF RND<.7 THEN X(IJL)=FIX(RND*699) ELSE IF RND<.05 THEN X(IJL)=A(IJL)-1 ELSE GOTO 244
235 GOTO 351
244 X(IJM)=A(IJN):X(IJN)=A(IJM)
351 FOR K=1 TO 14
361 FOR J=K+1 TO 15
364 IF ABS(X(K)-X(J))366 NEXT J
399 NEXT K
1590 SUMTZ=0
1591 FOR K=1 TO 14
1594 FOR J=K+1 TO 15
1596 SUMTZ=SUMTZ+TZ(K,J)
1597 NEXT J
1598 NEXT K
1623 PR1=-10*ABS(X(1)-X(2))-0*ABS(X(1)-X(3))-5*ABS(X(1)-X(4))-1*ABS(X(1)-X(5))-0*ABS(X(1)-X(6))-1*ABS(X(1)-X(7))-2*ABS(X(1)-X(8))-2*ABS(X(1)-X(9))-2*ABS(X(1)-X(10))-2*ABS(X(1)-X(11))-0*ABS(X(1)-X(12))-4*ABS(X(1)-X(13))-0*ABS(X(1)-X(14))-0*ABS(X(1)-X(15))
1624 PR2=-1*ABS(X(2)-X(3))-3*ABS(X(2)-X(4))-2*ABS(X(2)-X(5))-2*ABS(X(2)-X(6))-2*ABS(X(2)-X(7))-3*ABS(X(2)-X(8))-2*ABS(X(2)-X(9))-0*ABS(X(2)-X(10))-2*ABS(X(2)-X(11))-0*ABS(X(2)-X(12))-10*ABS(X(2)-X(13))-5*ABS(X(2)-X(14))-0*ABS(X(2)-X(15))
1625 PR3=-10*ABS(X(3)-X(4))-2*ABS(X(3)-X(5))-0*ABS(X(3)-X(6))-2*ABS(X(3)-X(7))-5*ABS(X(3)-X(8))-4*ABS(X(3)-X(9))-5*ABS(X(3)-X(10))-2*ABS(X(3)-X(11))-2*ABS(X(3)-X(12))-5*ABS(X(3)-X(13))-5*ABS(X(3)-X(14))-5*ABS(X(3)-X(15))
1626 PR4=-1*ABS(X(4)-X(5))-1*ABS(X(4)-X(6))-5*ABS(X(4)-X(7))-0*ABS(X(4)-X(8))-0*ABS(X(4)-X(9))-2*ABS(X(4)-X(10))-1*ABS(X(4)-X(11))-0*ABS(X(4)-X(12))-2*ABS(X(4)-X(13))-5*ABS(X(4)-X(14))-0*ABS(X(4)-X(15))
1627 PR5=-3*ABS(X(5)-X(6))-5*ABS(X(5)-X(7))-5*ABS(X(5)-X(8))-5*ABS(X(5)-X(9))-1*ABS(X(5)-X(10))-0*ABS(X(5)-X(11))-3*ABS(X(5)-X(12))-0*ABS(X(5)-X(13))-5*ABS(X(5)-X(14))-5*ABS(X(5)-X(15))
1628 PR6=-2*ABS(X(6)-X(7))-2*ABS(X(6)-X(8))-1*ABS(X(6)-X(9))-5*ABS(X(6)-X(10))-0*ABS(X(6)-X(11))-0*ABS(X(6)-X(12))-2*ABS(X(6)-X(13))-5*ABS(X(6)-X(14))-10*ABS(X(6)-X(15))
1629 PR7=-6*ABS(X(7)-X(8))-0*ABS(X(7)-X(9))-1*ABS(X(7)-X(10))-5*ABS(X(7)-X(11))-5*ABS(X(7)-X(12))-5*ABS(X(7)-X(13))-1*ABS(X(7)-X(14))-0*ABS(X(7)-X(15))
1630 PR8=-5*ABS(X(8)-X(9))-2*ABS(X(8)-X(10))-10*ABS(X(8)-X(11))-0*ABS(X(8)-X(12))-5*ABS(X(8)-X(13))-0*ABS(X(8)-X(14))-0*ABS(X(8)-X(15))
1631 PR9=-0*ABS(X(9)-X(10))-10*ABS(X(9)-X(11))-5*ABS(X(9)-X(12))-10*ABS(X(9)-X(13))-0*ABS(X(9)-X(14))-2*ABS(X(9)-X(15))
1632 PR10=-0*ABS(X(10)-X(11))-4*ABS(X(10)-X(12))-0*ABS(X(10)-X(13))-0*ABS(X(10)-X(14))-5*ABS(X(10)-X(15))
1633 PR11=-5*ABS(X(11)-X(12))-0*ABS(X(11)-X(13))-5*ABS(X(11)-X(14))-0*ABS(X(11)-X(15))
1636 PR12=-3*ABS(X(12)-X(13))-3*ABS(X(12)-X(14))-0*ABS(X(12)-X(15))-10*ABS(X(13)-X(14))-2*ABS(X(13)-X(15))-4*ABS(X(14)-X(15))
1650 P=PR1+PR2+PR3+PR4+PR5+PR6+PR7+PR8+PR9+PR10+PR11+PR12-SUMTZ
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 15
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-12700 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)
1917 PRINT M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW-BASIC 3.11 interpreter, and the output produced in the first nine hours of running is presented below. What immediately follows is a manual copy from the computer screen.

259 282 383 371 399
409 349 337 313 432
327 359 294 365 419
-12691 -31999

554 513 431 443 415
404 459 477 525 381
487 469 501 449 394
-12691 -319904

347 370 470 458 486
496 442 430 400 519
414 422 382 452 506
-12684 -31852

342 301 219 231 203
193 247 265 313 170
275 257 289 237 183
-12638 -31437

304 327 427 415 443
453 399 381 357 476
371 389 339 409 463
-12614 -31390

453 392 330 342 314
304 364 400 424 281
410 354 380 348 294
-12610 -31301

12610 is optimal, Amaral (2006, p. 513). Interpreted in accordance with line 1912 through line 1917, the output above was produced in the first nine hours of running on a personal computer with an Intel 2.66 GHz. chip and the Microsoft interpreter.

References

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

Simmons, D. M., 1969. One-dimensioanl space allocation: An ordering algorithm. Operations Research 17, 812-826.

ERRATA

Jsun Yui Wong

Line 377 and line 388 of the last post of September 17 of the present blog should read as follows:

377 IF ABHV(K,J) less than T(K,J,4) THEN TZ(K,J)=999999! ELSE TZ(K,J)=0
388 NEXT J

The "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 areas for department 1 through department 4 are 60,
42, 18, and 24, respectively; these are the areas of departments L, M, N, and P of Armour and Buffa (1963, p. 301). Following Drezner (1980), this paper uses circular shapes for the departments; the radii are then 4.3701, 3.6563, 2.3936, and 2.7639, respectively. The interdepartmental flows are shown in line 1625 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,4)=4.3701+3.6563
8 T(1,3,4)=4.3701+2.3936
9 T(1,4,4)=4.3701+2.7639
19 T(2,3,4)=3.6563+2.3936
20 T(2,4,4)=3.6563+2.7639
33 T(3,4,4)=2.3936+2.7639
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 8
88 A(I)=(RND*160)
89 NEXT I
126 IMAR=10+FIX(RND*25000)
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)
235 X(IJL)=(RND*160)
370 FOR K=1 TO 3
371 FOR J=K+1 TO 4
373 ABHV(K,J)=((X(K)-X(J))^2+(X(K+4)-X(J+4))^2)^.5
377 IF ABHV(K,J)388 NEXT J
399 NEXT K
1580 SUMTZ=0
1591 FOR K=1 TO 3
1594 FOR J=K+1 TO 4
1595 SUMTZ=SUMTZ+TZ(K,J)
1597 NEXT J
1598 NEXT K
1625 PR1=-111*ABHV(1,2)-222*ABHV(1,3)-110*ABHV(1,4)-88*ABHV(2,3)-260*ABBV(2,4)-250*ABHV(3,4)
1650 P=PR1-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>-5100 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 candidate solutions produced within the first four hours of running are presented below. What immediately follows is a manual copy from the computer screen.

73.74793 80.37548 80.34096 77.69028 136.5546
132.0092 138.0749 142.5063 -5004.126 -31755

75.62321 67.58608 71.05748 75.74828 68.22386
68.18848 63.22806 61.0816 -5002.802 -30078

Interpreted in accordance with line 1912 and line 1914, the best candidate solutions produced within the first four hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter are presented above.

References

G. C. Armour and E. S. Buffa, "A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities," Management Science 9, 294-309 (1963).

Z. Drezner, "DISCON: A New Method for the Layout Problem," Operations Research 28, 1375-1384 (1980).

ERRATA

Jsun Yui Wong

Line 377, line 378, line 379, and line 388 of the last post of September 16 and of the September 17 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),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).