Jsun Yui Wong
The computer program listed below seeks to solve Problem S10 of Amaral (2006, p. 516), 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(48),A(48),L(48),K(48),P(48),B(48),S(48)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 10
113 A(K)=FIX(RND*199)
115 NEXT K
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 10
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*10)
233 IF RND<.99 THEN X(IJL)=FIX(RND*199) ELSE IF RND<.5 THEN X(IJL)=A(IJL)-1 ELSE X(IJK)=A(IJL)+1
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 REM
547 REM
548 REM
549 REM
901 S(1)=B(1)-9
902 S(2)=B(2)-15
903 S(3)=B(3)-10
904 S(4)=B(4)-8
905 S(5)=B(5)-12
906 S(6)=B(6)-14
907 S(7)=B(7)-15
908 S(8)=B(8)-12
909 S(9)=B(9)-7
910 S(10)=B(10)-5
911 S(11)=B(11)-9
912 S(12)=B(12)-11
913 S(13)=B(13)-12
914 S(14)=B(14)-13
915 S(15)=B(15)-11
916 S(16)=B(16)-15
917 S(17)=B(17)-17
918 S(18)=B(18)-18
919 S(19)=B(19)-6
920 S(20)=B(20)-10
921 S(21)=B(21)-12
922 S(22)=B(22)-13
923 S(23)=B(23)-8
924 S(24)=B(24)-10
925 S(25)=B(25)-11
926 S(26)=B(26)-14
927 S(27)=B(27)-15
928 S(28)=B(28)-17
929 S(29)=B(29)-12
930 S(30)=B(30)-9
931 S(31)=B(31)-15
932 S(32)=B(32)-10
933 S(33)=B(33)-8
934 S(34)=B(34)-12
935 S(35)=B(35)-14
936 S(36)=B(36)-15
937 S(37)=B(37)-13
938 S(38)=B(38)-10
939 S(39)=B(39)-16
940 S(40)=B(40)-11
941 S(41)=B(41)-9
942 S(42)=B(42)-13
943 S(43)=B(43)-15
944 S(44)=B(44)-16
945 S(45)=B(45)-13
946 REM
947 REM
948 REM
949 REM
1107 FOR IJUL=1 TO 45
1111 IF S(IJUL)<0 THEN S(IJUL)=ABS(S(IJUL)) ELSE S(IJUL)=0
1115 NEXT IJUL
1444 PF=-0*B(37)-7*B(38)-4*B(39)-5*B(40)-12*B(41)-5*B(42)-9*B(43)-7*B(44)-0*B(45)
1480 PH=-0*B(1)-9*B(2)-5*B(3)-1*B(4)-4*B(5)-5*B(6)-4*B(7)-4*B(8)-5*B(9)
1481 PI=-2*B(10)-7*B(11)-2*B(12)-9*B(13)-0*B(14)-7*B(15)-2*B(16)-5*B(17)-0*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=-7*B(29)-0*B(30)-9*B(31)-2*B(32)-2*B(33)-3*B(34)-2*B(35)-1*B(36)
1484 PJ=-7*B(19)-9*B(20)-0*B(21)-5*B(22)-0*B(23)-4*B(24)-7*B(25)-4*B(26)-9*B(27)-0*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
1488 P=PK+PL1+PL2+PL3
1499 PR=PK
1551 IF P<=M THEN 1670
1657 FOR KEW=1 TO 10
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-5625 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 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 1.5 hours of running is presented below. (What immediately follows is a manual copy from the computer screen.)
131 80 146 87 107
71 117 56 161 98
-5563 -5563 -26486
Interpreted in accordance with line 1912, line 1913, and line 1915, the output through
JJJJ=-26486 was produced in the first 1.5 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.
