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