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.
