Jsun Yui Wong
The computer program listed below seeks to solve Problem P15 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
1 REM
3 DEFINT I,J,K
4 DIM X(166),A(166),L(166),K(166),P(166),B(166),S(166)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 15
113 A(K)=FIX(RND*699)
115 NEXT K
126 IMAR=10+FIX(RND*20000)
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 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(1)-X(9))
509 B(9)=ABS(X(1)-X(10))
510 B(10)=ABS(X(1)-X(11))
511 B(11)=ABS(X(1)-X(12))
512 B(12)=ABS(X(1)-X(13))
513 B(13)=ABS(X(1)-X(14))
514 B(14)=ABS(X(1)-X(15))
515 B(15)=ABS(X(2)-X(3))
516 B(16)=ABS(X(2)-X(4))
517 B(17)=ABS(X(2)-X(5))
518 B(18)=ABS(X(2)-X(6))
519 B(19)=ABS(X(2)-X(7))
520 B(20)=ABS(X(2)-X(8))
521 B(21)=ABS(X(2)-X(9))
522 B(22)=ABS(X(2)-X(10))
523 B(23)=ABS(X(2)-X(11))
524 B(24)=ABS(X(2)-X(12))
525 B(25)=ABS(X(2)-X(13))
526 B(26)=ABS(X(2)-X(14))
527 B(27)=ABS(X(2)-X(15))
528 B(28)=ABS(X(3)-X(4))
529 B(29)=ABS(X(3)-X(5))
530 B(30)=ABS(X(3)-X(6))
531 B(31)=ABS(X(3)-X(7))
532 B(32)=ABS(X(3)-X(8))
533 B(33)=ABS(X(3)-X(9))
534 B(34)=ABS(X(3)-X(10))
535 B(35)=ABS(X(3)-X(11))
536 B(36)=ABS(X(3)-X(12))
537 B(37)=ABS(X(3)-X(13))
538 B(38)=ABS(X(3)-X(14))
539 B(39)=ABS(X(3)-X(15))
540 B(40)=ABS(X(4)-X(5))
541 B(41)=ABS(X(4)-X(6))
542 B(42)=ABS(X(4)-X(7))
543 B(43)=ABS(X(4)-X(8))
544 B(44)=ABS(X(4)-X(9))
545 B(45)=ABS(X(4)-X(10))
546 B(46)=ABS(X(4)-X(11))
547 B(47)=ABS(X(4)-X(12))
548 B(48)=ABS(X(4)-X(13))
549 B(49)=ABS(X(4)-X(14))
550 B(50)=ABS(X(4)-X(15))
551 B(51)=ABS(X(5)-X(6))
552 B(52)=ABS(X(5)-X(7))
553 B(53)=ABS(X(5)-X(8))
554 B(54)=ABS(X(5)-X(9))
555 B(55)=ABS(X(5)-X(10))
556 B(56)=ABS(X(5)-X(11))
557 B(57)=ABS(X(5)-X(12))
558 B(58)=ABS(X(5)-X(13))
559 B(59)=ABS(X(5)-X(14))
560 B(60)=ABS(X(5)-X(15))
561 B(61)=ABS(X(6)-X(7))
562 B(62)=ABS(X(6)-X(8))
563 B(63)=ABS(X(6)-X(9))
564 B(64)=ABS(X(6)-X(10))
565 B(65)=ABS(X(6)-X(11))
566 B(66)=ABS(X(6)-X(12))
567 B(67)=ABS(X(6)-X(13))
568 B(68)=ABS(X(6)-X(14))
569 B(69)=ABS(X(6)-X(15))
570 B(70)=ABS(X(7)-X(8))
571 B(71)=ABS(X(7)-X(9))
572 B(72)=ABS(X(7)-X(10))
573 B(73)=ABS(X(7)-X(11))
574 B(74)=ABS(X(7)-X(12))
575 B(75)=ABS(X(7)-X(13))
576 B(76)=ABS(X(7)-X(14))
577 B(77)=ABS(X(7)-X(15))
578 B(78)=ABS(X(8)-X(9))
579 B(79)=ABS(X(8)-X(10))
580 B(80)=ABS(X(8)-X(11))
581 B(81)=ABS(X(8)-X(12))
582 B(82)=ABS(X(8)-X(13))
583 B(83)=ABS(X(8)-X(14))
584 B(84)=ABS(X(8)-X(15))
585 B(85)=ABS(X(9)-X(10))
586 B(86)=ABS(X(9)-X(11))
587 B(87)=ABS(X(9)-X(12))
588 B(88)=ABS(X(9)-X(13))
589 B(89)=ABS(X(9)-X(14))
590 B(90)=ABS(X(9)-X(15))
591 B(91)=ABS(X(10)-X(11))
592 B(92)=ABS(X(10)-X(12))
593 B(93)=ABS(X(10)-X(13))
594 B(94)=ABS(X(10)-X(14))
595 B(95)=ABS(X(10)-X(15))
596 B(96)=ABS(X(11)-X(12))
597 B(97)=ABS(X(11)-X(13))
598 B(98)=ABS(X(11)-X(14))
599 B(99)=ABS(X(11)-X(15))
600 B(100)=ABS(X(12)-X(13))
601 B(101)=ABS(X(12)-X(14))
602 B(102)=ABS(X(12)-X(15))
603 B(103)=ABS(X(13)-X(14))
604 B(104)=ABS(X(13)-X(15))
605 B(105)=ABS(X(14)-X(15))
901 S(1)=B(1)-23
902 S(2)=B(2)-29
903 S(3)=B(3)-23
904 S(4)=B(4)-27
905 S(5)=B(5)-23
906 S(6)=B(6)-27
907 S(7)=B(7)-25
908 S(8)=B(8)-29
909 S(9)=B(9)-26
910 S(10)=B(10)-25
911 S(11)=B(11)-23
912 S(12)=B(12)-29
913 S(13)=B(13)-23
914 S(14)=B(14)-27
915 S(15)=B(15)-12
916 S(16)=B(16)-6
917 S(17)=B(17)-10
918 S(18)=B(18)-6
919 S(19)=B(19)-10
920 S(20)=B(20)-8
921 S(21)=B(21)-12
922 S(22)=B(22)-9
923 S(23)=B(23)-8
924 S(24)=B(24)-6
925 S(25)=B(25)-12
926 S(26)=B(26)-6
927 S(27)=B(27)-10
928 S(28)=B(28)-12
929 S(29)=B(29)-16
930 S(30)=B(30)-12
931 S(31)=B(31)-16
932 S(32)=B(32)-14
933 S(33)=B(33)-18
934 S(34)=B(34)-15
935 S(35)=B(35)-14
936 S(36)=B(36)-12
937 S(37)=B(37)-18
938 S(38)=B(38)-12
939 S(39)=B(39)-16
940 S(40)=B(40)-10
941 S(41)=B(41)-6
942 S(42)=B(42)-10
943 S(43)=B(43)-8
944 S(44)=B(44)-12
945 S(45)=B(45)-9
946 S(46)=B(46)-8
947 S(47)=B(47)-6
948 S(48)=B(48)-12
949 S(49)=B(49)-6
950 S(50)=B(50)-10
951 S(51)=B(51)-10
952 S(52)=B(52)-14
953 S(53)=B(53)-12
954 S(54)=B(54)-16
955 S(55)=B(55)-13
956 S(56)=B(56)-12
957 S(57)=B(57)-10
958 S(58)=B(58)-16
959 S(59)=B(59)-10
960 S(60)=B(60)-14
961 S(61)=B(61)-10
962 S(62)=B(62)-8
963 S(63)=B(63)-12
964 S(64)=B(64)-9
965 S(65)=B(65)-8
966 S(66)=B(66)-6
967 S(67)=B(67)-12
968 S(68)=B(68)-6
969 S(69)=B(69)-10
970 S(70)=B(70)-12
971 S(71)=B(71)-16
972 S(72)=B(72)-13
973 S(73)=B(73)-12
974 S(74)=B(74)-10
975 S(75)=B(75)-16
976 S(76)=B(76)-10
977 S(77)=B(77)-14
978 S(78)=B(78)-14
979 S(79)=B(79)-11
980 S(80)=B(80)-10
981 S(81)=B(81)-8
982 S(82)=B(82)-14
983 S(83)=B(83)-8
984 S(84)=B(84)-12
985 S(85)=B(85)-15
986 S(86)=B(86)-14
987 S(87)=B(87)-12
988 S(88)=B(88)-18
989 S(89)=B(89)-12
990 S(90)=B(90)-16
991 S(91)=B(91)-11
992 S(92)=B(92)-9
993 S(93)=B(93)-15
994 S(94)=B(94)-9
995 S(95)=B(95)-13
996 S(96)=B(96)-8
997 S(97)=B(97)-14
998 S(98)=B(98)-8
999 S(99)=B(99)-12
1000 S(100)=B(100)-12
1001 S(101)=B(101)-6
1002 S(102)=B(102)-10
1003 S(103)=B(103)-12
1004 S(104)=B(104)-16
1005 S(105)=B(105)-10
1107 FOR IJUL=1 TO 105
1111 IF S(IJUL)<0 THEN S(IJUL)=ABS(S(IJUL)) ELSE S(IJUL)=0
1115 NEXT IJUL
1380 PH=-10*B(1)-0*B(2)-5*B(3)-1*B(4)-0*B(5)-1*B(6)-2*B(7)-2*B(8)-2*B(9)
1381 PI=-2*B(10)-0*B(11)-4*B(12)-0*B(13)-0*B(14)-1*B(15)-3*B(16)-2*B(17)-2*B(18)
1384 PJ=-2*B(19)-3*B(20)-2*B(21)-0*B(22)-2*B(23)-0*B(24)-10*B(25)-5*B(26)-0*B(27)-10*B(28)
1385 PG=-2*B(29)-0*B(30)-2*B(31)-5*B(32)-4*B(33)-5*B(34)-2*B(35)-2*B(36)
1387 PF=-5*B(37)-5*B(38)-5*B(39)-1*B(40)-1*B(41)-5*B(42)-0*B(43)-0*B(44)-2*B(45)
1389 PE=-1*B(46)-0*B(47)-2*B(48)-5*B(49)-0*B(50)-3*B(51)-5*B(52)-5*B(53)-5*B(54)-1*B(55)
1391 PU=-0*B(56)-3*B(57)-0*B(58)-5*B(59)-5*B(60)-2*B(61)-2*B(62)-1*B(63)-5*B(64)-0*B(65)
1392 PV=-0*B(66)-2*B(67)-5*B(68)-10*B(69)-6*B(70)-0*B(71)-1*B(72)-5*B(73)-5*B(74)-5*B(75)
1393 PW=-1*B(76)-0*B(77)-5*B(78)-2*B(79)-10*B(80)-0*B(81)-5*B(82)-0*B(83)-0*B(84)-0*B(85)
1394 PX=-10*B(86)-5*B(87)-10*B(88)-0*B(89)-2*B(90)-0*B(91)-4*B(92)-0*B(93)-0*B(94)-5*B(95)
1395 PY=-5*B(96)-0*B(97)-5*B(98)-0*B(99)-3*B(100)-3*B(101)-0*B(102)-10*B(103)-2*B(104)-4*B(105)
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))
1490 PL3=-333333!*(S(37)+S(38)+S(39)+S(40)+S(41)+S(42)+S(43)+S(44)+S(45))
1491 PL4=-333333!*(S(46)+S(47)+S(48)+S(49)+S(50)+S(51)+S(52)+S(53)+S(54)+S(55))
1493 PL5=-333333!*(S(56)+S(57)+S(58)+S(59)+S(60)+S(61)+S(62)+S(63)+S(64)+S(65)+S(66)+S(67)+S(68)+S(69)+S(70)+S(71)+S(72)+S(73)+S(74))
1494 PL6=-333333!*(S(75)+S(76)+S(77)+S(78)+S(79)+S(80)+S(81)+S(82)+S(83)+S(84)+S(85)+S(86)+S(87)+S(88)+S(89)+S(90)+S(91)+S(92)+S(93))
1495 PL7=-333333!*(S(94)+S(95)+S(96)+S(97)+S(98)+S(99)+S(100)+S(101)+S(102)+S(103)+S(104)+S(105))
1587 PK=PH+PI+PJ+PG+PF+PE+PU+PV+PW+PX+PY
1588 P=PK+PL1+PL2+PL3+PL4+PL5+PL6+PL7
1599 PR=PK
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 15
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
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)
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 8 hours of running is presented below. (What immediately follows is a manual copy from the computer screen.)
278 301 401 389 417
427 367 355 331 450
345 377 313 383 437
-12610 -12610 -31135
Interpreted in accordance with line 1912, line 1913, line 1914, and line 1915, the output through JJJJ=-31135 was produced in the first 8 hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D 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-dimensional space allocation: An ordering algorithm. Operations Research 17, 812-826.
