Jsun Yui Wong
The computer program listed below seeks to solve Problem S11 of Amaral (2006, p. 517), which is a problem from Simmons (1969). In order to have integer locations, the department lengths used in the following computer program have been made twice as long as the given department lengths.
0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(66),A(66),L(66),K(66),P(66),B(66),S(66)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 11
113 A(K)=FIX(RND*699)
115 NEXT K
126 IMAR=10+FIX(RND*12000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 11
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*11):IJM=1+FIX(RND*11):IJN=1+FIX(RND*11)
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 501
244 X(IJM)=A(IJN):X(IJN)=A(IJM)
501 B(1)=ABS(X(1)-X(2))
502 B(2)=ABS(X(1)-X(3))
503 B(3)=ABS(X(1)-X(4))
504 B(4)=ABS(X(1)-X(5))
505 B(5)=ABS(X(1)-X(6))
506 B(6)=ABS(X(1)-X(7))
507 B(7)=ABS(X(1)-X(8))
508 B(8)=ABS(X(2)-X(3))
509 B(9)=ABS(X(2)-X(4))
510 B(10)=ABS(X(2)-X(5))
511 B(11)=ABS(X(2)-X(6))
512 B(12)=ABS(X(2)-X(7))
513 B(13)=ABS(X(2)-X(8))
514 B(14)=ABS(X(3)-X(4))
515 B(15)=ABS(X(3)-X(5))
516 B(16)=ABS(X(3)-X(6))
517 B(17)=ABS(X(3)-X(7))
518 B(18)=ABS(X(3)-X(8))
519 B(19)=ABS(X(4)-X(5))
520 B(20)=ABS(X(4)-X(6))
521 B(21)=ABS(X(4)-X(7))
522 B(22)=ABS(X(4)-X(8))
523 B(23)=ABS(X(5)-X(6))
524 B(24)=ABS(X(5)-X(7))
525 B(25)=ABS(X(5)-X(8))
526 B(26)=ABS(X(6)-X(7))
527 B(27)=ABS(X(6)-X(8))
528 B(28)=ABS(X(7)-X(8))
529 B(29)=ABS(X(1)-X(9))
530 B(30)=ABS(X(2)-X(9))
531 B(31)=ABS(X(3)-X(9))
532 B(32)=ABS(X(4)-X(9))
533 B(33)=ABS(X(5)-X(9))
534 B(34)=ABS(X(6)-X(9))
535 B(35)=ABS(X(7)-X(9))
536 B(36)=ABS(X(8)-X(9))
537 B(37)=ABS(X(1)-X(10))
538 B(38)=ABS(X(2)-X(10))
539 B(39)=ABS(X(3)-X(10))
540 B(40)=ABS(X(4)-X(10))
541 B(41)=ABS(X(5)-X(10))
542 B(42)=ABS(X(6)-X(10))
543 B(43)=ABS(X(7)-X(10))
544 B(44)=ABS(X(8)-X(10))
545 B(45)=ABS(X(9)-X(10))
546 B(46)=ABS(X(1)-X(11))
547 B(47)=ABS(X(2)-X(11))
548 B(48)=ABS(X(3)-X(11))
549 B(49)=ABS(X(4)-X(11))
550 B(50)=ABS(X(5)-X(11))
551 B(51)=ABS(X(6)-X(11))
552 B(52)=ABS(X(7)-X(11))
553 B(53)=ABS(X(8)-X(11))
554 B(54)=ABS(X(9)-X(11))
555 B(55)=ABS(X(10)-X(11))
556 REM
557 REM
901 S(1)=B(1)-12
902 S(2)=B(2)-6
903 S(3)=B(3)-10
904 S(4)=B(4)-6
905 S(5)=B(5)-10
906 S(6)=B(6)-8
907 S(7)=B(7)-12
908 S(8)=B(8)-12
909 S(9)=B(9)-16
910 S(10)=B(10)-12
911 S(11)=B(11)-16
912 S(12)=B(12)-14
913 S(13)=B(13)-18
914 S(14)=B(14)-10
915 S(15)=B(15)-6
916 S(16)=B(16)-10
917 S(17)=B(17)-8
918 S(18)=B(18)-12
919 S(19)=B(19)-10
920 S(20)=B(20)-14
921 S(21)=B(21)-12
922 S(22)=B(22)-16
923 S(23)=B(23)-10
924 S(24)=B(24)-8
925 S(25)=B(25)-12
926 S(26)=B(26)-12
927 S(27)=B(27)-16
928 S(28)=B(28)-14
929 S(29)=B(29)-9
930 S(30)=B(30)-15
931 S(31)=B(31)-9
932 S(32)=B(32)-13
933 S(33)=B(33)-9
934 S(34)=B(34)-13
935 S(35)=B(35)-11
936 S(36)=B(36)-15
937 S(37)=B(37)-8
938 S(38)=B(38)-14
939 S(39)=B(39)-8
940 S(40)=B(40)-12
941 S(41)=B(41)-8
942 S(42)=B(42)-12
943 S(43)=B(43)-10
944 S(44)=B(44)-14
945 S(45)=B(45)-11
946 S(46)=B(46)-13
947 S(47)=B(47)-19
948 S(48)=B(48)-13
949 S(49)=B(49)-17
950 S(50)=B(50)-13
951 S(51)=B(51)-17
952 S(52)=B(52)-15
953 S(53)=B(53)-19
954 S(54)=B(54)-16
955 S(55)=B(55)-15
956 REM
1107 FOR IJUL=1 TO 55
1111 IF S(IJUL)<0 THEN S(IJUL)=ABS(S(IJUL)) ELSE S(IJUL)=0
1115 NEXT IJUL
1441 PL4=-333333!*(S(46)+S(47)+S(48)+S(49)+S(50)+S(51)+S(52)+S(53)+S(54)+S(55))
1443 PE=-3*B(46)-7*B(47)-0*B(48)-6*B(49)-2*B(50)-18*B(51)-7*B(52)-2*B(53)-0*B(54)-3*B(55)
1444 PF=-20*B(37)-6*B(38)-8*B(39)-14*B(40)-8*B(41)-7*B(42)-15*B(43)-7*B(44)-12*B(45)
1480 PH=-20*B(1)-2*B(2)-8*B(3)-0*B(4)-9*B(5)-5*B(6)-7*B(7)-8*B(8)-9*B(9)
1481 PI=-13*B(10)-17*B(11)-16*B(12)-1*B(13)-18*B(14)-0*B(15)-10*B(16)-4*B(17)-18*B(18)
1482 PL3=-333333!*(S(37)+S(38)+S(39)+S(40)+S(41)+S(42)+S(43)+S(44)+S(45))
1483 PG=-0*B(29)-8*B(30)-5*B(31)-2*B(32)-0*B(33)-2*B(34)-11*B(35)-1*B(36)
1484 PJ=-6*B(19)-16*B(20)-10*B(21)-4*B(22)-6*B(23)-0*B(24)-11*B(25)-6*B(26)-13*B(27)-1*B(28)
1485 PL1=-333333!*(S(1)+S(2)+S(3)+S(4)+S(5)+S(6)+S(7)+S(8)+S(9)+S(10)+S(11)+S(12)+S(13)+S(14)+S(15)+S(16)+S(17)+S(18)+S(19)+S(20)+S(21)+S(22)+S(23)+S(24)+S(25)+S(26)+S(27)+S(28))
1486 PL2=-333333!*(S(29)+S(30)+S(31)+S(32)+S(33)+S(34)+S(35)+S(36))
1487 PK=PH+PI+PJ+PG+PF+PE
1488 P=PK+PL1+PL2+PL3+PL4
1499 PR=PK
1551 IF P<=M THEN 1670
1657 FOR KEW=1 TO 11
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-13900 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)
1915 PRINT A(11),M,MM,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 3 hours of running is presented below. (What immediately follows is a manual copy from the computer screen.)
111 99 141 131 161
151 85 173 74 119
192 -13867 -13867 -31876
334 346 304 314 298
288 360 272 371 326
253 -13887 -13887 -31589
319 307 349 339 369
359 293 381 282 327
400 -13867 -13867 -31231
568 580 538 548 518
528 594 506 605 560
487 -31867 -31867 -31007
Interpreted in accordance with line 1912, line 1913, and line 1915, the output through
JJJJ=-31007 was produced in the first 3 hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Amaral, 2006 A.R.S. Amaral, On the exact solution of a facility layout problem, European Journal of Operational Research 173 (2006), pp. 508-518.
Simmons, 1969 D.M. Simmons, One-dimensional space allocation: An ordering algorithm, Operations Research 17 (1969), pp. 812-826.
