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-FIX(RND*2) 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>-21500 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 ten hours of running is presented below. What immediately follows is a manual copy from the computer screen.
443 332 280 358 402
292 388 376 244 301
366 352 262 320 342
326 416 312 -21441 -31958
331 448 494 396 372
482 386 420 530 473
404 428 512 454 438
412 358 462 -21301 -31922
443 354 280 392 314
292 402 368 244 301
384 360 262 334 344
376 416 326 -21499 -31881
470 367 307 379 341
319 429 397 271 328
387 405 289 361 415
373 443 353 -21391 -31820
21301 is optimal, Amaral (2008, p. 1030). Interpreted in accordance with line 1912 through line 1915, the output through JJJJ=-31820 was produced within the first ten 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.
Heragu, S. S., A. Kusiak, 1991. Efficient models for the facility layout problem. European Journal of Operational Research 53, 1-13.
Simmons, D. M., 1969. One-dimensioanl space allocation: An ordering algorithm. Operations Research 17, 812-826.
