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