Jsun Yui Wong
The computer program listed below seeks to solve Problem P15 of Amaral (2006, p. 517), which is an instance of the allocation/ordering problem of 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 29 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
343 320 206 218 228
194 248 266 290 171
276 258 308 238 184
-12676 -12676 -30879
142 204 266 254 282
292 232 196 172 301
186 242 216 248 314
-12667 -12667 -29661
420 397 297 309 281
271 325 343 367 248
353 335 385 315 261
-12614 -12614 -29334
241 300 364 352 380
390 330 318 270 413
308 340 288 346 400
-12610 -12610 -28901
Interpreted in accordance with line 1912, line 1913, line 1914, and line 1915, the output through JJJJ=-28901 was produced in the first 29 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.
