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 <.
Tuesday, September 22, 2009
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))
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.
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))
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.
Saturday, September 19, 2009
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 <.
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))
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.
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.
Friday, September 18, 2009
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 <.
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 <.
Thursday, September 17, 2009
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)
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).
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)
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 <.
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 <.
Subscribe to:
Posts (Atom)