An Integer Programming Computer Program Applied to a Widely-Known Assignment Problem

Jsun Yui Wong
The problem considered here is the 12-location problem in Hillier [1] and in Nugent, Vollmann, and Ruml [2]. Line 561 through line 626 of the computer program below are slightly different from the mathematical formulation on page 6 of Heragu and Kusiak [3] and on page 140 of Heragu [4]. Line 1321 through line 1328 below use the interdepartmental flows presented in Hillier [1, p. 33] and in Nugent, Vollmann, and Ruml [2, p. 168].
The following computer program benefits from the computer programs of the present blog and the computer program on pages 229-232 of Conley [5].
2 DEFINT I,J,K
5 DIM B(99),N(99),A(99),H(99),L(99),U(99),X(1111),D(111),P(222)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
43 FOR IOC=1 TO 24
45 B(IOC)=0
47 NEXT IOC
51 FOR IOCTT=1 TO 12
53 N(IOCTT)=3
57 NEXT IOCTT
58 FOR IOCTT=13 TO 24
59 N(IOCTT)=2
60 NEXT IOCTT
61 FOR KLQ=1 TO 24
62 A(KLQ)=B(KLQ)+RND*(N(KLQ)-B(KLQ))
63 NEXT KLQ
71 FOR KLR=1 TO 24
72 H(KLR)=3
73 NEXT KLR
88 FOR JJJ=1 TO 1000 STEP 10
90 FOR INEW=1 TO 1
94 FOR J=INEW*2 TO 0 STEP -1
102 FOR JJ=0 TO 24
128 FOR I=1 TO 3
129 FOR KKQQ=1 TO 24
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
132 FOR K=1 TO 24
133 IF RND<=.5 THEN 298 ELSE 230
134 REM
137 REM
230 IF A(K)-(N(K)-B(K))/H(K)^J250 L(K)=B(K)
255 GOTO 265
260 L(K)=A(K)-(N(K)-B(K))/H(K)^J
265 IF A(K)+(N(K)-B(K))/H(K)^J>N(K) THEN 266 ELSE 268
266 U(K)=N(K)-L(K)
267 GOTO 272
268 U(K)=A(K)+(N(K)-B(K))/H(K)^J-L(K)
272 GOTO 300
298 X(K)=A(K)+2*RND*(2*RND-1)*(1/(1+RND*JJJ))*.05*A(K)
299 GOTO 302
300 X(K)=(L(K)+2*RND*RND*U(K))
302 NEXT K
304 X(JJ)=A(JJ)
306 KLPS=FIX(1+RND*72)
307 FOR KLA1=1 TO KLPS
308 KLA2=FIX(1+24*RND)
309 X(KLA2)=A(KLA2)
310 NEXT KLA1
343 IF RND>.1 GOTO 361
352 IF RND<.5 THEN 353 ELSE 355
353 X(JJ)=B(JJ)
354 GOTO 361
355 X(JJ)=N(JJ)
361 FOR I222=1 TO 24
364 X(I222)=FIX(X(I222))
368 NEXT I222
461 IF RND>.1 GOTO 531
465 IF RND<1/2 THEN 471 ELSE 491
471 IOCT1=1+FIX(RND*12)
474 IOCT2=1+FIX(RND*12)
477 X(IOCT1)=A(IOCT2)
480 X(IOCT2)=A(IOCT1)
481 GOTO 531
491 IOCT6=13+FIX(RND*12)
494 IOCT7=13+FIX(RND*12)
497 X(IOCT6)=A(IOCT7)
500 X(IOCT7)=A(IOCT6)
502 GOTO 531
511 IOCT8=25+FIX(RND*12)
514 IOCT9=25+FIX(RND*12)
517 X(IOCT8)=A(IOCT9)
520 X(IOCT9)=A(IOCT8)
522 GOTO 531
531 FOR IOCX=1 TO 12
533 IF X(IOCX)>3 THEN X(IOCX)=3
535 NEXT IOCX
537 FOR IOCXX=13 TO 24
538 IF X(IOCXX)>2 THEN X(IOCXX)=2
539 NEXT IOCXX
541 FOR IOCY=1 TO 24
543 IF X(IOCY)<0 THEN X(IOCY)=0
545 NEXT IOCY
561 P(11)=ABS(X(1)-X(2))+ABS(X(13)-X(14))
562 P(12)=ABS(X(1)-X(3))+ABS(X(13)-X(15))
563 P(13)=ABS(X(1)-X(4))+ABS(X(13)-X(16))
564 P(14)=ABS(X(1)-X(5))+ABS(X(13)-X(17))
565 P(15)=ABS(X(1)-X(6))+ABS(X(13)-X(18))
566 P(16)=ABS(X(1)-X(7))+ABS(X(13)-X(19))
567 P(17)=ABS(X(1)-X(8))+ABS(X(13)-X(20))
568 P(18)=ABS(X(1)-X(9))+ABS(X(13)-X(21))
569 P(19)=ABS(X(1)-X(10))+ABS(X(13)-X(22))
570 P(20)=ABS(X(1)-X(11))+ABS(X(13)-X(23))
571 P(21)=ABS(X(1)-X(12))+ABS(X(13)-X(24))
572 P(22)=ABS(X(2)-X(3))+ABS(X(14)-X(15))
573 P(23)=ABS(X(2)-X(4))+ABS(X(14)-X(16))
574 P(24)=ABS(X(2)-X(5))+ABS(X(14)-X(17))
575 P(25)=ABS(X(2)-X(6))+ABS(X(14)-X(18))
576 P(26)=ABS(X(2)-X(7))+ABS(X(14)-X(19))
577 P(27)=ABS(X(2)-X(8))+ABS(X(14)-X(20))
578 P(28)=ABS(X(2)-X(9))+ABS(X(14)-X(21))
579 P(29)=ABS(X(2)-X(10))+ABS(X(14)-X(22))
580 P(30)=ABS(X(2)-X(11))+ABS(X(14)-X(23))
581 P(31)=ABS(X(2)-X(12))+ABS(X(14)-X(24))
582 P(32)=ABS(X(3)-X(4))+ABS(X(15)-X(16))
583 P(33)=ABS(X(3)-X(5))+ABS(X(15)-X(17))
584 P(34)=ABS(X(3)-X(6))+ABS(X(15)-X(18))
585 P(35)=ABS(X(3)-X(7))+ABS(X(15)-X(19))
586 P(36)=ABS(X(3)-X(8))+ABS(X(15)-X(20))
587 P(37)=ABS(X(3)-X(9))+ABS(X(15)-X(21))
588 P(38)=ABS(X(3)-X(10))+ABS(X(15)-X(22))
589 P(39)=ABS(X(3)-X(11))+ABS(X(15)-X(23))
590 P(40)=ABS(X(3)-X(12))+ABS(X(15)-X(24))
591 P(41)=ABS(X(4)-X(5))+ABS(X(16)-X(17))
592 P(42)=ABS(X(4)-X(6))+ABS(X(16)-X(18))
593 P(43)=ABS(X(4)-X(7))+ABS(X(16)-X(19))
594 P(44)=ABS(X(4)-X(8))+ABS(X(16)-X(20))
595 P(45)=ABS(X(4)-X(9))+ABS(X(16)-X(21))
596 P(46)=ABS(X(4)-X(10))+ABS(X(16)-X(22))
597 P(47)=ABS(X(4)-X(11))+ABS(X(16)-X(23))
598 P(48)=ABS(X(4)-X(12))+ABS(X(16)-X(24))
599 P(49)=ABS(X(5)-X(6))+ABS(X(17)-X(18))
600 P(50)=ABS(X(5)-X(7))+ABS(X(17)-X(19))
601 P(51)=ABS(X(5)-X(8))+ABS(X(17)-X(20))
602 P(52)=ABS(X(5)-X(9))+ABS(X(17)-X(21))
603 P(53)=ABS(X(5)-X(10))+ABS(X(17)-X(22))
604 P(54)=ABS(X(5)-X(11))+ABS(X(17)-X(23))
605 P(55)=ABS(X(5)-X(12))+ABS(X(17)-X(24))
606 P(56)=ABS(X(6)-X(7))+ABS(X(18)-X(19))
607 P(57)=ABS(X(6)-X(8))+ABS(X(18)-X(20))
608 P(58)=ABS(X(6)-X(9))+ABS(X(18)-X(21))
609 P(59)=ABS(X(6)-X(10))+ABS(X(18)-X(22))
610 P(60)=ABS(X(6)-X(11))+ABS(X(18)-X(23))
611 P(61)=ABS(X(6)-X(12))+ABS(X(18)-X(24))
612 P(62)=ABS(X(7)-X(8))+ABS(X(19)-X(20))
613 P(63)=ABS(X(7)-X(9))+ABS(X(19)-X(21))
614 P(64)=ABS(X(7)-X(10))+ABS(X(19)-X(22))
615 P(65)=ABS(X(7)-X(11))+ABS(X(19)-X(23))
616 P(66)=ABS(X(7)-X(12))+ABS(X(19)-X(24))
617 P(67)=ABS(X(8)-X(9))+ABS(X(20)-X(21))
618 P(68)=ABS(X(8)-X(10))+ABS(X(20)-X(22))
619 P(69)=ABS(X(8)-X(11))+ABS(X(20)-X(23))
620 P(70)=ABS(X(8)-X(12))+ABS(X(20)-X(24))
621 P(71)=ABS(X(9)-X(10))+ABS(X(21)-X(22))
622 P(72)=ABS(X(9)-X(11))+ABS(X(21)-X(23))
623 P(73)=ABS(X(9)-X(12))+ABS(X(21)-X(24))
624 P(74)=ABS(X(10)-X(11))+ABS(X(22)-X(23))
625 P(75)=ABS(X(10)-X(12))+ABS(X(22)-X(24))
626 P(76)=ABS(X(11)-X(12))+ABS(X(23)-X(24))
788 FOR INSI=11 TO 76
791 IF P(INSI)<.5 THEN P(INSI)=9999 ELSE P(INSI)=P(INSI)
795 NEXT INSI
1321 P11B=5*P(11)+2*P(12)+4*P(13)+1*P(14)+.01*P(15)+.01*P(16)+6*P(17)+2*P(18)+1*P(19)+1*P(20)+1*P(21)
1322 P12B=3*P(22)+.01*P(23)+2*P(24)+2*P(25)+2*P(26)+.01*P(27)+4*P(28)+5*P(29)+.01*P(30)+.01*P(31)
1323 P13B=.01*P(32)+.01*P(33)+.01*P(34)+.01*P(35)+5*P(36)+5*P(37)+2*P(38)+2*P(39)+2*P(40)
1324 P14B=5*P(41)+2*P(42)+2*P(43)+10*P(44)+.01*P(45)+.01*P(46)+5*P(47)+5*P(48)
1325 P15B=10*P(49)+.01*P(50)+.01*P(51)+.01*P(52)+5*P(53)+1*P(54)+1*P(55)
1326 P16B=5*P(56)+1*P(57)+1*P(58)+5*P(59)+4*P(60)+.01*P(61)
1327 P17B=10*P(62)+5*P(63)+2*P(64)+3*P(65)+3*P(66)+.01*P(67)+.01*P(68)+5*P(69)+.01*P(70)
1328 P18B=.01*P(71)+10*P(72)+10*P(73)+5*P(74)+.01*P(75)+2*P(76)
1443 P1=P11B+P12B+P13B+P14B+P15B+P16B+P17B+P18B
1448 P6=P1+0+0+0+0
1449 PS1=0
1450 P=-P6+PS1
1451 IF P<=M THEN 1670
1452 M=P
1453 PP1=P6
1454 FOR KLX=1 TO 24
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1457 GOTO 128
1670 NEXT I
1702 NEXT JJ
1706 NEXT J
1777 NEXT INEW
1888 NEXT JJJ
1890 IF M>-295 THEN 1916 ELSE 1999
1916 PRINT JJJJ,M,PP1
1917 PRINT A(1),A(2),A(3),A(4),A(5)
1918 PRINT A(6),A(7),A(8),A(9),A(10)
1920 PRINT A(11),A(12)
1922 PRINT A(13),A(14),A(15),A(16),A(17)
1924 PRINT A(18),A(19),A(20),A(21),A(22)
1926 PRINT A(23),A(24),JJJJ,M,PP1
1999 NEXT JJJJ
The .01s above are the 0s of the n=12 case, Nugent et al. [2, p. 168].
This BASIC computer program was run with the IBM basica/D interpreter, and its best candidate solutions through JJJJ=-30497 (in compressed form and to be interpreted in accordance with line 1916 through line 1926; copied manually from the computer monitor) are presented below.
-31908 -289.65 289.65
0 0 0 3 3
2 2 2 1 1
1 3
1 2 0 1 2
2 0 1 0 2
1 0 -31908 -289.65 289.65
-31625 -291.64 291.64
3 3 3 0 0
1 2 2 1 2
1 0
1 0 2 1 0
0 2 1 2 0
1 2 -31625 -291.64 291.64
-30901 -291.64 291.64
3 3 3 0 0
1 2 2 1 2
1 0
1 0 2 1 0
0 2 1 2 0
1 2 -30901 -291.64 291.64
-30896 -289.65 289.65
0 0 0 3 3
2 2 2 1 1
1 3
1 0 2 1 0
0 2 1 2 0
1 2 -30896 -289.65 289.65
-30497 -289.65 289.65
0 0 0 3 3
2 2 2 1 1
1 3
1 2 0 1 2
2 0 1 0 2
1 0 -30497 -289.65 289.65
The best candidate solutions shown above are at JJJJ=-31908, JJJJ=-30896, and JJJJ=-30497 with an objective function value of 289.65. (The last two digits, 6 and 5, should be disregarded because these are due to the artificial flows, the .01s.)
The output above was produced in 10 hours on a personal computer with an Intel 2.66 GHz. chip and the IBM interpreter, which is slower than the corresponding compiler.
If one makes changes to the computer program above, such as a change of changing line 128 above to 128 FOR I=1 TO 4, one may or may not obtain 289, which is optimal. That leads to a general remedy that in general, in order to increase the probability of getting an optimal solution, one preferably should run several computers simultaneously, each with a different line 128, for example; instead of line 128, another line can be chosen. This multicomputer approach can mitigate the possible danger of missed optimality and can produce a usable solution faster than just running one computer.
References
[1] F.S. Hillier, Quantitative tools for plant layout analysis, J. Indust. Eng. 14 (1963) 33-40.
[2] C.E. Nugent, T.E. Vollmann, J. Ruml, An experimental comparison of techniques for the assignment of facilities to locations, Operations Research 16 (1968) 150-173.
[3] S.S. Heragu, A. Kusiak, Efficient models for the facility layout problem, European Journal of Operational Research 53 (1991) 1-13.
[4] S.S. Heragu, Recent models and techniques for solving the layout problem, European Journal of Operational Research 57 (1992) 136-144.
[5] W.C. Conley, Optimization: A Simplified Approach, Petrocelli, Princeton, New Jersey, 1981.

An Integer Programming Computer Program Applied to a Three-Dimensional Layout Problem

Jsun Yui Wong
The problem considered here is essentially the 12-location problem in Hillier [1] and in Nugent, Vollmann, and Ruml [2] plus a change to more than 12 locations spread over three dimensions. The same interfacility flows [1, p. 33; 2, p. 168] are used here. So one knows the minimum objective function value to this newer problem is 289 [2, p. 159] or smaller.
Line 561 through line 626 of the computer program below are slightly different from the mathematical formulation on page 6 of Heragu and Kusiak [3] and on page 140 of Heragu [4]. Line 1321 through line 1328 below use the interdepartmental flows presented in Hillier [1, p. 33] and in Nugent, Vollmann, and Ruml [2, p. 168].
The following computer program benefits from the computer programs of the present blog and the computer program on pages 229-232 of Conley [5].
A computer program that is identical to the one listed below with the exception of line 128, 128 FOR I=1 TO 3 for the former, produced no computational results after six hours of running. Then the following computer program was inputted.
2 DEFINT I,J,K
5 DIM B(99),N(99),A(99),H(99),L(99),U(99),X(1111),D(111),P(222)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
43 FOR IOC=1 TO 36
45 B(IOC)=0
47 NEXT IOC
51 FOR IOCTT=1 TO 36
53 N(IOCTT)=2
57 NEXT IOCTT
61 FOR KLQ=1 TO 36
62 A(KLQ)=B(KLQ)+RND*(N(KLQ)-B(KLQ))
63 NEXT KLQ
71 FOR KLR=1 TO 36
72 H(KLR)=3
73 NEXT KLR
88 FOR JJJ=1 TO 1000 STEP 10
90 FOR INEW=1 TO 1
94 FOR J=INEW*2 TO 0 STEP -1
102 FOR JJ=0 TO 36
128 FOR I=1 TO 10
129 FOR KKQQ=1 TO 36
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
132 FOR K=1 TO 36
133 IF RND<=.5 THEN 298 ELSE 230
134 REM
137 REM
230 IF A(K)-(N(K)-B(K))/H(K)^J250 L(K)=B(K)
255 GOTO 265
260 L(K)=A(K)-(N(K)-B(K))/H(K)^J
265 IF A(K)+(N(K)-B(K))/H(K)^J>N(K) THEN 266 ELSE 268
266 U(K)=N(K)-L(K)
267 GOTO 272
268 U(K)=A(K)+(N(K)-B(K))/H(K)^J-L(K)
272 GOTO 300
298 X(K)=A(K)+2*RND*(2*RND-1)*(1/(1+RND*JJJ))*.05*A(K)
299 GOTO 302
300 X(K)=(L(K)+2*RND*RND*U(K))
302 NEXT K
304 X(JJ)=A(JJ)
306 KLPS=FIX(1+RND*108)
307 FOR KLA1=1 TO KLPS
308 KLA2=FIX(1+36*RND)
309 X(KLA2)=A(KLA2)
310 NEXT KLA1
343 IF RND>.1 GOTO 361
352 IF RND<.5 THEN 353 ELSE 355
353 X(JJ)=B(JJ)
354 GOTO 361
355 X(JJ)=N(JJ)
361 FOR I222=1 TO 36
364 X(I222)=FIX(X(I222))
368 NEXT I222
461 IF RND>.1 GOTO 531
465 IF RND<1/3 THEN 471 ELSE IF RND<1/2 THEN 491 ELSE 511
471 IOCT1=1+FIX(RND*12)
474 IOCT2=1+FIX(RND*12)
477 X(IOCT1)=A(IOCT2)
480 X(IOCT2)=A(IOCT1)
481 GOTO 531
491 IOCT6=13+FIX(RND*12)
494 IOCT7=13+FIX(RND*12)
497 X(IOCT6)=A(IOCT7)
500 X(IOCT7)=A(IOCT6)
502 GOTO 531
511 IOCT8=25+FIX(RND*12)
514 IOCT9=25+FIX(RND*12)
517 X(IOCT8)=A(IOCT9)
520 X(IOCT9)=A(IOCT8)
522 GOTO 531
531 FOR IOCX=1 TO 36
533 IF X(IOCX)>2 THEN X(IOCX)=1
535 NEXT IOCX
541 FOR IOCY=1 TO 36
543 IF X(IOCY)<0 THEN X(IOCY)=0
545 NEXT IOCY
561 P(11)=ABS(X(1)-X(2))+ABS(X(13)-X(14))+ABS(X(25)-X(26))
562 P(12)=ABS(X(1)-X(3))+ABS(X(13)-X(15))+ABS(X(25)-X(27))
563 P(13)=ABS(X(1)-X(4))+ABS(X(13)-X(16))+ABS(X(25)-X(28))
564 P(14)=ABS(X(1)-X(5))+ABS(X(13)-X(17))+ABS(X(25)-X(29))
565 P(15)=ABS(X(1)-X(6))+ABS(X(13)-X(18))+ABS(X(25)-X(30))
566 P(16)=ABS(X(1)-X(7))+ABS(X(13)-X(19))+ABS(X(25)-X(31))
567 P(17)=ABS(X(1)-X(8))+ABS(X(13)-X(20))+ABS(X(25)-X(32))
568 P(18)=ABS(X(1)-X(9))+ABS(X(13)-X(21))+ABS(X(25)-X(33))
569 P(19)=ABS(X(1)-X(10))+ABS(X(13)-X(22))+ABS(X(25)-X(34))
570 P(20)=ABS(X(1)-X(11))+ABS(X(13)-X(23))+ABS(X(25)-X(35))
571 P(21)=ABS(X(1)-X(12))+ABS(X(13)-X(24))+ABS(X(25)-X(36))
572 P(22)=ABS(X(2)-X(3))+ABS(X(14)-X(15))+ABS(X(26)-X(27))
573 P(23)=ABS(X(2)-X(4))+ABS(X(14)-X(16))+ABS(X(26)-X(28))
574 P(24)=ABS(X(2)-X(5))+ABS(X(14)-X(17))+ABS(X(26)-X(29))
575 P(25)=ABS(X(2)-X(6))+ABS(X(14)-X(18))+ABS(X(26)-X(30))
576 P(26)=ABS(X(2)-X(7))+ABS(X(14)-X(19))+ABS(X(26)-X(31))
577 P(27)=ABS(X(2)-X(8))+ABS(X(14)-X(20))+ABS(X(26)-X(32))
578 P(28)=ABS(X(2)-X(9))+ABS(X(14)-X(21))+ABS(X(26)-X(33))
579 P(29)=ABS(X(2)-X(10))+ABS(X(14)-X(22))+ABS(X(26)-X(34))
580 P(30)=ABS(X(2)-X(11))+ABS(X(14)-X(23))+ABS(X(26)-X(35))
581 P(31)=ABS(X(2)-X(12))+ABS(X(14)-X(24))+ABS(X(26)-X(36))
582 P(32)=ABS(X(3)-X(4))+ABS(X(15)-X(16))+ABS(X(27)-X(28))
583 P(33)=ABS(X(3)-X(5))+ABS(X(15)-X(17))+ABS(X(27)-X(29))
584 P(34)=ABS(X(3)-X(6))+ABS(X(15)-X(18))+ABS(X(27)-X(30))
585 P(35)=ABS(X(3)-X(7))+ABS(X(15)-X(19))+ABS(X(27)-X(31))
586 P(36)=ABS(X(3)-X(8))+ABS(X(15)-X(20))+ABS(X(27)-X(32))
587 P(37)=ABS(X(3)-X(9))+ABS(X(15)-X(21))+ABS(X(27)-X(33))
588 P(38)=ABS(X(3)-X(10))+ABS(X(15)-X(22))+ABS(X(27)-X(34))
589 P(39)=ABS(X(3)-X(11))+ABS(X(15)-X(23))+ABS(X(27)-X(35))
590 P(40)=ABS(X(3)-X(12))+ABS(X(15)-X(24))+ABS(X(27)-X(36))
591 P(41)=ABS(X(4)-X(5))+ABS(X(16)-X(17))+ABS(X(28)-X(29))
592 P(42)=ABS(X(4)-X(6))+ABS(X(16)-X(18))+ABS(X(28)-X(30))
593 P(43)=ABS(X(4)-X(7))+ABS(X(16)-X(19))+ABS(X(28)-X(31))
594 P(44)=ABS(X(4)-X(8))+ABS(X(16)-X(20))+ABS(X(28)-X(32))
595 P(45)=ABS(X(4)-X(9))+ABS(X(16)-X(21))+ABS(X(28)-X(33))
596 P(46)=ABS(X(4)-X(10))+ABS(X(16)-X(22))+ABS(X(28)-X(34))
597 P(47)=ABS(X(4)-X(11))+ABS(X(16)-X(23))+ABS(X(28)-X(35))
598 P(48)=ABS(X(4)-X(12))+ABS(X(16)-X(24))+ABS(X(28)-X(36))
599 P(49)=ABS(X(5)-X(6))+ABS(X(17)-X(18))+ABS(X(29)-X(30))
600 P(50)=ABS(X(5)-X(7))+ABS(X(17)-X(19))+ABS(X(29)-X(31))
601 P(51)=ABS(X(5)-X(8))+ABS(X(17)-X(20))+ABS(X(29)-X(32))
602 P(52)=ABS(X(5)-X(9))+ABS(X(17)-X(21))+ABS(X(29)-X(33))
603 P(53)=ABS(X(5)-X(10))+ABS(X(17)-X(22))+ABS(X(29)-X(34))
604 P(54)=ABS(X(5)-X(11))+ABS(X(17)-X(23))+ABS(X(29)-X(35))
605 P(55)=ABS(X(5)-X(12))+ABS(X(17)-X(24))+ABS(X(29)-X(36))
606 P(56)=ABS(X(6)-X(7))+ABS(X(18)-X(19))+ABS(X(30)-X(31))
607 P(57)=ABS(X(6)-X(8))+ABS(X(18)-X(20))+ABS(X(30)-X(32))
608 P(58)=ABS(X(6)-X(9))+ABS(X(18)-X(21))+ABS(X(30)-X(33))
609 P(59)=ABS(X(6)-X(10))+ABS(X(18)-X(22))+ABS(X(30)-X(34))
610 P(60)=ABS(X(6)-X(11))+ABS(X(18)-X(23))+ABS(X(30)-X(35))
611 P(61)=ABS(X(6)-X(12))+ABS(X(18)-X(24))+ABS(X(30)-X(36))
612 P(62)=ABS(X(7)-X(8))+ABS(X(19)-X(20))+ABS(X(31)-X(32))
613 P(63)=ABS(X(7)-X(9))+ABS(X(19)-X(21))+ABS(X(31)-X(33))
614 P(64)=ABS(X(7)-X(10))+ABS(X(19)-X(22))+ABS(X(31)-X(34))
615 P(65)=ABS(X(7)-X(11))+ABS(X(19)-X(23))+ABS(X(31)-X(35))
616 P(66)=ABS(X(7)-X(12))+ABS(X(19)-X(24))+ABS(X(31)-X(36))
617 P(67)=ABS(X(8)-X(9))+ABS(X(20)-X(21))+ABS(X(32)-X(33))
618 P(68)=ABS(X(8)-X(10))+ABS(X(20)-X(22))+ABS(X(32)-X(34))
619 P(69)=ABS(X(8)-X(11))+ABS(X(20)-X(23))+ABS(X(32)-X(35))
620 P(70)=ABS(X(8)-X(12))+ABS(X(20)-X(24))+ABS(X(32)-X(36))
621 P(71)=ABS(X(9)-X(10))+ABS(X(21)-X(22))+ABS(X(33)-X(34))
622 P(72)=ABS(X(9)-X(11))+ABS(X(21)-X(23))+ABS(X(33)-X(35))
623 P(73)=ABS(X(9)-X(12))+ABS(X(21)-X(24))+ABS(X(33)-X(36))
624 P(74)=ABS(X(10)-X(11))+ABS(X(22)-X(23))+ABS(X(34)-X(35))
625 P(75)=ABS(X(10)-X(12))+ABS(X(22)-X(24))+ABS(X(34)-X(36))
626 P(76)=ABS(X(11)-X(12))+ABS(X(23)-X(24))+ABS(X(35)-X(36))
788 FOR INSI=11 TO 76
791 IF P(INSI)<.5 THEN P(INSI)=9999 ELSE P(INSI)=P(INSI)
795 NEXT INSI
1321 P11B=5*P(11)+2*P(12)+4*P(13)+1*P(14)+.01*P(15)+.01*P(16)+6*P(17)+2*P(18)+1*P(19)+1*P(20)+1*P(21)
1322 P12B=3*P(22)+.01*P(23)+2*P(24)+2*P(25)+2*P(26)+.01*P(27)+4*P(28)+5*P(29)+.01*P(30)+.01*P(31)
1323 P13B=.01*P(32)+.01*P(33)+.01*P(34)+.01*P(35)+5*P(36)+5*P(37)+2*P(38)+2*P(39)+2*P(40)
1324 P14B=5*P(41)+2*P(42)+2*P(43)+10*P(44)+.01*P(45)+.01*P(46)+5*P(47)+5*P(48)
1325 P15B=10*P(49)+.01*P(50)+.01*P(51)+.01*P(52)+5*P(53)+1*P(54)+1*P(55)
1326 P16B=5*P(56)+1*P(57)+1*P(58)+5*P(59)+4*P(60)+.01*P(61)
1327 P17B=10*P(62)+5*P(63)+2*P(64)+3*P(65)+3*P(66)+.01*P(67)+.01*P(68)+5*P(69)+.01*P(70)
1328 P18B=.01*P(71)+10*P(72)+10*P(73)+5*P(74)+.01*P(75)+2*P(76)
1443 P1=P11B+P12B+P13B+P14B+P15B+P16B+P17B+P18B
1448 P6=P1+0+0+0+0
1449 PS1=0
1450 P=-P6+PS1
1451 IF P<=M THEN 1670
1452 M=P
1453 PP1=P6
1454 FOR KLX=1 TO 36
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1457 GOTO 128
1670 NEXT I
1702 NEXT JJ
1706 NEXT J
1777 NEXT INEW
1778 REM
1888 NEXT JJJ
1890 IF M>-265 THEN 1916 ELSE 1999
1916 PRINT JJJJ,M,PP1
1917 PRINT A(1),A(2),A(3),A(4),A(5)
1918 PRINT A(6),A(7),A(8),A(9),A(10)
1920 PRINT A(11),A(12)
1922 PRINT A(13),A(14),A(15),A(16),A(17)
1924 PRINT A(18),A(19),A(20),A(21),A(22)
1926 PRINT A(23),A(24)
1928 PRINT A(25),A(26),A(27),A(28),A(29)
1930 PRINT A(30),A(31),A(32),A(33),A(34)
1932 PRINT A(35),A(36),JJJJ,M,PP1
1999 NEXT JJJJ
(The .01s above are the 0s of the n=12 case, Nugent et al. [2, p. 168].)
This BASIC computer program was run with the IBM basica/D interpreter, and its output through JJJJ=-31868 (in compressed form and to be interpreted in accordance with line 1916 through line 1932; copied manually from the computer monitor) is presented below.
-31987 -262.58 262.58
2 0 1 2 0
0 1 2 1 0
1 2
0 0 0 1 1
1 0 0 1 0
1 1
1 1 1 0 1
0 0 0 1 0
0 1 -31987 -262.58 262.58
-31977 -262.58 262.58
2 0 1 2 0
0 1 2 1 0
1 2
0 0 0 1 0
1 1 1 0 1
1 0
0 0 0 1 1
1 0 0 1 0
1 1 -31977 -262.58 262.58
-31972 -264.56 264.56
1 1 1 1 1
0 0 1 0 0
0 0
1 0 2 1 0
0 2 2 1 0
1 2
1 1 1 0 0
0 0 0 1 1
0 1 -31972 -264.56 264.56
-31868 -262.58 262.58
2 0 1 2 0
0 1 2 1 0
1 2
1 1 1 0 1
0 0 0 1 0
0 1
1 1 1 0 0
0 1 1 0 1
0 0 -31868 -262.58 262.58
The best candidate solutions shown above are at JJJJ=-31987, JJJJ=-31977, and JJJJ=-31868 with an objective function value of 262.58. (The last two digits, 5 and 8, should be disregarded because these are due to the artificial flows, the .01s.)
The output above was produced in 6 hours on a personal computer with an Intel 2.66 GHz. chip and the IBM interpreter, which is slower than the corresponding compiler.
If one makes changes to the computer program above, such as a change of changing line 128 above to 128 FOR I=1 TO 11, one may or may not obtain 262, which may or may not be optimal. That leads to a general remedy that in general, in order to increase the probability of getting an optimal solution, one preferably should run several computers simultaneously, each with a different line 128, for example; instead of line 128, another line can be chosen. This multicomputer approach can mitigate the possible danger of missed optimality and can produce a usable solution faster than just running one computer.
References
[1] F.S. Hillier, Quantitative tools for plant layout analysis, J. Indust. Eng. 14 (1963) 33-40.
[2] C.E. Nugent, T.E. Vollmann, J. Ruml, An experimental comparison of techniques for the assignment of facilities to locations, Operations Research 16 (1968) 150-173.
[3] S.S. Heragu, A. Kusiak, Efficient models for the facility layout problem, European Journal of Operational Research 53 (1991) 1-13.
[4] S.S. Heragu, Recent models and techniques for solving the layout problem, European Journal of Operational Research 57 (1992) 136-144.
[5] W.C. Conley, Optimization: A Simplified Approach, Petrocelli, Princeton, New Jersey, 1981.

Scheduling Thirty Activities Competing for Eight Facilities

Jsun Yui Wong
This is an instance of the Carlson and Nemhauser problem of scheduling to minimize interaction cost [1]. Line 561 through line 995 of the computer program below are slightly different from the mathematical formulation on page 6 of Heragu and Kusiak [2] and on page 140 of Heragu [3]. The objective is to minimize the total interaction cost of assigning thirty courses to eight time periods, which are period 0 through 7. As the individual interaction costs the program uses the interdepartmental flows presented in Nugent, Vollmann, and Ruml [4, p. 170]; these flows are used in line 1238 through line 1268 below.
The following computer program benefits from the computer programs of the present blog and the computer program on pages 229-232 of Conley [5].
2 DEFINT I,J,K
5 DIM B(99),N(99),A(99),H(99),L(99),U(99),X(1111),D(111),P(522)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
45 FOR IOC=1 TO 30
46 B(IOC)=0
47 NEXT IOC
51 FOR IOCTT=1 TO 30
53 N(IOCTT)=7
57 NEXT IOCTT
61 FOR KLQ=1 TO 30
62 A(KLQ)=B(KLQ)+RND*(N(KLQ)-B(KLQ))
63 NEXT KLQ
71 FOR KLR=1 TO 30
72 H(KLR)=3
73 NEXT KLR
88 FOR JJJ=1 TO 1000 STEP 10
90 FOR INEW=1 TO 1
94 FOR J=INEW*2 TO 0 STEP -1
102 FOR JJ=0 TO 30
128 FOR I=1 TO 1
129 FOR KKQQ=1 TO 30
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
132 FOR K=1 TO 30
133 IF RND<=.5 THEN 298 ELSE 230
230 IF A(K)-(N(K)-B(K))/H(K)^J250 L(K)=B(K)
255 GOTO 265
260 L(K)=A(K)-(N(K)-B(K))/H(K)^J
265 IF A(K)+(N(K)-B(K))/H(K)^J>N(K) THEN 266 ELSE 268
266 U(K)=N(K)-L(K)
267 GOTO 272
268 U(K)=A(K)+(N(K)-B(K))/H(K)^J-L(K)
272 GOTO 300
298 X(K)=A(K)+2*RND*(2*RND-1)*(1/(1+RND*JJJ))*.05*A(K)
299 GOTO 302
300 X(K)=(L(K)+2*RND*RND*U(K))
302 NEXT K
304 X(JJ)=A(JJ)
306 KLPS=FIX(1+RND*90)
307 FOR KLA1=1 TO KLPS
308 KLA2=FIX(1+30*RND)
309 X(KLA2)=A(KLA2)
310 NEXT KLA1
343 IF RND>.1 GOTO 361
352 IF RND<.5 THEN 353 ELSE 355
353 X(JJ)=B(JJ)
354 GOTO 361
355 X(JJ)=N(JJ)
361 FOR I222=1 TO 30
364 X(I222)=FIX(X(I222))
368 NEXT I222
371 FOR I223=1 TO 30
374 IF X(I223)>7 THEN X(I223)=7
377 NEXT I223
381 FOR I224=1 TO 30
384 IF X(I224)<0 THEN X(I224)=0
388 NEXT I224
461 IF RND>.1 GOTO 561
471 IOCT1=1+FIX(RND*30)
474 IOCT2=1+FIX(RND*30)
477 X(IOCT1)=A(IOCT2)
480 X(IOCT2)=A(IOCT1)
561 P(11)=ABS(X(1)-X(2))
562 P(12)=ABS(X(1)-X(3))
563 P(13)=ABS(X(1)-X(4))
564 P(14)=ABS(X(1)-X(5))
565 P(15)=ABS(X(1)-X(6))
566 P(16)=ABS(X(1)-X(7))
567 P(17)=ABS(X(1)-X(8))
568 P(18)=ABS(X(1)-X(9))
569 P(19)=ABS(X(1)-X(10))
570 P(20)=ABS(X(1)-X(11))
571 P(21)=ABS(X(1)-X(12))
572 P(22)=ABS(X(1)-X(13))
573 P(23)=ABS(X(1)-X(14))
574 P(24)=ABS(X(1)-X(15))
575 P(25)=ABS(X(1)-X(16))
576 P(26)=ABS(X(1)-X(17))
577 P(27)=ABS(X(1)-X(18))
578 P(28)=ABS(X(1)-X(19))
579 P(29)=ABS(X(1)-X(20))
580 P(30)=ABS(X(1)-X(21))
581 P(31)=ABS(X(1)-X(22))
582 P(32)=ABS(X(1)-X(23))
583 P(33)=ABS(X(1)-X(24))
584 P(34)=ABS(X(1)-X(25))
585 P(35)=ABS(X(1)-X(26))
586 P(36)=ABS(X(1)-X(27))
587 P(37)=ABS(X(1)-X(28))
588 P(38)=ABS(X(1)-X(29))
589 P(39)=ABS(X(1)-X(30))
590 P(40)=ABS(X(2)-X(3))
591 P(41)=ABS(X(2)-X(4))
592 P(42)=ABS(X(2)-X(5))
593 P(43)=ABS(X(2)-X(6))
594 P(44)=ABS(X(2)-X(7))
595 P(45)=ABS(X(2)-X(8))
596 P(46)=ABS(X(2)-X(9))
597 P(47)=ABS(X(2)-X(10))
598 P(48)=ABS(X(2)-X(11))
599 P(49)=ABS(X(2)-X(12))
600 P(50)=ABS(X(2)-X(13))
601 P(51)=ABS(X(2)-X(14))
602 P(52)=ABS(X(2)-X(15))
603 P(53)=ABS(X(2)-X(16))
604 P(54)=ABS(X(2)-X(17))
605 P(55)=ABS(X(2)-X(18))
606 P(56)=ABS(X(2)-X(19))
607 P(57)=ABS(X(2)-X(20))
608 P(58)=ABS(X(2)-X(21))
609 P(59)=ABS(X(2)-X(22))
610 P(60)=ABS(X(2)-X(23))
611 P(61)=ABS(X(2)-X(24))
612 P(62)=ABS(X(2)-X(25))
613 P(63)=ABS(X(2)-X(26))
614 P(64)=ABS(X(2)-X(27))
615 P(65)=ABS(X(2)-X(28))
616 P(66)=ABS(X(2)-X(29))
617 P(67)=ABS(X(2)-X(30))
618 P(68)=ABS(X(3)-X(4))
619 P(69)=ABS(X(3)-X(5))
620 P(70)=ABS(X(3)-X(6))
621 P(71)=ABS(X(3)-X(7))
622 P(72)=ABS(X(3)-X(8))
623 P(73)=ABS(X(3)-X(9))
624 P(74)=ABS(X(3)-X(10))
625 P(75)=ABS(X(3)-X(11))
626 P(76)=ABS(X(3)-X(12))
627 P(77)=ABS(X(3)-X(13))
628 P(78)=ABS(X(3)-X(14))
629 P(79)=ABS(X(3)-X(15))
630 P(80)=ABS(X(3)-X(16))
631 P(81)=ABS(X(3)-X(17))
632 P(82)=ABS(X(3)-X(18))
633 P(83)=ABS(X(3)-X(19))
634 P(84)=ABS(X(3)-X(20))
635 P(85)=ABS(X(3)-X(21))
636 P(86)=ABS(X(3)-X(22))
637 P(87)=ABS(X(3)-X(23))
638 P(88)=ABS(X(3)-X(24))
639 P(89)=ABS(X(3)-X(25))
640 P(90)=ABS(X(3)-X(26))
641 P(91)=ABS(X(3)-X(27))
642 P(92)=ABS(X(3)-X(28))
643 P(93)=ABS(X(3)-X(29))
644 P(94)=ABS(X(3)-X(30))
645 P(95)=ABS(X(4)-X(5))
646 P(96)=ABS(X(4)-X(6))
647 P(97)=ABS(X(4)-X(7))
648 P(98)=ABS(X(4)-X(8))
649 P(99)=ABS(X(4)-X(9))
650 P(100)=ABS(X(4)-X(10))
651 P(101)=ABS(X(4)-X(11))
652 P(102)=ABS(X(4)-X(12))
653 P(103)=ABS(X(4)-X(13))
654 P(104)=ABS(X(4)-X(14))
655 P(105)=ABS(X(4)-X(15))
656 P(106)=ABS(X(4)-X(16))
657 P(107)=ABS(X(4)-X(17))
658 P(108)=ABS(X(4)-X(18))
659 P(109)=ABS(X(4)-X(19))
660 P(110)=ABS(X(4)-X(20))
661 P(111)=ABS(X(4)-X(21))
662 P(112)=ABS(X(4)-X(22))
663 P(113)=ABS(X(4)-X(23))
664 P(114)=ABS(X(4)-X(24))
665 P(115)=ABS(X(4)-X(25))
666 P(116)=ABS(X(4)-X(26))
667 P(117)=ABS(X(4)-X(27))
668 P(118)=ABS(X(4)-X(28))
669 P(119)=ABS(X(4)-X(29))
670 P(120)=ABS(X(4)-X(30))
671 P(121)=ABS(X(5)-X(6))
672 P(122)=ABS(X(5)-X(7))
673 P(123)=ABS(X(5)-X(8))
674 P(124)=ABS(X(5)-X(9))
675 P(125)=ABS(X(5)-X(10))
676 P(126)=ABS(X(5)-X(11))
677 P(127)=ABS(X(5)-X(12))
678 P(128)=ABS(X(5)-X(13))
679 P(129)=ABS(X(5)-X(14))
680 P(130)=ABS(X(5)-X(15))
681 P(131)=ABS(X(5)-X(16))
682 P(132)=ABS(X(5)-X(17))
683 P(133)=ABS(X(5)-X(18))
684 P(134)=ABS(X(5)-X(19))
685 P(135)=ABS(X(5)-X(20))
686 P(136)=ABS(X(5)-X(21))
687 P(137)=ABS(X(5)-X(22))
688 P(138)=ABS(X(5)-X(23))
689 P(139)=ABS(X(5)-X(24))
690 P(140)=ABS(X(5)-X(25))
691 P(141)=ABS(X(5)-X(26))
692 P(142)=ABS(X(5)-X(27))
693 P(143)=ABS(X(5)-X(28))
694 P(144)=ABS(X(5)-X(29))
695 P(145)=ABS(X(5)-X(30))
696 P(146)=ABS(X(6)-X(7))
697 P(147)=ABS(X(6)-X(8))
698 P(148)=ABS(X(6)-X(9))
699 P(149)=ABS(X(6)-X(10))
700 P(150)=ABS(X(6)-X(11))
701 P(151)=ABS(X(6)-X(12))
702 P(152)=ABS(X(6)-X(13))
703 P(153)=ABS(X(6)-X(14))
704 P(154)=ABS(X(6)-X(15))
705 P(155)=ABS(X(6)-X(16))
706 P(156)=ABS(X(6)-X(17))
707 P(157)=ABS(X(6)-X(18))
708 P(158)=ABS(X(6)-X(19))
709 P(159)=ABS(X(6)-X(20))
710 P(160)=ABS(X(6)-X(21))
711 P(161)=ABS(X(6)-X(22))
712 P(162)=ABS(X(6)-X(23))
713 P(163)=ABS(X(6)-X(24))
714 P(164)=ABS(X(6)-X(25))
715 P(165)=ABS(X(6)-X(26))
716 P(166)=ABS(X(6)-X(27))
717 P(167)=ABS(X(6)-X(28))
718 P(168)=ABS(X(6)-X(29))
719 P(169)=ABS(X(6)-X(30))
720 P(170)=ABS(X(7)-X(8))
721 P(171)=ABS(X(7)-X(9))
722 P(172)=ABS(X(7)-X(10))
723 P(173)=ABS(X(7)-X(11))
724 P(174)=ABS(X(7)-X(12))
725 P(175)=ABS(X(7)-X(13))
726 P(176)=ABS(X(7)-X(14))
727 P(177)=ABS(X(7)-X(15))
728 P(178)=ABS(X(7)-X(16))
729 P(179)=ABS(X(7)-X(17))
730 P(180)=ABS(X(7)-X(18))
731 P(181)=ABS(X(7)-X(19))
732 P(182)=ABS(X(7)-X(20))
733 P(183)=ABS(X(7)-X(21))
734 P(184)=ABS(X(7)-X(22))
735 P(185)=ABS(X(7)-X(23))
736 P(186)=ABS(X(7)-X(24))
737 P(187)=ABS(X(7)-X(25))
738 P(188)=ABS(X(7)-X(26))
739 P(189)=ABS(X(7)-X(27))
740 P(190)=ABS(X(7)-X(28))
741 P(191)=ABS(X(7)-X(29))
742 P(192)=ABS(X(7)-X(30))
743 P(193)=ABS(X(8)-X(9))
744 P(194)=ABS(X(8)-X(10))
745 P(195)=ABS(X(8)-X(11))
746 P(196)=ABS(X(8)-X(12))
747 P(197)=ABS(X(8)-X(13))
748 P(198)=ABS(X(8)-X(14))
749 P(199)=ABS(X(8)-X(15))
750 P(200)=ABS(X(8)-X(16))
751 P(201)=ABS(X(8)-X(17))
752 P(202)=ABS(X(8)-X(18))
753 P(203)=ABS(X(8)-X(19))
754 P(204)=ABS(X(8)-X(20))
755 P(205)=ABS(X(8)-X(21))
756 P(206)=ABS(X(8)-X(22))
757 P(207)=ABS(X(8)-X(23))
758 P(208)=ABS(X(8)-X(24))
759 P(209)=ABS(X(8)-X(25))
760 P(210)=ABS(X(8)-X(26))
761 P(211)=ABS(X(8)-X(27))
762 P(212)=ABS(X(8)-X(28))
763 P(213)=ABS(X(8)-X(29))
764 P(214)=ABS(X(8)-X(30))
765 P(215)=ABS(X(9)-X(10))
766 P(216)=ABS(X(9)-X(11))
767 P(217)=ABS(X(9)-X(12))
768 P(218)=ABS(X(9)-X(13))
769 P(219)=ABS(X(9)-X(14))
770 P(220)=ABS(X(9)-X(15))
771 P(221)=ABS(X(9)-X(16))
772 P(222)=ABS(X(9)-X(17))
773 P(223)=ABS(X(9)-X(18))
774 P(224)=ABS(X(9)-X(19))
775 P(225)=ABS(X(9)-X(20))
776 P(226)=ABS(X(9)-X(21))
777 P(227)=ABS(X(9)-X(22))
778 P(228)=ABS(X(9)-X(23))
779 P(229)=ABS(X(9)-X(24))
780 P(230)=ABS(X(9)-X(25))
781 P(231)=ABS(X(9)-X(26))
782 P(232)=ABS(X(9)-X(27))
783 P(233)=ABS(X(9)-X(28))
784 P(234)=ABS(X(9)-X(29))
785 P(235)=ABS(X(9)-X(30))
786 P(236)=ABS(X(10)-X(11))
787 P(237)=ABS(X(10)-X(12))
788 P(238)=ABS(X(10)-X(13))
789 P(239)=ABS(X(10)-X(14))
790 P(240)=ABS(X(10)-X(15))
791 P(241)=ABS(X(10)-X(16))
792 P(242)=ABS(X(10)-X(17))
793 P(243)=ABS(X(10)-X(18))
794 P(244)=ABS(X(10)-X(19))
795 P(245)=ABS(X(10)-X(20))
796 P(246)=ABS(X(10)-X(21))
797 P(247)=ABS(X(10)-X(22))
798 P(248)=ABS(X(10)-X(23))
799 P(249)=ABS(X(10)-X(24))
800 P(250)=ABS(X(10)-X(25))
801 P(251)=ABS(X(10)-X(26))
802 P(252)=ABS(X(10)-X(27))
803 P(253)=ABS(X(10)-X(28))
804 P(254)=ABS(X(10)-X(29))
805 P(255)=ABS(X(10)-X(30))
806 P(256)=ABS(X(11)-X(12))
807 P(257)=ABS(X(11)-X(13))
808 P(258)=ABS(X(11)-X(14))
809 P(259)=ABS(X(11)-X(15))
810 P(260)=ABS(X(11)-X(16))
811 P(261)=ABS(X(11)-X(17))
812 P(262)=ABS(X(11)-X(18))
813 P(263)=ABS(X(11)-X(19))
814 P(264)=ABS(X(11)-X(20))
815 P(265)=ABS(X(11)-X(21))
816 P(266)=ABS(X(11)-X(22))
817 P(267)=ABS(X(11)-X(23))
818 P(268)=ABS(X(11)-X(24))
819 P(269)=ABS(X(11)-X(25))
820 P(270)=ABS(X(11)-X(26))
821 P(271)=ABS(X(11)-X(27))
822 P(272)=ABS(X(11)-X(28))
823 P(273)=ABS(X(11)-X(29))
824 P(274)=ABS(X(11)-X(30))
825 P(275)=ABS(X(12)-X(13))
826 P(276)=ABS(X(12)-X(14))
827 P(277)=ABS(X(12)-X(15))
828 P(278)=ABS(X(12)-X(16))
829 P(279)=ABS(X(12)-X(17))
830 P(280)=ABS(X(12)-X(18))
831 P(281)=ABS(X(12)-X(19))
832 P(282)=ABS(X(12)-X(20))
833 P(283)=ABS(X(12)-X(21))
834 P(284)=ABS(X(12)-X(22))
835 P(285)=ABS(X(12)-X(23))
836 P(286)=ABS(X(12)-X(24))
837 P(287)=ABS(X(12)-X(25))
838 P(288)=ABS(X(12)-X(26))
839 P(289)=ABS(X(12)-X(27))
840 P(290)=ABS(X(12)-X(28))
841 P(291)=ABS(X(12)-X(29))
842 P(292)=ABS(X(12)-X(30))
843 P(293)=ABS(X(13)-X(14))
844 P(294)=ABS(X(13)-X(15))
845 P(295)=ABS(X(13)-X(16))
846 P(296)=ABS(X(13)-X(17))
847 P(297)=ABS(X(13)-X(18))
848 P(298)=ABS(X(13)-X(19))
849 P(299)=ABS(X(13)-X(20))
850 P(300)=ABS(X(13)-X(21))
851 P(301)=ABS(X(13)-X(22))
852 P(302)=ABS(X(13)-X(23))
853 P(303)=ABS(X(13)-X(24))
854 P(304)=ABS(X(13)-X(25))
855 P(305)=ABS(X(13)-X(26))
856 P(306)=ABS(X(13)-X(27))
857 P(307)=ABS(X(13)-X(28))
858 P(308)=ABS(X(13)-X(29))
859 P(309)=ABS(X(13)-X(30))
860 P(310)=ABS(X(14)-X(15))
861 P(311)=ABS(X(14)-X(16))
862 P(312)=ABS(X(14)-X(17))
863 P(313)=ABS(X(14)-X(18))
864 P(314)=ABS(X(14)-X(19))
865 P(315)=ABS(X(14)-X(20))
866 P(316)=ABS(X(14)-X(21))
867 P(317)=ABS(X(14)-X(22))
868 P(318)=ABS(X(14)-X(23))
869 P(319)=ABS(X(14)-X(24))
870 P(320)=ABS(X(14)-X(25))
871 P(321)=ABS(X(14)-X(26))
872 P(322)=ABS(X(14)-X(27))
873 P(323)=ABS(X(14)-X(28))
874 P(324)=ABS(X(14)-X(29))
875 P(325)=ABS(X(14)-X(30))
876 P(326)=ABS(X(15)-X(16))
877 P(327)=ABS(X(15)-X(17))
878 P(328)=ABS(X(15)-X(18))
879 P(329)=ABS(X(15)-X(19))
880 P(330)=ABS(X(15)-X(20))
881 P(331)=ABS(X(15)-X(21))
882 P(332)=ABS(X(15)-X(22))
883 P(333)=ABS(X(15)-X(23))
884 P(334)=ABS(X(15)-X(24))
885 P(335)=ABS(X(15)-X(25))
886 P(336)=ABS(X(15)-X(26))
887 P(337)=ABS(X(15)-X(27))
888 P(338)=ABS(X(15)-X(28))
889 P(339)=ABS(X(15)-X(29))
890 P(340)=ABS(X(15)-X(30))
891 P(341)=ABS(X(16)-X(17))
892 P(342)=ABS(X(16)-X(18))
893 P(343)=ABS(X(16)-X(19))
894 P(344)=ABS(X(16)-X(20))
895 P(345)=ABS(X(16)-X(21))
896 P(346)=ABS(X(16)-X(22))
897 P(347)=ABS(X(16)-X(23))
898 P(348)=ABS(X(16)-X(24))
899 P(349)=ABS(X(16)-X(25))
900 P(350)=ABS(X(16)-X(26))
901 P(351)=ABS(X(16)-X(27))
902 P(352)=ABS(X(16)-X(28))
903 P(353)=ABS(X(16)-X(29))
904 P(354)=ABS(X(16)-X(30))
905 P(355)=ABS(X(17)-X(18))
906 P(356)=ABS(X(17)-X(19))
907 P(357)=ABS(X(17)-X(20))
908 P(358)=ABS(X(17)-X(21))
909 P(359)=ABS(X(17)-X(22))
910 P(360)=ABS(X(17)-X(23))
911 P(361)=ABS(X(17)-X(24))
912 P(362)=ABS(X(17)-X(25))
913 P(363)=ABS(X(17)-X(26))
914 P(364)=ABS(X(17)-X(27))
915 P(365)=ABS(X(17)-X(28))
916 P(366)=ABS(X(17)-X(29))
917 P(367)=ABS(X(17)-X(30))
918 P(368)=ABS(X(18)-X(19))
919 P(369)=ABS(X(18)-X(20))
920 P(370)=ABS(X(18)-X(21))
921 P(371)=ABS(X(18)-X(22))
922 P(372)=ABS(X(18)-X(23))
923 P(373)=ABS(X(18)-X(24))
924 P(374)=ABS(X(18)-X(25))
925 P(375)=ABS(X(18)-X(26))
926 P(376)=ABS(X(18)-X(27))
927 P(377)=ABS(X(18)-X(28))
928 P(378)=ABS(X(18)-X(29))
929 P(379)=ABS(X(18)-X(30))
930 P(380)=ABS(X(19)-X(20))
931 P(381)=ABS(X(19)-X(21))
932 P(382)=ABS(X(19)-X(22))
933 P(383)=ABS(X(19)-X(23))
934 P(384)=ABS(X(19)-X(24))
935 P(385)=ABS(X(19)-X(25))
936 P(386)=ABS(X(19)-X(26))
937 P(387)=ABS(X(19)-X(27))
938 P(388)=ABS(X(19)-X(28))
939 P(389)=ABS(X(19)-X(29))
940 P(390)=ABS(X(19)-X(30))
941 P(391)=ABS(X(20)-X(21))
942 P(392)=ABS(X(20)-X(22))
943 P(393)=ABS(X(20)-X(23))
944 P(394)=ABS(X(20)-X(24))
945 P(395)=ABS(X(20)-X(25))
946 P(396)=ABS(X(20)-X(26))
947 P(397)=ABS(X(20)-X(27))
948 P(398)=ABS(X(20)-X(28))
949 P(399)=ABS(X(20)-X(29))
950 P(400)=ABS(X(20)-X(30))
951 P(401)=ABS(X(21)-X(22))
952 P(402)=ABS(X(21)-X(23))
953 P(403)=ABS(X(21)-X(24))
954 P(404)=ABS(X(21)-X(25))
955 P(405)=ABS(X(21)-X(26))
956 P(406)=ABS(X(21)-X(27))
957 P(407)=ABS(X(21)-X(28))
958 P(408)=ABS(X(21)-X(29))
959 P(409)=ABS(X(21)-X(30))
960 P(410)=ABS(X(22)-X(23))
961 P(411)=ABS(X(22)-X(24))
962 P(412)=ABS(X(22)-X(25))
963 P(413)=ABS(X(22)-X(26))
964 P(414)=ABS(X(22)-X(27))
965 P(415)=ABS(X(22)-X(28))
966 P(416)=ABS(X(22)-X(29))
967 P(417)=ABS(X(22)-X(30))
968 P(418)=ABS(X(23)-X(24))
969 P(419)=ABS(X(23)-X(25))
970 P(420)=ABS(X(23)-X(26))
971 P(421)=ABS(X(23)-X(27))
972 P(422)=ABS(X(23)-X(28))
973 P(423)=ABS(X(23)-X(29))
974 P(424)=ABS(X(23)-X(30))
975 P(425)=ABS(X(24)-X(25))
976 P(426)=ABS(X(24)-X(26))
977 P(427)=ABS(X(24)-X(27))
978 P(428)=ABS(X(24)-X(28))
979 P(429)=ABS(X(24)-X(29))
980 P(430)=ABS(X(24)-X(30))
981 P(431)=ABS(X(25)-X(26))
982 P(432)=ABS(X(25)-X(27))
983 P(433)=ABS(X(25)-X(28))
984 P(434)=ABS(X(25)-X(29))
985 P(435)=ABS(X(25)-X(30))
986 P(436)=ABS(X(26)-X(27))
987 P(437)=ABS(X(26)-X(28))
988 P(438)=ABS(X(26)-X(29))
989 P(439)=ABS(X(26)-X(30))
990 P(440)=ABS(X(27)-X(28))
991 P(441)=ABS(X(27)-X(29))
992 P(442)=ABS(X(27)-X(30))
993 P(443)=ABS(X(28)-X(29))
994 P(444)=ABS(X(28)-X(30))
995 P(445)=ABS(X(29)-X(30))
1088 FOR INSI=11 TO 445
1091 IF P(INSI)<.5 THEN P(INSI)=1 ELSE P(INSI)=0
1095 NEXT INSI
1238 P11B=3*P(11)+2*P(12)+0*P(13)+0*P(14)+2*P(15)+10*P(16)+5*P(17)+0*P(18)+5*P(19)+2*P(20)
1239 P12B=5*P(21)+0*P(22)+0*P(23)+2*P(24)
1240 P13B=0*P(25)+5*P(26)+6*P(27)+3*P(28)+0*P(29)+1*P(30)+10*P(31)+0*P(32)+10*P(33)+2*P(34)+1*P(35)+1*P(36)+1*P(37)+0*P(38)+1*P(39)
1241 P14B=4*P(40)+0*P(41)+10*P(42)+4*P(43)+0*P(44)+0*P(45)+2*P(46)+2*P(47)+1*P(48)+0*P(49)+5*P(50)+0*P(51)+0*P(52)+0*P(53)+0*P(54)
1242 P15B=2*P(55)+0*P(56)+1*P(57)+6*P(58)+1*P(59)+0*P(60)+1*P(61)+2*P(62)+2*P(63)+5*P(64)+1*P(65)+10*P(66)+5*P(67)
1243 P16B=3*P(68)+4*P(69)+0*P(70)+5*P(71)+5*P(72)+5*P(73)+1*P(74)+4*P(75)+1*P(76)+0*P(77)+4*P(78)+0*P(79)+4*P(80)+0*P(81)+6*P(82)
1244 P17B=3*P(83)+2*P(84)+5*P(85)+5*P(86)+2*P(87)+1*P(88)+0*P(89)+0*P(90)+3*P(91)+1*P(92)+0*P(93)+2*P(94)+0*P(95)+0*P(96)+0*P(97)
1245 P18B=2*P(98)+2*P(99)+0*P(100)+6*P(101)+0*P(102)+2*P(103)+5*P(104)+2*P(105)+5*P(106)+1*P(107)+1*P(108)+1*P(109)+1*P(110)+2*P(111)+2*P(112)
1246 P19B=4*P(113)+0*P(114)+2*P(115)+0*P(116)+2*P(117)+2*P(118)+5*P(119)+5*P(120)+5*P(121)+2*P(122)+0*P(123)+0*P(124)+0*P(125)+0*P(126)+2*P(127)
1247 P20B=0*P(128)+0*P(129)+0*P(130)+0*P(131)+2*P(132)+1*P(133)+0*P(134)+0*P(135)+2*P(136)+0*P(137)+5*P(138)+1*P(139)+0*P(140)+2*P(141)+1*P(142)
1248 P21B=0*P(143)+2*P(144)+1*P(145)+1*P(146)+2*P(147)+2*P(148)+1*P(149)+4*P(150)+10*P(151)+10*P(152)+2*P(153)+5*P(154)+5*P(155)+0*P(156)+5*P(157)
1249 P22B=0*P(158)+0*P(159)+0*P(160)+10*P(161)+0*P(162)+0*P(163)+0*P(164)+4*P(165)+0*P(166)+10*P(167)+1*P(168)+1*P(169)+10*P(170)+10*P(171)+5*P(172)
1250 P23B=10*P(173)+10*P(174)+6*P(175)+0*P(176)+0*P(177)+10*P(178)+2*P(179)+1*P(180)+10*P(181)+1*P(182)+5*P(183)+5*P(184)+2*P(185)+3*P(186)+5*P(187)
1251 P24B=0*P(188)+2*P(189)+0*P(190)+1*P(191)+3*P(192)+1*P(193)+3*P(194)+5*P(195)+0*P(196)+0*P(197)+0*P(198)+2*P(199)+4*P(200)+5*P(201)+2*P(202)
1252 P25B=10*P(203)+6*P(204)+0*P(205)+5*P(206)+5*P(207)+2*P(208)+5*P(209)+0*P(210)+5*P(211)+5*P(212)+0*P(213)+2*P(214)+10*P(215)+2*P(216)+1*P(217)
1253 P26B=5*P(218)+2*P(219)+0*P(220)+3*P(221)+0*P(222)+2*P(223)+0*P(224)+0*P(225)+4*P(226)+0*P(227)+5*P(228)+2*P(229)+0*P(230)+5*P(231)+2*P(232)
1254 P27B=2*P(233)+5*P(234)+2*P(235)+5*P(236)+5*P(237)+6*P(238)+0*P(239)+1*P(240)+5*P(241)+5*P(242)+0*P(243)+5*P(244)+2*P(245)+3*P(246)+5*P(247)
1255 P28B=0*P(248)+5*P(249)+2*P(250)+10*P(251)+10*P(252)+1*P(253)+5*P(254)+2*P(255)+0*P(256)+0*P(257)+1*P(258)+2*P(259)+1*P(260)+0*P(261)+2*P(262)
1256 P29B=0*P(263)+0*P(264)+0*P(265)+6*P(266)+6*P(267)+0*P(268)+4*P(269)+5*P(270)+3*P(271)+2*P(272)+2*P(273)+10*P(274)+5*P(275)+5*P(276)+2*P(277)
1257 P30B=0*P(278)+0*P(279)+0*P(280)+0*P(281)+2*P(282)+0*P(283)+4*P(284)+5*P(285)+10*P(286)+1*P(287)+0*P(288)+0*P(289)+0*P(290)+0*P(291)+1*P(292)
1258 P31B=2*P(293)+0*P(294)+4*P(295)+2*P(296)+2*P(297)+1*P(298)+0*P(299)+6*P(300)+2*P(301)+1*P(302)+5*P(303)+5*P(304)+0*P(305)+0*P(306)+1*P(307)
1259 P32B=5*P(308)+5*P(309)+2*P(310)+1*P(311)+0*P(312)+5*P(313)+3*P(314)+10*P(315)+0*P(316)+0*P(317)+4*P(318)+2*P(319)+0*P(320)+0*P(321)+4*P(322)
1260 P33B=2*P(323)+5*P(324)+5*P(325)+4*P(326)+5*P(327)+1*P(328)+0*P(329)+1*P(330)+0*P(331)+5*P(332)+0*P(333)+2*P(334)+0*P(335)+0*P(336)+5*P(337)
1261 P34B=1*P(338)+1*P(339)+0*P(340)+0*P(341)+3*P(342)+0*P(343)+2*P(344)+2*P(345)+0*P(346)+2*P(347)+0*P(348)+5*P(349)+0*P(350)+5*P(351)+2*P(352)
1262 P35B=5*P(353)+10*P(354)+2*P(355)+2*P(356)+0*P(357)+0*P(358)+0*P(359)+6*P(360)+5*P(361)+3*P(362)+5*P(363)+0*P(364)+0*P(365)+5*P(366)+1*P(367)
1263 P36B=5*P(368)+1*P(369)+2*P(370)+10*P(371)+10*P(372)+4*P(373)+0*P(374)+0*P(375)+5*P(376)+0*P(377)+0*P(378)+0*P(379)+0*P(380)+5*P(381)+5*P(382)
1264 P38B=1*P(383)+0*P(384)+5*P(385)+2*P(386)+1*P(387)+2*P(388)+10*P(389)+10*P(390)+5*P(391)+2*P(392)+1*P(393)+3*P(394)+1*P(395)+5*P(396)+6*P(397)
1265 P39B=5*P(398)+5*P(399)+3*P(400)+4*P(401)+0*P(402)+1*P(403)+0*P(404)+0*P(405)+0*P(406)+5*P(407)+0*P(408)+0*P(409)+5*P(410)+0*P(411)+4*P(412)
1266 P40B=4*P(413)+5*P(414)+0*P(415)+2*P(416)+5*P(417)+0*P(418)+4*P(419)+4*P(420)+1*P(421)+0*P(422)+2*P(423)+2*P(424)+5*P(425)+5*P(426)+0*P(427)
1267 P41B=1*P(428)+0*P(429)+0*P(430)+1*P(431)+0*P(432)+10*P(433)+1*P(434)+0*P(435)+0*P(436)+0*P(437)+0*P(438)+0*P(439)+0*P(440)+0*P(441)+10*P(442)
1268 P42B=2*P(443)+2*P(444)+2*P(445)
1388 P1=P11B+P12B+P13B+P14B+P15B+P16B+P17B+P18B+P19B+P20B+P21B+P22B+P23B+P24B+P25B+P26B
1395 P2=P27B+P28B+P29B+P30B+P31B+P32B+P33B+P34B+P35B+P36B+P37B+P38B+P39B+P40B+P41B+P42B
1397 P4=0
1398 P3=0
1448 P5=P1+P2+P3+P4
1450 P=-P5+PS1
1451 IF P<=M THEN 1670
1452 M=P
1453 PP1=P5
1454 FOR KLX=1 TO 30
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1457 GOTO 128
1670 NEXT I
1702 NEXT JJ
1706 NEXT J
1777 NEXT INEW
1888 NEXT JJJ
1890 IF M>-8 THEN 1916 ELSE 1999
1916 PRINT JJJJ,M,PP1
1917 PRINT A(1),A(2),A(3),A(4),A(5)
1918 PRINT A(6),A(7),A(8),A(9),A(10)
1920 PRINT A(11),A(12),A(13),A(14),A(15)
1922 PRINT A(16),A(17),A(18),A(19),A(20)
1924 PRINT A(21),A(22),A(23),A(24),A(25)
1926 PRINT A(26),A(27),A(28),A(29),A(30)
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and its output through JJJJ=-29975 (in compressed form and to be interpreted in accordance with line 1916 through line 1926; copied manually from the computer monitor) is presented below.
-30472 -6 6
4 5 7 5 0
2 5 6 4 3
0 6 0 1 7
1 1 3 0 0
6 1 2 2 7
6 2 3 6 7
-30360 -6 6
3 6 7 6 2
0 6 5 1 4
2 5 2 3 7
3 1 4 2 2
5 1 0 0 7
5 0 4 5 7
-29975 -7 7
1 0 6 0 1
3 0 2 7 5
4 2 4 1 6
1 7 5 4 4
2 7 3 3 6
2 3 7 2 5
Among the candidate solutions presented above, the best are at JJJJ=-30472 and JJJJ=-30360 with an objective function value of 6.
The output above was produced in 16 hours on a personal computer with an Intel 2.66 GHz. chip and the IBM interpreter, which is slower than the corresponding compiler.
If one makes changes to the computer program above, such as a change of changing line 128 to, for example, 128 FOR I=1 TO 2, one may or may not obtain the best objective function value of the output above, 6, which may or may not optimal. Generally speaking, in order to increase the probability of getting an optimal solution, one preferably should run several computers simultaneously, each with a different line 128, for example; that does not have to be line 128. This multicomputer approach can mitigate the possible danger of missed optimality and can produce a usable solution faster than just running one computer.
References
[1] R.C. Carlson, G.L. Nemhauser, Scheduling to minimize interaction cost, Operations Research, 14 (1966) 52-58.
[2] S.S. Heragu, A. Kusiak, Efficient models for the facility layout problem, European Journal of Operational Research 53 (1991) 1-13.
[3] S.S. Heragu, Recent models and techniques for solving the layout problem, European Journal of Operational Research 57 (1992) 136-144.
[4] C.E. Nugent, T.E. Vollmann, J. Ruml, An experimental comparison of techniques for the assignment of facilities to locations, Operations Research 16 (1968) 150-173.
[5] W.C. Conley, Optimization: A Simplified Approach, Petrocelli, Princeton, New Jersey, 1981.

Scheduling Fifteen Activities Competing for Four Facilities

Jsun Yui Wong
This is an instance of the Carlson and Nemhauser problem of scheduling to minimize interaction cost [1]. The computer program listed below slightly changes the mathematical formulation on page 6 of Heragu and Kusiak [2] and on page 140 of Heragu [3]; its goal is to minimize the total interaction cost of assigning fifteen courses to four time periods, which are period 0, period 1, period 2, and period 3. As the individual interaction costs it uses the interdepartmental flows (of n=20, not n=15) presented in Nugent, Vollmann, and Ruml [4, p. 169]; these flows are used in line 1238 through line 1259 below.
The following computer program benefits from the computer programs of the present blog and the computer program on pages 229-232 of Conley [5].
2 DEFINT I,J,K
5 DIM B(99),N(99),A(99),H(99),L(99),U(99),X(1111),D(111),P(222)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
21 FOR IOC=1 TO 15
23 B(IOC)=0
24 NEXT IOC
51 FOR IOCTT=1 TO 15
53 N(IOCTT)=3
57 NEXT IOCTT
61 FOR KLQ=1 TO 15
62 A(KLQ)=B(KLQ)+RND*(N(KLQ)-B(KLQ))
63 NEXT KLQ
71 FOR KLR=1 TO 15
72 H(KLR)=3
73 NEXT KLR
88 FOR JJJ=1 TO 1000 STEP 10
90 FOR INEW=1 TO 1
94 FOR J=INEW*2 TO 0 STEP -1
102 FOR JJ=0 TO 15
128 FOR I=1 TO 1
129 FOR KKQQ=1 TO 15
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
132 FOR K=1 TO 15
133 IF RND<=.5 THEN 298 ELSE 230
230 IF A(K)-(N(K)-B(K))/H(K)^J250 L(K)=B(K)
255 GOTO 265
260 L(K)=A(K)-(N(K)-B(K))/H(K)^J
265 IF A(K)+(N(K)-B(K))/H(K)^J>N(K) THEN 266 ELSE 268
266 U(K)=N(K)-L(K)
267 GOTO 272
268 U(K)=A(K)+(N(K)-B(K))/H(K)^J-L(K)
272 GOTO 300
298 X(K)=A(K)+2*RND*(2*RND-1)*(1/(1+RND*JJJ))*.05*A(K)
299 GOTO 302
300 X(K)=(L(K)+2*RND*RND*U(K))
302 NEXT K
304 X(JJ)=A(JJ)
306 KLPS=FIX(1+RND*45)
307 FOR KLA1=1 TO KLPS
308 KLA2=FIX(1+15*RND)
309 X(KLA2)=A(KLA2)
310 NEXT KLA1
343 IF RND>.1 GOTO 361
352 IF RND<.5 THEN 353 ELSE 355
353 X(JJ)=B(JJ)
354 GOTO 361
355 X(JJ)=N(JJ)
361 FOR I222=1 TO 15
364 X(I222)=FIX(X(I222))
368 NEXT I222
371 FOR I223=1 TO 15
374 IF X(I223)>3 THEN X(I223)=3
378 NEXT I223
381 FOR I224=1 TO 15
384 IF X(I224)<0 THEN X(I224)=0
388 NEXT I224
461 IF RND>.1 GOTO 561
471 IOCT1=1+FIX(RND*15)
474 IOCT2=1+FIX(RND*15)
477 X(IOCT1)=A(IOCT2)
480 X(IOCT2)=A(IOCT1)
561 P(11)=ABS(X(1)-X(2))
562 P(12)=ABS(X(1)-X(3))
563 P(13)=ABS(X(1)-X(4))
564 P(14)=ABS(X(1)-X(5))
565 P(15)=ABS(X(1)-X(6))
566 P(16)=ABS(X(1)-X(7))
567 P(17)=ABS(X(1)-X(8))
568 P(18)=ABS(X(1)-X(9))
569 P(19)=ABS(X(1)-X(10))
570 P(20)=ABS(X(1)-X(11))
571 P(21)=ABS(X(1)-X(12))
572 P(22)=ABS(X(1)-X(13))
573 P(23)=ABS(X(1)-X(14))
574 P(24)=ABS(X(1)-X(15))
580 P(25)=ABS(X(2)-X(3))
581 P(26)=ABS(X(2)-X(4))
582 P(27)=ABS(X(2)-X(5))
583 P(28)=ABS(X(2)-X(6))
584 P(29)=ABS(X(2)-X(7))
585 P(30)=ABS(X(2)-X(8))
586 P(31)=ABS(X(2)-X(9))
587 P(32)=ABS(X(2)-X(10))
588 P(33)=ABS(X(2)-X(11))
589 P(34)=ABS(X(2)-X(12))
590 P(35)=ABS(X(2)-X(13))
591 P(36)=ABS(X(2)-X(14))
592 P(37)=ABS(X(2)-X(15))
598 P(38)=ABS(X(3)-X(4))
599 P(39)=ABS(X(3)-X(5))
600 P(40)=ABS(X(3)-X(6))
601 P(41)=ABS(X(3)-X(7))
602 P(42)=ABS(X(3)-X(8))
603 P(43)=ABS(X(3)-X(9))
604 P(44)=ABS(X(3)-X(10))
605 P(45)=ABS(X(3)-X(11))
606 P(46)=ABS(X(3)-X(12))
607 P(47)=ABS(X(3)-X(13))
608 P(48)=ABS(X(3)-X(14))
609 P(49)=ABS(X(3)-X(15))
615 P(50)=ABS(X(4)-X(5))
616 P(51)=ABS(X(4)-X(6))
617 P(52)=ABS(X(4)-X(7))
618 P(53)=ABS(X(4)-X(8))
619 P(54)=ABS(X(4)-X(9))
620 P(55)=ABS(X(4)-X(10))
621 P(56)=ABS(X(4)-X(11))
622 P(57)=ABS(X(4)-X(12))
623 P(58)=ABS(X(4)-X(13))
624 P(59)=ABS(X(4)-X(14))
625 P(60)=ABS(X(4)-X(15))
631 P(61)=ABS(X(5)-X(6))
632 P(62)=ABS(X(5)-X(7))
633 P(63)=ABS(X(5)-X(8))
634 P(64)=ABS(X(5)-X(9))
635 P(65)=ABS(X(5)-X(10))
636 P(66)=ABS(X(5)-X(11))
637 P(67)=ABS(X(5)-X(12))
638 P(68)=ABS(X(5)-X(13))
639 P(69)=ABS(X(5)-X(14))
640 P(70)=ABS(X(5)-X(15))
646 P(71)=ABS(X(6)-X(7))
647 P(72)=ABS(X(6)-X(8))
648 P(73)=ABS(X(6)-X(9))
649 P(74)=ABS(X(6)-X(10))
650 P(75)=ABS(X(6)-X(11))
651 P(76)=ABS(X(6)-X(12))
652 P(77)=ABS(X(6)-X(13))
653 P(78)=ABS(X(6)-X(14))
654 P(79)=ABS(X(6)-X(15))
660 P(80)=ABS(X(7)-X(8))
661 P(81)=ABS(X(7)-X(9))
662 P(82)=ABS(X(7)-X(10))
663 P(83)=ABS(X(7)-X(11))
664 P(84)=ABS(X(7)-X(12))
665 P(85)=ABS(X(7)-X(13))
666 P(86)=ABS(X(7)-X(14))
667 P(87)=ABS(X(7)-X(15))
673 P(88)=ABS(X(8)-X(9))
674 P(89)=ABS(X(8)-X(10))
675 P(90)=ABS(X(8)-X(11))
676 P(91)=ABS(X(8)-X(12))
677 P(92)=ABS(X(8)-X(13))
678 P(93)=ABS(X(8)-X(14))
679 P(94)=ABS(X(8)-X(15))
685 P(95)=ABS(X(9)-X(10))
686 P(96)=ABS(X(9)-X(11))
687 P(97)=ABS(X(9)-X(12))
688 P(98)=ABS(X(9)-X(13))
689 P(99)=ABS(X(9)-X(14))
690 P(100)=ABS(X(9)-X(15))
696 P(101)=ABS(X(10)-X(11))
697 P(102)=ABS(X(10)-X(12))
698 P(103)=ABS(X(10)-X(13))
699 P(104)=ABS(X(10)-X(14))
700 P(105)=ABS(X(10)-X(15))
706 P(106)=ABS(X(11)-X(12))
707 P(107)=ABS(X(11)-X(13))
708 P(108)=ABS(X(11)-X(14))
709 P(109)=ABS(X(11)-X(15))
715 P(110)=ABS(X(12)-X(13))
716 P(111)=ABS(X(12)-X(14))
717 P(112)=ABS(X(12)-X(15))
723 P(113)=ABS(X(13)-X(14))
724 P(114)=ABS(X(13)-X(15))
730 P(115)=ABS(X(14)-X(15))
788 FOR INSI=11 TO 115
791 IF P(INSI)<.5 THEN P(INSI)=1 ELSE P(INSI)=0
795 NEXT INSI
1238 P11B=0*P(11)+5*P(12)+0*P(13)+5*P(14)+2*P(15)+10*P(16)+3*P(17)+1*P(18)+5*P(19)+5*P(20)
1239 P12B=5*P(21)+0*P(22)+0*P(23)+5*P(24)
1240 P13B=3*P(25)+10*P(26)+5*P(27)+1*P(28)+5*P(29)+1*P(30)+2*P(31)+4*P(32)+2*P(33)
1241 P14B=5*P(34)+0*P(35)+10*P(36)+10*P(37)
1243 P15B=2*P(38)+0*P(39)+5*P(40)+2*P(41)+4*P(42)+4*P(43)+5*P(44)+0*P(45)
1244 P16B=0*P(46)+0*P(47)+5*P(48)+1*P(49)
1245 P17B=1*P(50)+0*P(51)+5*P(52)+2*P(53)+1*P(54)+0*P(55)+10*P(56)
1246 P18B=2*P(57)+2*P(58)+0*P(59)+2*P(60)
1248 P19B=5*P(61)+6*P(62)+5*P(63)+2*P(64)+5*P(65)+2*P(66)+0*P(67)+5*P(68)+1*P(69)+1*P(70)
1249 P20B=5*P(71)+2*P(72)+1*P(73)+6*P(74)+0*P(75)+0*P(76)+10*P(77)+0*P(78)+2*P(79)
1250 P21B=0*P(80)+0*P(81)+0*P(82)+5*P(83)+10*P(84)+2*P(85)+2*P(86)+5*P(87)
1251 P22B=1*P(88)+1*P(89)+10*P(90)+10*P(91)+2*P(92)+0*P(93)+10*P(94)
1255 P23B=2*P(95)+0*P(96)+3*P(97)+5*P(98)+5*P(99)+0*P(100)
1257 P24B=5*P(101)+5*P(102)+0*P(103)+5*P(104)+1*P(105)
1258 P25B=5*P(106)+2*P(107)+5*P(108)+1*P(109)
1259 P26B=2*P(110)+10*P(111)+5*P(112)+2*P(113)+2*P(114)+5*P(115)
1445 P1=P11B+P12B+P13B+P14B+P15B+P16B+P17B+P18B+P19B+P20B+P21B+P22B+P23B+P24B+P25B+P26B
1446 P2=0
1448 P3=P1+P2
1450 P=-P3+PS1
1451 IF P<=M THEN 1670
1452 M=P
1453 PP1=P3
1454 FOR KLX=1 TO 15
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1457 GOTO 128
1670 NEXT I
1702 NEXT JJ
1706 NEXT J
1777 NEXT INEW
1888 NEXT JJJ
1890 IF M>-9999 THEN 1916 ELSE 1999
1916 PRINT JJJJ,M,PP1
1917 PRINT A(1),A(2),A(3),A(4),A(5)
1918 PRINT A(6),A(7),A(8),A(9),A(10)
1920 PRINT A(11),A(12),A(13),A(14),A(15)
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the candidate solutions produced from JJJJ=-32000 through JJJJ=-31995 (in compressed form and to be interpreted in accordance with line 1916 through line 1920; copied manually from the computer monitor) are presented below.
-32000 -20 20
0 0 2 3 2
3 1 1 3 1
2 3 0 1 2
-31999 -21 21
0 2 1 0 1
0 2 2 2 3
1 1 3 0 3
-31998 -17 17
2 0 1 2 1
2 3 3 3 3
0 1 0 2 1
-31997 -17 17
0 3 2 0 2
0 1 1 1 1
3 2 3 0 2
-31996 -17 17
1 0 2 1 2
1 3 3 3 3
0 2 0 1 2
-31995 -18 18
1 0 3 1 3
1 0 0 2 0
2 3 0 1 2
Among the candidate solutions presented above, the best are at JJJJ=-31998, JJJJ=-31997, and JJJJ=-31996 with an objective function value of 17.
The output above was produced in one minute on a personal computer with an Intel 2.66 GHz. chip and the IBM interpreter, which is slower than the corresponding compiler.
References
[1] R.C. Carlson, G.L. Nemhauser, Scheduling to minimize interaction cost, Operations Research 14 (1966) 52-58.
[2] S.S. Heragu, A. Kusiak, Efficient models for the facility layout problem, European Journal of Operational Research 53 (1991) 1-13.
[3] S.S. Heragu, Recent models and techniques for solving the layout problem, European Journal of Operational Research 57 (1992) 136-144.
[4] C.E. Nugent, T.E. Vollmann, J. Ruml, An experimental comparison of techniques for the assignment of facilities to locations, Operations Research 16 (1968) 150-173.
[5] W.C. Conley, Optimization: A Simplified Approach, Petrocelli, Princeton, New Jersey, 1981.

A General Integer Programming Computer Program Applied to a Three-Dimensional Layout Problem

Jsun Yui Wong
The problem considered here is essentially the 12-location problem in Hillier [1] and in Nugent, Vollmann, and Ruml [2] plus a change to more than 12 locations spread over three dimensions. The same interfacility flows [1, p. 33; 2, p. 168] are used here. So one knows the minimum objective function value to this newer problem is 289 [2, p. 159] or smaller.
Line 561 through line 626 of the computer program below extend to three dimensions the mathematical formulation appearing on page 6 of Heragu and Kusiak [3] and on page 140 of Heragu [4]. Line 1321 through line 1414 below use the interdepartmental flows presented in Hillier [1, p. 33] and in Nugent, Vollmann, and Ruml [2, p. 168].
The following computer program benefits from the computer programs of the present blog and the computer program on pages 229-232 of Conley [5].
2 DEFINT I,J,K
5 DIM B(99),N(99),A(99),H(99),L(99),U(99),X(1111),D(111),P(222)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
43 FOR IOC=1 TO 36
45 B(IOC)=0
47 NEXT IOC
51 FOR IOCTT=1 TO 36
53 N(IOCTT)=2
57 NEXT IOCTT
61 FOR KLQ=1 TO 36
62 A(KLQ)=B(KLQ)+RND*(N(KLQ)-B(KLQ))
63 NEXT KLQ
71 FOR KLR=1 TO 36
72 H(KLR)=3
73 NEXT KLR
88 FOR JJJ=1 TO 1000 STEP 10
90 FOR INEW=1 TO 1
94 FOR J=INEW*2 TO 0 STEP -1
102 FOR JJ=0 TO 36
128 FOR I=1 TO 3
129 FOR KKQQ=1 TO 36
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
132 FOR K=1 TO 36
133 IF RND<=.5 THEN 298 ELSE 230
134 REM
137 REM
230 IF A(K)-(N(K)-B(K))/H(K)^J250 L(K)=B(K)
255 GOTO 265
260 L(K)=A(K)-(N(K)-B(K))/H(K)^J
265 IF A(K)+(N(K)-B(K))/H(K)^J>N(K) THEN 266 ELSE 268
266 U(K)=N(K)-L(K)
267 GOTO 272
268 U(K)=A(K)+(N(K)-B(K))/H(K)^J-L(K)
272 GOTO 300
298 X(K)=A(K)+2*RND*(2*RND-1)*(1/(1+RND*JJJ))*.05*A(K)
299 GOTO 302
300 X(K)=(L(K)+2*RND*RND*U(K))
302 NEXT K
304 X(JJ)=A(JJ)
306 KLPS=FIX(1+RND*108)
307 FOR KLA1=1 TO KLPS
308 KLA2=FIX(1+36*RND)
309 X(KLA2)=A(KLA2)
310 NEXT KLA1
343 IF RND>.1 GOTO 361
352 IF RND<.5 THEN 353 ELSE 355
353 X(JJ)=B(JJ)
354 GOTO 361
355 X(JJ)=N(JJ)
361 FOR I222=1 TO 36
364 X(I222)=FIX(X(I222))
368 NEXT I222
461 IF RND>.1 GOTO 531
465 IF RND<1/3 THEN 471 ELSE IF RND<1/2 THEN 491 ELSE 511
471 IOCT1=1+FIX(RND*12)
474 IOCT2=1+FIX(RND*12)
477 X(IOCT1)=A(IOCT2)
480 X(IOCT2)=A(IOCT1)
481 GOTO 531
491 IOCT6=13+FIX(RND*12)
494 IOCT7=13+FIX(RND*12)
497 X(IOCT6)=A(IOCT7)
500 X(IOCT7)=A(IOCT6)
502 GOTO 531
511 IOCT8=25+FIX(RND*12)
514 IOCT9=25+FIX(RND*12)
517 X(IOCT8)=A(IOCT9)
520 X(IOCT9)=A(IOCT8)
522 GOTO 531
531 FOR IOCX=1 TO 36
533 IF X(IOCX)>2 THEN X(IOCX)=1
535 NEXT IOCX
541 FOR IOCY=1 TO 36
543 IF X(IOCY)<0 THEN X(IOCY)=0
545 NEXT IOCY
561 P(11)=ABS(X(1)-X(2))+ABS(X(13)-X(14))+ABS(X(25)-X(26))-1
562 P(12)=ABS(X(1)-X(3))+ABS(X(13)-X(15))+ABS(X(25)-X(27))-1
563 P(13)=ABS(X(1)-X(4))+ABS(X(13)-X(16))+ABS(X(25)-X(28))-1
564 P(14)=ABS(X(1)-X(5))+ABS(X(13)-X(17))+ABS(X(25)-X(29))-1
565 P(15)=ABS(X(1)-X(6))+ABS(X(13)-X(18))+ABS(X(25)-X(30))-1
566 P(16)=ABS(X(1)-X(7))+ABS(X(13)-X(19))+ABS(X(25)-X(31))-1
567 P(17)=ABS(X(1)-X(8))+ABS(X(13)-X(20))+ABS(X(25)-X(32))-1
568 P(18)=ABS(X(1)-X(9))+ABS(X(13)-X(21))+ABS(X(25)-X(33))-1
569 P(19)=ABS(X(1)-X(10))+ABS(X(13)-X(22))+ABS(X(25)-X(34))-1
570 P(20)=ABS(X(1)-X(11))+ABS(X(13)-X(23))+ABS(X(25)-X(35))-1
571 P(21)=ABS(X(1)-X(12))+ABS(X(13)-X(24))+ABS(X(25)-X(36))-1
572 P(22)=ABS(X(2)-X(3))+ABS(X(14)-X(15))+ABS(X(26)-X(27))-1
573 P(23)=ABS(X(2)-X(4))+ABS(X(14)-X(16))+ABS(X(26)-X(28))-1
574 P(24)=ABS(X(2)-X(5))+ABS(X(14)-X(17))+ABS(X(26)-X(29))-1
575 P(25)=ABS(X(2)-X(6))+ABS(X(14)-X(18))+ABS(X(26)-X(30))-1
576 P(26)=ABS(X(2)-X(7))+ABS(X(14)-X(19))+ABS(X(26)-X(31))-1
577 P(27)=ABS(X(2)-X(8))+ABS(X(14)-X(20))+ABS(X(26)-X(32))-1
578 P(28)=ABS(X(2)-X(9))+ABS(X(14)-X(21))+ABS(X(26)-X(33))-1
579 P(29)=ABS(X(2)-X(10))+ABS(X(14)-X(22))+ABS(X(26)-X(34))-1
580 P(30)=ABS(X(2)-X(11))+ABS(X(14)-X(23))+ABS(X(26)-X(35))-1
581 P(31)=ABS(X(2)-X(12))+ABS(X(14)-X(24))+ABS(X(26)-X(36))-1
582 P(32)=ABS(X(3)-X(4))+ABS(X(15)-X(16))+ABS(X(27)-X(28))-1
583 P(33)=ABS(X(3)-X(5))+ABS(X(15)-X(17))+ABS(X(27)-X(29))-1
584 P(34)=ABS(X(3)-X(6))+ABS(X(15)-X(18))+ABS(X(27)-X(30))-1
585 P(35)=ABS(X(3)-X(7))+ABS(X(15)-X(19))+ABS(X(27)-X(31))-1
586 P(36)=ABS(X(3)-X(8))+ABS(X(15)-X(20))+ABS(X(27)-X(32))-1
587 P(37)=ABS(X(3)-X(9))+ABS(X(15)-X(21))+ABS(X(27)-X(33))-1
588 P(38)=ABS(X(3)-X(10))+ABS(X(15)-X(22))+ABS(X(27)-X(34))-1
589 P(39)=ABS(X(3)-X(11))+ABS(X(15)-X(23))+ABS(X(27)-X(35))-1
590 P(40)=ABS(X(3)-X(12))+ABS(X(15)-X(24))+ABS(X(27)-X(36))-1
591 P(41)=ABS(X(4)-X(5))+ABS(X(16)-X(17))+ABS(X(28)-X(29))-1
592 P(42)=ABS(X(4)-X(6))+ABS(X(16)-X(18))+ABS(X(28)-X(30))-1
593 P(43)=ABS(X(4)-X(7))+ABS(X(16)-X(19))+ABS(X(28)-X(31))-1
594 P(44)=ABS(X(4)-X(8))+ABS(X(16)-X(20))+ABS(X(28)-X(32))-1
595 P(45)=ABS(X(4)-X(9))+ABS(X(16)-X(21))+ABS(X(28)-X(33))-1
596 P(46)=ABS(X(4)-X(10))+ABS(X(16)-X(22))+ABS(X(28)-X(34))-1
597 P(47)=ABS(X(4)-X(11))+ABS(X(16)-X(23))+ABS(X(28)-X(35))-1
598 P(48)=ABS(X(4)-X(12))+ABS(X(16)-X(24))+ABS(X(28)-X(36))-1
599 P(49)=ABS(X(5)-X(6))+ABS(X(17)-X(18))+ABS(X(29)-X(30))-1
600 P(50)=ABS(X(5)-X(7))+ABS(X(17)-X(19))+ABS(X(29)-X(31))-1
601 P(51)=ABS(X(5)-X(8))+ABS(X(17)-X(20))+ABS(X(29)-X(32))-1
602 P(52)=ABS(X(5)-X(9))+ABS(X(17)-X(21))+ABS(X(29)-X(33))-1
603 P(53)=ABS(X(5)-X(10))+ABS(X(17)-X(22))+ABS(X(29)-X(34))-1
604 P(54)=ABS(X(5)-X(11))+ABS(X(17)-X(23))+ABS(X(29)-X(35))-1
605 P(55)=ABS(X(5)-X(12))+ABS(X(17)-X(24))+ABS(X(29)-X(36))-1
606 P(56)=ABS(X(6)-X(7))+ABS(X(18)-X(19))+ABS(X(30)-X(31))-1
607 P(57)=ABS(X(6)-X(8))+ABS(X(18)-X(20))+ABS(X(30)-X(32))-1
608 P(58)=ABS(X(6)-X(9))+ABS(X(18)-X(21))+ABS(X(30)-X(33))-1
609 P(59)=ABS(X(6)-X(10))+ABS(X(18)-X(22))+ABS(X(30)-X(34))-1
610 P(60)=ABS(X(6)-X(11))+ABS(X(18)-X(23))+ABS(X(30)-X(35))-1
611 P(61)=ABS(X(6)-X(12))+ABS(X(18)-X(24))+ABS(X(30)-X(36))-1
612 P(62)=ABS(X(7)-X(8))+ABS(X(19)-X(20))+ABS(X(31)-X(32))-1
613 P(63)=ABS(X(7)-X(9))+ABS(X(19)-X(21))+ABS(X(31)-X(33))-1
614 P(64)=ABS(X(7)-X(10))+ABS(X(19)-X(22))+ABS(X(31)-X(34))-1
615 P(65)=ABS(X(7)-X(11))+ABS(X(19)-X(23))+ABS(X(31)-X(35))-1
616 P(66)=ABS(X(7)-X(12))+ABS(X(19)-X(24))+ABS(X(31)-X(36))-1
617 P(67)=ABS(X(8)-X(9))+ABS(X(20)-X(21))+ABS(X(32)-X(33))-1
618 P(68)=ABS(X(8)-X(10))+ABS(X(20)-X(22))+ABS(X(32)-X(34))-1
619 P(69)=ABS(X(8)-X(11))+ABS(X(20)-X(23))+ABS(X(32)-X(35))-1
620 P(70)=ABS(X(8)-X(12))+ABS(X(20)-X(24))+ABS(X(32)-X(36))-1
621 P(71)=ABS(X(9)-X(10))+ABS(X(21)-X(22))+ABS(X(33)-X(34))-1
622 P(72)=ABS(X(9)-X(11))+ABS(X(21)-X(23))+ABS(X(33)-X(35))-1
623 P(73)=ABS(X(9)-X(12))+ABS(X(21)-X(24))+ABS(X(33)-X(36))-1
624 P(74)=ABS(X(10)-X(11))+ABS(X(22)-X(23))+ABS(X(34)-X(35))-1
625 P(75)=ABS(X(10)-X(12))+ABS(X(22)-X(24))+ABS(X(34)-X(36))-1
626 P(76)=ABS(X(11)-X(12))+ABS(X(23)-X(24))+ABS(X(35)-X(36))-1
788 FOR INSI=11 TO 76
791 IF P(INSI)<0 THEN P(INSI)=P(INSI) ELSE P(INSI)=0
795 NEXT INSI
1111 PSUM=0
1115 FOR IOCT=11 TO 76
1118 PSUM=PSUM+P(IOCT)
1121 NEXT IOCT
1131 PS1=99*555555!*PSUM
1321 P11B=5*ABS(X(1)-X(2))+2*ABS(X(1)-X(3))+4*ABS(X(1)-X(4))+1*ABS(X(1)-X(5))+0*ABS(X(1)-X(6))
1322 P12B=0*ABS(X(1)-X(7))+6*ABS(X(1)-X(8))+2*ABS(X(1)-X(9))+1*ABS(X(1)-X(10))+1*ABS(X(1)-X(11))+1*ABS(X(1)-X(12))
1323 P13B=3*ABS(X(2)-X(3))+0*ABS(X(2)-X(4))+2*ABS(X(2)-X(5))+2*ABS(X(2)-X(6))+2*ABS(X(2)-X(7))
1324 P14B=0*ABS(X(2)-X(8))+4*ABS(X(2)-X(9))+5*ABS(X(2)-X(10))+0*ABS(X(2)-X(11))+0*ABS(X(2)-X(12))
1325 P15B=0*ABS(X(3)-X(4))+0*ABS(X(3)-X(5))+0*ABS(X(3)-X(6))+0*ABS(X(3)-X(7))+5*ABS(X(3)-X(8))
1326 P16B=5*ABS(X(3)-X(9))+2*ABS(X(3)-X(10))+2*ABS(X(3)-X(11))+2*ABS(X(3)-X(12))
1327 P17B=5*ABS(X(4)-X(5))+2*ABS(X(4)-X(6))+2*ABS(X(4)-X(7))+10*ABS(X(4)-X(8))+0*ABS(X(4)-X(9))+0*ABS(X(4)-X(10))+5*ABS(X(4)-X(11))+5*ABS(X(4)-X(12))
1328 P18B=10*ABS(X(5)-X(6))+0*ABS(X(5)-X(7))+0*ABS(X(5)-X(8))+0*ABS(X(5)-X(9))+5*ABS(X(5)-X(10))+1*ABS(X(5)-X(11))+1*ABS(X(5)-X(12))
1329 P19B=5*ABS(X(6)-X(7))+1*ABS(X(6)-X(8))+1*ABS(X(6)-X(9))+5*ABS(X(6)-X(10))+4*ABS(X(6)-X(11))+0*ABS(X(6)-X(12))
1330 P20B=10*ABS(X(7)-X(8))+5*ABS(X(7)-X(9))+2*ABS(X(7)-X(10))+3*ABS(X(7)-X(11))+3*ABS(X(7)-X(12))
1331 P21B=0*ABS(X(8)-X(9))+0*ABS(X(8)-X(10))+5*ABS(X(8)-X(11))+0*ABS(X(8)-X(12))
1332 P22B=0*ABS(X(9)-X(10))+10*ABS(X(9)-X(11))+10*ABS(X(9)-X(12))
1333 P23B=5*ABS(X(10)-X(11))+0*ABS(X(10)-X(12))
1334 P24B=2*ABS(X(11)-X(12))
1351 P25B=5*ABS(X(13)-X(14))+2*ABS(X(13)-X(15))+4*ABS(X(13)-X(16))+1*ABS(X(13)-X(17))+0*ABS(X(13)-X(18))
1352 P26B=0*ABS(X(13)-X(19))+6*ABS(X(13)-X(20))+2*ABS(X(13)-X(21))+1*ABS(X(13)-X(22))+1*ABS(X(13)-X(23))+1*ABS(X(13)-X(24))
1353 P27B=3*ABS(X(14)-X(15))+0*ABS(X(14)-X(16))+2*ABS(X(14)-X(17))+2*ABS(X(14)-X(18))+2*ABS(X(14)-X(19))
1354 P28B=0*ABS(X(14)-X(20))+4*ABS(X(14)-X(21))+5*ABS(X(14)-X(22))+0*ABS(X(14)-X(23))+0*ABS(X(14)-X(24))
1355 P29B=0*ABS(X(15)-X(16))+0*ABS(X(15)-X(17))+0*ABS(X(15)-X(18))+0*ABS(X(15)-X(19))+5*ABS(X(15)-X(20))
1356 P30B=5*ABS(X(15)-X(21))+2*ABS(X(15)-X(22))+2*ABS(X(15)-X(23))+2*ABS(X(15)-X(24))
1367 P31B=5*ABS(X(16)-X(17))+2*ABS(X(16)-X(18))+2*ABS(X(16)-X(19))+10*ABS(X(16)-X(20))+0*ABS(X(16)-X(21))+0*ABS(X(16)-X(22))+5*ABS(X(16)-X(23))+5*ABS(X(16)-X(24))
1368 P32B=10*ABS(X(17)-X(18))+0*ABS(X(17)-X(19))+0*ABS(X(17)-X(20))+0*ABS(X(17)-X(21))+5*ABS(X(17)-X(22))+1*ABS(X(17)-X(23))+1*ABS(X(17)-X(24))
1369 P33B=5*ABS(X(18)-X(19))+1*ABS(X(18)-X(20))+1*ABS(X(18)-X(21))+5*ABS(X(18)-X(22))+4*ABS(X(18)-X(23))+0*ABS(X(18)-X(24))
1370 P34B=10*ABS(X(19)-X(20))+5*ABS(X(19)-X(21))+2*ABS(X(19)-X(22))+3*ABS(X(19)-X(23))+3*ABS(X(19)-X(24))
1371 P35B=0*ABS(X(20)-X(21))+0*ABS(X(20)-X(22))+5*ABS(X(20)-X(23))+0*ABS(X(20)-X(24))
1372 P36B=0*ABS(X(21)-X(22))+10*ABS(X(21)-X(23))+10*ABS(X(21)-X(24))
1373 P37B=5*ABS(X(22)-X(23))+0*ABS(X(22)-X(24))
1374 P38B=2*ABS(X(23)-X(24))
1401 P39B=5*ABS(X(25)-X(26))+2*ABS(X(25)-X(27))+4*ABS(X(25)-X(28))+1*ABS(X(25)-X(29))+0*ABS(X(25)-X(30))
1402 P40B=0*ABS(X(25)-X(31))+6*ABS(X(25)-X(32))+2*ABS(X(25)-X(33))+1*ABS(X(25)-X(34))+1*ABS(X(25)-X(35))+1*ABS(X(25)-X(36))
1403 P41B=3*ABS(X(26)-X(27))+0*ABS(X(26)-X(28))+2*ABS(X(26)-X(29))+2*ABS(X(26)-X(30))+2*ABS(X(26)-X(31))
1404 P42B=0*ABS(X(26)-X(32))+4*ABS(X(26)-X(33))+5*ABS(X(26)-X(34))+0*ABS(X(26)-X(35))+0*ABS(X(26)-X(36))
1405 P43B=0*ABS(X(27)-X(28))+0*ABS(X(27)-X(29))+0*ABS(X(27)-X(30))+0*ABS(X(27)-X(31))+5*ABS(X(27)-X(32))
1406 P44B=5*ABS(X(27)-X(33))+2*ABS(X(27)-X(34))+2*ABS(X(27)-X(35))+2*ABS(X(27)-X(36))
1407 P45B=5*ABS(X(28)-X(29))+2*ABS(X(28)-X(30))+2*ABS(X(28)-X(31))+10*ABS(X(28)-X(32))+0*ABS(X(28)-X(33))+0*ABS(X(28)-X(34))+5*ABS(X(28)-X(35))+5*ABS(X(28)-X(36))
1408 P46B=10*ABS(X(29)-X(30))+0*ABS(X(29)-X(31))+0*ABS(X(29)-X(32))+0*ABS(X(29)-X(33))+5*ABS(X(29)-X(34))+1*ABS(X(29)-X(35))+1*ABS(X(29)-X(36))
1409 P47B=5*ABS(X(30)-X(31))+1*ABS(X(30)-X(32))+1*ABS(X(30)-X(33))+5*ABS(X(30)-X(34))+4*ABS(X(30)-X(35))+0*ABS(X(30)-X(36))
1410 P48B=10*ABS(X(31)-X(32))+5*ABS(X(31)-X(33))+2*ABS(X(31)-X(34))+3*ABS(X(31)-X(35))+3*ABS(X(31)-X(36))
1411 P49B=0*ABS(X(32)-X(33))+0*ABS(X(32)-X(34))+5*ABS(X(32)-X(35))+0*ABS(X(32)-X(36))
1412 P50B=0*ABS(X(33)-X(34))+10*ABS(X(33)-X(35))+10*ABS(X(33)-X(36))
1413 P51B=5*ABS(X(34)-X(35))+0*ABS(X(34)-X(36))
1414 P52B=2*ABS(X(35)-X(36))
1443 P1=P11B+P12B+P13B+P14B+P15B+P16B+P17B+P18B+P19B+P20B
1444 P2=P21B+P22B+P23B+P24B+P25B+P26B+P27B+P28B+P29B+P30B
1445 P3=P31B+P32B+P33B+P34B+P35B+P36B+P37B+P38B
1446 P4=P39B+P40B+P41B+P42B+P43B+P44B+P45B+P46B+P47B+P48B
1447 P5=P49B+P50B+P51B+P52B
1448 P6=P1+P2+P3+P4+P5
1450 P=-P6+PS1
1451 IF P<=M THEN 1670
1452 M=P
1453 PP1=P6
1454 FOR KLX=1 TO 36
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1457 GOTO 128
1670 NEXT I
1702 NEXT JJ
1706 NEXT J
1777 NEXT INEW
1778 REM
1888 NEXT JJJ
1890 IF M>-280 THEN 1916 ELSE 1999
1916 PRINT JJJJ,M,PP1
1917 PRINT A(1),A(2),A(3),A(4),A(5)
1918 PRINT A(6),A(7),A(8),A(9),A(10)
1920 PRINT A(11),A(12)
1922 PRINT A(13),A(14),A(15),A(16),A(17)
1924 PRINT A(18),A(19),A(20),A(21),A(22)
1926 PRINT A(23),A(24)
1928 PRINT A(25),A(26),A(27),A(28),A(29)
1930 PRINT A(30),A(31),A(32),A(33),A(34)
1932 PRINT A(35),A(36),JJJJ,M,PP1
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the best candidate solutions produced from JJJJ=-32000 through JJJJ=-31658 (in compressed form and to be interpreted in accordance with line 1916 through line 1932; copied manually from the computer monitor) are presented below.
-31989 -262 262
2 0 1 2 0
0 1 2 1 0
1 2
0 0 0 1 1
1 0 0 1 0
1 1
1 1 1 0 1
0 0 0 1 0
0 1 -31989 -262 262
-31716 -262 262
0 2 1 0 2
2 1 0 1 2
1 0
1 1 1 0 0
0 1 1 0 1
0 0
0 0 0 1 0
1 1 1 0 1
1 0 -31716 -262 262
-31658 -263 263
1 1 0 1 1
0 0 0 1 0
0 1
2 0 2 2 0
0 1 2 1 0
1 1
1 1 1 0 0
0 0 0 1 1
1 0 -31658 -263 263
The best candidate solutions shown above are at JJJJ=-31989 and at JJJJ=-31716 with an objective function value of 262. 289, the minimum objective function value for the older problem [2, p. 159], to 262 is 1.103 to 1.
The output above was produced in 7 hours on a personal computer with an Intel 2.66 GHz. chip and the IBM interpreter, which is slower than the corresponding compiler.
If one makes changes to the computer program above, such as a change of changing line 128 above to 128 FOR I=1 TO 4, one may or may not obtain 262, which may or may not be optimal. That leads to a general remedy that in general, in order to increase the chance of getting an optimal solution, one preferably should run several computers simultaneously, each with a different line 128, for example; instead of line 128, another line can be chosen. This multicomputer approach can mitigate the possible danger of missed optimality and can produce a usable solution faster than just running one computer.
References
[1] F.S. Hillier, Quantitative tools for plant layout analysis, J. Indust. Eng. 14 (1963) 33-40.
[2] C.E. Nugent, T.E. Vollmann, J. Ruml, An experimental comparison of techniques for the assignment of facilities to locations, Operations Research 16 (1968) 150-173.
[3] S.S. Heragu, A. Kusiak, Efficient models for the facility layout problem, European Journal of Operational Research 53 (1991) 1-13.
[4] S.S. Heragu, Recent models and techniques for solving the layout problem, European Journal of Operational Research 57 (1992) 136-144.
[5] W.C. Conley, Optimization: A Simplified Approach, Petrocelli, Princeton, New Jersey, 1981.

An Integer Programming Computer Program Applied to a Scheduling Problem

Jsun Yui Wong
This paper is concerned with the Carlson and Nemhauser problem of scheduling to minimize interaction cost [1]. The computer program listed below uses in line 561 through line 626 the mathematical formulation appearing on page 6 of Heragu and Kusiak [2] and on page 140 of Heragu [3]; it attempts to minimize the total interaction cost of assigning twelve courses to four time periods, which are period 0, period 1, period 2, and period 3. The total interaction cost is the sum of the individual interaction costs. An individual interaction cost occurs when, for example, a student wants to take two courses scheduled during the same time period. For these individual interaction costs, the BASIC computer program below uses the interdepartmental flows presented in Hillier [4] and in Nugent, Vollmann, and Ruml [5]; these flows are used in line 1321 through line 1334 below.
The following computer program benefits from the computer programs of the present blog and the computer program on pages 229-232 of Conley [6].
2 DEFINT I,J,K
5 DIM B(99),N(99),A(99),H(99),L(99),U(99),X(1111),D(111),P(222)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
43 FOR IOC=1 TO 12
45 B(IOC)=0
47 NEXT IOC
51 FOR IOCTT=1 TO 12
53 N(IOCTT)=3
57 NEXT IOCTT
61 FOR KLQ=1 TO 12
62 A(KLQ)=B(KLQ)+RND*(N(KLQ)-B(KLQ))
63 NEXT KLQ
71 FOR KLR=1 TO 12
72 H(KLR)=3
73 NEXT KLR
88 FOR JJJ=1 TO 1000 STEP 10
90 FOR INEW=1 TO 1
94 FOR J=INEW*2 TO 0 STEP -1
102 FOR JJ=0 TO 12
128 FOR I=1 TO 1
129 FOR KKQQ=1 TO 12
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
132 FOR K=1 TO 12
133 IF RND<=.5 THEN 298 ELSE 230
230 IF A(K)-(N(K)-B(K))/H(K)^J250 L(K)=B(K)
255 GOTO 265
260 L(K)=A(K)-(N(K)-B(K))/H(K)^J
265 IF A(K)+(N(K)-B(K))/H(K)^J>N(K) THEN 266 ELSE 268
266 U(K)=N(K)-L(K)
267 GOTO 272
268 U(K)=A(K)+(N(K)-B(K))/H(K)^J-L(K)
272 GOTO 300
298 X(K)=A(K)+2*RND*(2*RND-1)*(1/(1+RND*JJJ))*.05*A(K)
299 GOTO 302
300 X(K)=(L(K)+2*RND*RND*U(K))
302 NEXT K
304 X(JJ)=A(JJ)
306 KLPS=FIX(1+RND*36)
307 FOR KLA1=1 TO KLPS
308 KLA2=FIX(1+12*RND)
309 X(KLA2)=A(KLA2)
310 NEXT KLA1
343 IF RND>.1 GOTO 361
352 IF RND<=.9 THEN 353 ELSE 355
353 X(JJ)=B(JJ)
354 GOTO 361
355 X(JJ)=N(JJ)
361 FOR I222=1 TO 12
364 X(I222)=FIX(X(I222))
368 NEXT I222
411 FOR I223=1 TO 12
416 IF X(I223)>3 THEN X(I223)=3
418 NEXT I223
421 FOR I224=1 TO 12
426 IF X(I224)<0 THEN X(I224)=0
428 NEXT I224
461 IF RND>.1 GOTO 561
465 IF RND<5 THEN 471 ELSE IF RND<1/2 THEN 491 ELSE 511
471 IOCT1=1+FIX(RND*12)
474 IOCT2=1+FIX(RND*12)
477 X(IOCT1)=A(IOCT2)
480 X(IOCT2)=A(IOCT1)
561 P(11)=ABS(X(1)-X(2))-.5
562 P(12)=ABS(X(1)-X(3))-.5
563 P(13)=ABS(X(1)-X(4))-.5
564 P(14)=ABS(X(1)-X(5))-.5
565 P(15)=ABS(X(1)-X(6))-.5
566 P(16)=ABS(X(1)-X(7))-.5
567 P(17)=ABS(X(1)-X(8))-.5
568 P(18)=ABS(X(1)-X(9))-.5
569 P(19)=ABS(X(1)-X(10))-.5
570 P(20)=ABS(X(1)-X(11))-.5
571 P(21)=ABS(X(1)-X(12))-.5
572 P(22)=ABS(X(2)-X(3))-.5
573 P(23)=ABS(X(2)-X(4))-.5
574 P(24)=ABS(X(2)-X(5))-.5
575 P(25)=ABS(X(2)-X(6))-.5
576 P(26)=ABS(X(2)-X(7))-.5
577 P(27)=ABS(X(2)-X(8))-.5
578 P(28)=ABS(X(2)-X(9))-.5
579 P(29)=ABS(X(2)-X(10))-.5
580 P(30)=ABS(X(2)-X(11))-.5
581 P(31)=ABS(X(2)-X(12))-.5
582 P(32)=ABS(X(3)-X(4))-.5
583 P(33)=ABS(X(3)-X(5))-.5
584 P(34)=ABS(X(3)-X(6))-.5
585 P(35)=ABS(X(3)-X(7))-.5
586 P(36)=ABS(X(3)-X(8))-.5
587 P(37)=ABS(X(3)-X(9))-.5
588 P(38)=ABS(X(3)-X(10))-.5
589 P(39)=ABS(X(3)-X(11))-.5
590 P(40)=ABS(X(3)-X(12))-.5
591 P(41)=ABS(X(4)-X(5))-.5
592 P(42)=ABS(X(4)-X(6))-.5
593 P(43)=ABS(X(4)-X(7))-.5
594 P(44)=ABS(X(4)-X(8))-.5
595 P(45)=ABS(X(4)-X(9))-.5
596 P(46)=ABS(X(4)-X(10))-.5
597 P(47)=ABS(X(4)-X(11))-.5
598 P(48)=ABS(X(4)-X(12))-.5
599 P(49)=ABS(X(5)-X(6))-.5
600 P(50)=ABS(X(5)-X(7))-.5
601 P(51)=ABS(X(5)-X(8))-.5
602 P(52)=ABS(X(5)-X(9))-.5
603 P(53)=ABS(X(5)-X(10))-.5
604 P(54)=ABS(X(5)-X(11))-.5
605 P(55)=ABS(X(5)-X(12))-.5
606 P(56)=ABS(X(6)-X(7))-.5
607 P(57)=ABS(X(6)-X(8))-.5
608 P(58)=ABS(X(6)-X(9))-.5
609 P(59)=ABS(X(6)-X(10))-.5
610 P(60)=ABS(X(6)-X(11))-.5
611 P(61)=ABS(X(6)-X(12))-.5
612 P(62)=ABS(X(7)-X(8))-.5
613 P(63)=ABS(X(7)-X(9))-.5
614 P(64)=ABS(X(7)-X(10))-.5
615 P(65)=ABS(X(7)-X(11))-.5
616 P(66)=ABS(X(7)-X(12))-.5
617 P(67)=ABS(X(8)-X(9))-.5
618 P(68)=ABS(X(8)-X(10))-.5
619 P(69)=ABS(X(8)-X(11))-.5
620 P(70)=ABS(X(8)-X(12))-.5
621 P(71)=ABS(X(9)-X(10))-.5
622 P(72)=ABS(X(9)-X(11))-.5
623 P(73)=ABS(X(9)-X(12))-.5
624 P(74)=ABS(X(10)-X(11))-.5
625 P(75)=ABS(X(10)-X(12))-.5
626 P(76)=ABS(X(11)-X(12))-.5
788 FOR INSI=11 TO 76
791 IF P(INSI)<0 THEN P(INSI)=1 ELSE P(INSI)=0
795 NEXT INSI
1321 P11B=5*P(11)+2*P(12)+4*P(13)+1*P(14)+0*P(15)
1322 P12B=0*P(16)+6*P(17)+2*P(18)+1*P(19)+1*P(20)+1*P(21)
1323 P13B=3*P(22)+0*P(23)+2*P(24)+2*P(25)+2*P(26)
1324 P14B=0*P(27)+4*P(28)+5*P(29)+0*P(30)+0*P(31)
1325 P15B=0*P(32)+0*P(33)+0*P(34)+0*P(35)+5*P(36)
1326 P16B=5*P(37)+2*P(38)+2*P(39)+2*P(40)
1327 P17B=5*P(41)+2*P(42)+2*P(43)+10*P(44)+0*P(45)+0*P(46)+5*P(47)+5*P(48)
1328 P18B=10*P(49)+0*P(50)+0*P(51)+0*P(52)+5*P(53)+1*P(54)+1*P(55)
1329 P19B=5*P(56)+1*P(57)+1*P(58)+5*P(59)+4*P(60)+0*P(61)
1330 P20B=10*P(62)+5*P(63)+2*P(64)+3*P(65)+3*P(66)
1331 P21B=0*P(67)+0*P(68)+5*P(69)+0*P(70)
1332 P22B=0*P(71)+10*P(72)+10*P(73)
1333 P23B=5*P(74)+0*P(75)
1334 P24B=2*P(76)
1443 P1=P11B+P12B+P13B+P14B+P15B+P16B+P17B+P18B+P19B+P20B
1444 P2=P21B+P22B+P23B+P24B
1448 P6=P1+P2
1450 P=-P6+PS1
1451 IF P<=M THEN 1670
1452 M=P
1453 PP1=P6
1454 FOR KLX=1 TO 12
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1457 GOTO 128
1670 NEXT I
1702 NEXT JJ
1706 NEXT J
1777 NEXT INEW
1888 NEXT JJJ
1890 IF M>-55 THEN 1916 ELSE 1999
1916 PRINT JJJJ,M,PP1
1917 PRINT A(1),A(2),A(3),A(4),A(5)
1918 PRINT A(6),A(7),A(8),A(9),A(10)
1920 PRINT A(11),A(12)
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the candidate solutions produced from JJJJ=-32000 through JJJJ=-31994 (in compressed form and to be interpreted in accordance with line 1916 through line 1920; copied manually from the computer monitor) are presented below.
-32000 -4 4
2 0 3 1 3
0 3 0 1 1
2 0
-31999 -6 6
1 3 2 0 2
1 2 3 0 0
3 1
-31998 -4 4
2 1 2 3 2
0 2 0 3 3
1 0
-31997 -6 6
1 2 3 3 2
1 3 0 0 0
2 1
-31996 -6 6
2 1 3 3 1
2 3 0 0 0
1 2
-31995 -5 5
2 3 0 0 2
0 2 1 1 1
3 3
-31994 -4 4
2 0 3 1 3
0 3 0 1 1
2 0

Among the candidate solutions presented above, the best are at JJJJ=-32000, -31998, and -31994 with an objective function value of 4.
The output above was produced in less than one minute on a personal computer with an Intel 2.66 GHz. chip and the IBM interpreter, which is slower than the corresponding compiler.
References
[1] R.C. Carlson, G.L. Nemhauser, Scheduling to minimize interaction cost, Operations Research, 14 (1966) 52-58.
[2] S.S. Heragu, A. Kusiak, Efficient models for the facility layout problem, European Journal of Operational Research 53 (1991) 1-13.
[3] S.S. Heragu, Recent models and techniques for solving the layout problem, European Journal of Operational Research 57 (1992) 136-144.
[4] F.S. Hillier, Quantitative tools for plant layout analysis, J. Indust. Eng. 14 (1963) 33-44.
[5] C.E. Nugent, T.E. Vollmann, J. Ruml, An experimental comparison of techniques for the assignment of facilities to locations, Operations Research 16 (1968) 150-173.
[6] W.C. Conley, Optimization: A Simplified Approach, Petrocelli, Princeton, New Jersey, 1981.

A General Integer Programming Computer Program Applied to a Scheduling Problem

Jsun Yui Wong
This paper is concerned with the Carlson and Nemhauser problem of scheduling to minimize interaction cost [1]. The computer program listed below uses in line 561 through line 575 the mathematical formulation appearing on page 6 of Heragu and Kusiak [2] and on page 140 of Heragu [3]; it attempts to minimize the total interaction cost of assigning six courses to two time periods, period 0 and period 1. The total interaction cost is the sum of the individual interaction costs. An individual interaction cost occurs when, for example, a student wants to take two courses scheduled during the same time period. For these individual interaction costs, the BASIC computer program below uses the interdepartmental flows of Nugent, Vollmann, and Ruml [4, p. 168]; these flows are used in line 1238 through line 1247 below.
The following computer program benefits from the computer programs of the present blog and the computer program on pages 229-232 of Conley [5].
2 DEFINT I,J,K
5 DIM B(99),N(99),A(99),H(99),L(99),U(99),X(1111),D(111),P(222)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
44 FOR IO=1 TO 6
45 B(IO)=0
46 NEXT IO
51 FOR IOCTT=1 TO 6
53 N(IOCTT)=1
57 NEXT IOCTT
61 FOR KLQ=1 TO 6
62 A(KLQ)=B(KLQ)+RND*(N(KLQ)-B(KLQ))
63 NEXT KLQ
71 FOR KLR=1 TO 6
72 H(KLR)=3
73 NEXT KLR
88 FOR JJJ=1 TO 1000 STEP 10
90 FOR INEW=1 TO 2
94 FOR J=INEW*2 TO 0 STEP -1
102 FOR JJ=0 TO 6
128 FOR I=1 TO 1
129 FOR KKQQ=1 TO 6
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
132 FOR K=1 TO 6
133 IF RND<=.5 THEN 298 ELSE 230
230 IF A(K)-(N(K)-B(K))/H(K)^J250 L(K)=B(K)
255 GOTO 265
260 L(K)=A(K)-(N(K)-B(K))/H(K)^J
265 IF A(K)+(N(K)-B(K))/H(K)^J>N(K) THEN 266 ELSE 268
266 U(K)=N(K)-L(K)
267 GOTO 272
268 U(K)=A(K)+(N(K)-B(K))/H(K)^J-L(K)
272 GOTO 300
298 X(K)=A(K)+2*RND*(2*RND-1)*(1/(1+RND*JJJ))*.05*A(K)
299 GOTO 302
300 X(K)=(L(K)+2*RND*RND*U(K))
302 NEXT K
304 X(JJ)=A(JJ)
306 KLPS=FIX(1+RND*18)
307 FOR KLA1=1 TO KLPS
308 KLA2=FIX(1+6*RND)
309 X(KLA2)=A(KLA2)
310 NEXT KLA1
343 IF RND>.1 GOTO 361
352 IF RND<=.9 THEN 353 ELSE 355
353 X(JJ)=B(JJ)
354 GOTO 361
355 X(JJ)=N(JJ)
361 FOR I222=1 TO 6
364 X(I222)=FIX(X(I222))
368 NEXT I222
461 IF RND>.1 GOTO 561
465 IF RND<5 THEN 471 ELSE IF RND<2/3 THEN 491 ELSE 521
471 IOCT1=1+FIX(RND*6)
474 IOCT2=1+FIX(RND*6)
477 X(IOCT1)=A(IOCT2)
480 X(IOCT2)=A(IOCT1)
561 P(11)=ABS(X(1)-X(2))-.5
562 P(12)=ABS(X(1)-X(3))-.5
563 P(13)=ABS(X(1)-X(4))-.5
564 P(14)=ABS(X(1)-X(5))-.5
565 P(15)=ABS(X(1)-X(6))-.5
566 P(16)=ABS(X(2)-X(3))-.5
567 P(17)=ABS(X(2)-X(4))-.5
568 P(18)=ABS(X(2)-X(5))-.5
569 P(19)=ABS(X(2)-X(6))-.5
570 P(20)=ABS(X(3)-X(4))-.5
571 P(21)=ABS(X(3)-X(5))-.5
572 P(22)=ABS(X(3)-X(6))-.5
573 P(23)=ABS(X(4)-X(5))-.5
574 P(24)=ABS(X(4)-X(6))-.5
575 P(25)=ABS(X(5)-X(6))-.5
788 FOR INSI=11 TO 25
792 IF P(INSI)<0 THEN P(INSI)=1 ELSE P(INSI)=0
795 NEXT INSI
1238 P11B=5*P(11)+2*P(12)+4*P(13)+1*P(14)+0*P(15)
1240 P13B=3*P(16)+0*P(17)+2*P(18)+2*P(19)
1243 P15B=0*P(20)+0*P(21)+0*P(22)
1245 P17B=5*P(23)+2*P(24)
1247 P19B=10*P(25)
1445 P1=P11B+P13B+P15B+P17B+P19B
1447 P2=0
1448 P3=P1+P2
1450 P=-P3+PS1
1451 IF P<=M THEN 1670
1452 M=P
1453 PP1=P3
1454 FOR KLX=1 TO 6
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1457 GOTO 128
1670 NEXT I
1702 NEXT JJ
1706 NEXT J
1777 NEXT INEW
1888 NEXT JJJ
1890 IF M>-55 THEN 1916 ELSE 1999
1916 PRINT JJJJ,M,PP1
1917 PRINT A(1),A(2),A(3),A(4),A(5),A(6)
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the candidate solutions produced from JJJJ=-32000 through JJJJ=-31995 (in compressed form and to be interpreted in accordance with line 1916 through line 1917; copied manually from the computer monitor) are presented below.
-32000 -7 7
1 0 1 0 1
0
-31999 -7 7
1 0 1 0 1
0
-31998 -7 7
1 0 1 0 1
0
-31997 -7 7
1 0 1 0 1
0
-31996 -7 7
1 0 1 0 1
0
-31995 -7 7
0 1 0 1 0
1
Each of the six candidate solutions shown above has the objective function value of 7.
(For this example, one ignores a candidate solution vector if any of its elements is not 0 or 1.)
The output above was produced in one minute on a personal computer with an Intel 2.66 GHz. chip and the IBM interpreter, which is slower than the corresponding compiler.
References
[1] R.C. Carlson, G.L. Nemhauser, Scheduling to minimize interaction cost, Operations Research 14 (1966) 52-58.
[2] S.S. Heragu, A. Kusiak, Efficient models for the facility layut problem, European Journal of Operational Research 53 (1991) 1-13.
[3] S.S. Heragu, Recent models and techniques for solving the layout problem, European Journal of Operational Research 57 (1992) 136-144.
[4] C.E. Nugent, T.E. Vollmann, J. Ruml, An experimental comparison of techniques for the assignment of facilities to locations, Operations Research 16 (1968) 150-173.
[5] W. C. Conley, Optimization: A Simplified Approach, Petrocelli, Princeton, New Jersey, 1981.

A General Integer Programming Computer Program Applied to a Plant Layout Problem

Jsun Yui Wong
The problem considered is the 12-department problem considered by Hillier [1] and by Nugent, Vollmann, and Ruml [2]. In line 561 through line 626 the computer program listed below uses the mathematical formulation appearing on page 6 of Heragu and Kusiak [3] and on page 140 of Heragu [4]. The plant shape is 3 by 4. The locations and the interdepartmental flows are given in Hillier [1] and Nugent et al. [2]. These flows are used in line 1321 through line 1374 of the computer program below.
The following computer program benefits from the computer programs of the present blog and the computer program of Conley [5, pp. 229-232].
2 DEFINT I,J,K
5 DIM B(99),N(99),A(99),H(99),L(99),U(99),X(1111),D(111),P(222)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
43 FOR IOC=1 TO 24
45 B(IOC)=0
47 NEXT IOC
51 FOR IOCTT=1 TO 24
53 N(IOCTT)=5
57 NEXT IOCTT
61 FOR KLQ=1 TO 24
62 A(KLQ)=B(KLQ)+RND*(N(KLQ)-B(KLQ))
63 NEXT KLQ
71 FOR KLR=1 TO 24
72 H(KLR)=3
73 NEXT KLR
88 FOR JJJ=1 TO 1000 STEP 10
90 FOR INEW=1 TO 8
94 FOR J=INEW*2 TO 0 STEP -1
102 FOR JJ=0 TO 24
128 FOR I=1 TO 1
129 FOR KKQQ=1 TO 24
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
132 FOR K=1 TO 24
133 IF RND<=.5 THEN 298 ELSE 230
230 IF A(K)-(N(K)-B(K))/H(K)^J250 L(K)=B(K)
255 GOTO 265
260 L(K)=A(K)-(N(K)-B(K))/H(K)^J
265 IF A(K)+(N(K)-B(K))/H(K)^J>N(K) THEN 266 ELSE 268
266 U(K)=N(K)-L(K)
267 GOTO 272
268 U(K)=A(K)+(N(K)-B(K))/H(K)^J-L(K)
272 GOTO 300
298 X(K)=A(K)+2*RND*(2*RND-1)*(1/(1+RND*JJJ))*.05*A(K)
299 GOTO 302
300 X(K)=(L(K)+2*RND*RND*U(K))
302 NEXT K
304 X(JJ)=A(JJ)
306 KLPS=FIX(1+RND*72)
307 FOR KLA1=1 TO KLPS
308 KLA2=FIX(1+24*RND)
309 X(KLA2)=A(KLA2)
310 NEXT KLA1
343 IF RND>.1 GOTO 361
352 IF RND<=.9 THEN 353 ELSE 355
353 X(JJ)=B(JJ)
354 GOTO 361
355 X(JJ)=N(JJ)
361 FOR I222=1 TO 24
364 X(I222)=FIX(X(I222))
368 NEXT I222
461 IF RND>.1 GOTO 561
465 IF RND<.5 THEN 471 ELSE 491
471 IOCT1=1+FIX(RND*12)
474 IOCT2=1+FIX(RND*12)
477 X(IOCT1)=A(IOCT2)
480 X(IOCT2)=A(IOCT1)
481 GOTO 561
491 IOCT6=13+FIX(RND*12)
494 IOCT7=13+FIX(RND*12)
497 X(IOCT6)=A(IOCT7)
500 X(IOCT7)=A(IOCT6)
561 P(11)=ABS(X(1)-X(2))+ABS(X(13)-X(14))-1
562 P(12)=ABS(X(1)-X(3))+ABS(X(13)-X(15))-1
563 P(13)=ABS(X(1)-X(4))+ABS(X(13)-X(16))-1
564 P(14)=ABS(X(1)-X(5))+ABS(X(13)-X(17))-1
565 P(15)=ABS(X(1)-X(6))+ABS(X(13)-X(18))-1
566 P(16)=ABS(X(1)-X(7))+ABS(X(13)-X(19))-1
567 P(17)=ABS(X(1)-X(8))+ABS(X(13)-X(20))-1
568 P(18)=ABS(X(1)-X(9))+ABS(X(13)-X(21))-1
569 P(19)=ABS(X(1)-X(10))+ABS(X(13)-X(22))-1
570 P(20)=ABS(X(1)-X(11))+ABS(X(13)-X(23))-1
571 P(21)=ABS(X(1)-X(12))+ABS(X(13)-X(24))-1
572 P(22)=ABS(X(2)-X(3))+ABS(X(14)-X(15))-1
573 P(23)=ABS(X(2)-X(4))+ABS(X(14)-X(16))-1
574 P(24)=ABS(X(2)-X(5))+ABS(X(14)-X(17))-1
575 P(25)=ABS(X(2)-X(6))+ABS(X(14)-X(18))-1
576 P(26)=ABS(X(2)-X(7))+ABS(X(14)-X(19))-1
577 P(27)=ABS(X(2)-X(8))+ABS(X(14)-X(20))-1
578 P(28)=ABS(X(2)-X(9))+ABS(X(14)-X(21))-1
579 P(29)=ABS(X(2)-X(10))+ABS(X(14)-X(22))-1
580 P(30)=ABS(X(2)-X(11))+ABS(X(14)-X(23))-1
581 P(31)=ABS(X(2)-X(12))+ABS(X(14)-X(24))-1
582 P(32)=ABS(X(3)-X(4))+ABS(X(15)-X(16))-1
583 P(33)=ABS(X(3)-X(5))+ABS(X(15)-X(17))-1
584 P(34)=ABS(X(3)-X(6))+ABS(X(15)-X(18))-1
585 P(35)=ABS(X(3)-X(7))+ABS(X(15)-X(19))-1
586 P(36)=ABS(X(3)-X(8))+ABS(X(15)-X(20))-1
587 P(37)=ABS(X(3)-X(9))+ABS(X(15)-X(21))-1
588 P(38)=ABS(X(3)-X(10))+ABS(X(15)-X(22))-1
589 P(39)=ABS(X(3)-X(11))+ABS(X(15)-X(23))-1
590 P(40)=ABS(X(3)-X(12))+ABS(X(15)-X(24))-1
591 P(41)=ABS(X(4)-X(5))+ABS(X(16)-X(17))-1
592 P(42)=ABS(X(4)-X(6))+ABS(X(16)-X(18))-1
593 P(43)=ABS(X(4)-X(7))+ABS(X(16)-X(19))-1
594 P(44)=ABS(X(4)-X(8))+ABS(X(16)-X(20))-1
595 P(45)=ABS(X(4)-X(9))+ABS(X(16)-X(21))-1
596 P(46)=ABS(X(4)-X(10))+ABS(X(16)-X(22))-1
597 P(47)=ABS(X(4)-X(11))+ABS(X(16)-X(23))-1
598 P(48)=ABS(X(4)-X(12))+ABS(X(16)-X(24))-1
599 P(49)=ABS(X(5)-X(6))+ABS(X(17)-X(18))-1
600 P(50)=ABS(X(5)-X(7))+ABS(X(17)-X(19))-1
601 P(51)=ABS(X(5)-X(8))+ABS(X(17)-X(20))-1
602 P(52)=ABS(X(5)-X(9))+ABS(X(17)-X(21))-1
603 P(53)=ABS(X(5)-X(10))+ABS(X(17)-X(22))-1
604 P(54)=ABS(X(5)-X(11))+ABS(X(17)-X(23))-1
605 P(55)=ABS(X(5)-X(12))+ABS(X(17)-X(24))-1
606 P(56)=ABS(X(6)-X(7))+ABS(X(18)-X(19))-1
607 P(57)=ABS(X(6)-X(8))+ABS(X(18)-X(20))-1
608 P(58)=ABS(X(6)-X(9))+ABS(X(18)-X(21))-1
609 P(59)=ABS(X(6)-X(10))+ABS(X(18)-X(22))-1
610 P(60)=ABS(X(6)-X(11))+ABS(X(18)-X(23))-1
611 P(61)=ABS(X(6)-X(12))+ABS(X(18)-X(24))-1
612 P(62)=ABS(X(7)-X(8))+ABS(X(19)-X(20))-1
613 P(63)=ABS(X(7)-X(9))+ABS(X(19)-X(21))-1
614 P(64)=ABS(X(7)-X(10))+ABS(X(19)-X(22))-1
615 P(65)=ABS(X(7)-X(11))+ABS(X(19)-X(23))-1
616 P(66)=ABS(X(7)-X(12))+ABS(X(19)-X(24))-1
617 P(67)=ABS(X(8)-X(9))+ABS(X(20)-X(21))-1
618 P(68)=ABS(X(8)-X(10))+ABS(X(20)-X(22))-1
619 P(69)=ABS(X(8)-X(11))+ABS(X(20)-X(23))-1
620 P(70)=ABS(X(8)-X(12))+ABS(X(20)-X(24))-1
621 P(71)=ABS(X(9)-X(10))+ABS(X(21)-X(22))-1
622 P(72)=ABS(X(9)-X(11))+ABS(X(21)-X(23))-1
623 P(73)=ABS(X(9)-X(12))+ABS(X(21)-X(24))-1
624 P(74)=ABS(X(10)-X(11))+ABS(X(22)-X(23))-1
625 P(75)=ABS(X(10)-X(12))+ABS(X(22)-X(24))-1
626 P(76)=ABS(X(11)-X(12))+ABS(X(23)-X(24))-1
788 FOR INSI=11 TO 76
791 IF P(INSI)<0 THEN P(INSI)=P(INSI) ELSE P(INSI)=0
795 NEXT INSI
1111 PSUM=0
1115 FOR IOCT=11 TO 76
1118 PSUM=PSUM+P(IOCT)
1121 NEXT IOCT
1131 PS1=99*555555!*PSUM
1321 P11B=5*ABS(X(1)-X(2))+2*ABS(X(1)-X(3))+4*ABS(X(1)-X(4))+1*ABS(X(1)-X(5))+0*ABS(X(1)-X(6))
1322 P12B=0*ABS(X(1)-X(7))+6*ABS(X(1)-X(8))+2*ABS(X(1)-X(9))+1*ABS(X(1)-X(10))+1*ABS(X(1)-X(11))+1*ABS(X(1)-X(12))
1323 P13B=3*ABS(X(2)-X(3))+0*ABS(X(2)-X(4))+2*ABS(X(2)-X(5))+2*ABS(X(2)-X(6))+2*ABS(X(2)-X(7))
1324 P14B=0*ABS(X(2)-X(8))+4*ABS(X(2)-X(9))+5*ABS(X(2)-X(10))+0*ABS(X(2)-X(11))+0*ABS(X(2)-X(12))
1325 P15B=0*ABS(X(3)-X(4))+0*ABS(X(3)-X(5))+0*ABS(X(3)-X(6))+0*ABS(X(3)-X(7))+5*ABS(X(3)-X(8))
1326 P16B=5*ABS(X(3)-X(9))+2*ABS(X(3)-X(10))+2*ABS(X(3)-X(11))+2*ABS(X(3)-X(12))
1327 P17B=5*ABS(X(4)-X(5))+2*ABS(X(4)-X(6))+2*ABS(X(4)-X(7))+10*ABS(X(4)-X(8))+0*ABS(X(4)-X(9))+0*ABS(X(4)-X(10))+5*ABS(X(4)-X(11))+5*ABS(X(4)-X(12))
1328 P18B=10*ABS(X(5)-X(6))+0*ABS(X(5)-X(7))+0*ABS(X(5)-X(8))+0*ABS(X(5)-X(9))+5*ABS(X(5)-X(10))+1*ABS(X(5)-X(11))+1*ABS(X(5)-X(12))
1329 P19B=5*ABS(X(6)-X(7))+1*ABS(X(6)-X(8))+1*ABS(X(6)-X(9))+5*ABS(X(6)-X(10))+4*ABS(X(6)-X(11))+0*ABS(X(6)-X(12))
1330 P20B=10*ABS(X(7)-X(8))+5*ABS(X(7)-X(9))+2*ABS(X(7)-X(10))+3*ABS(X(7)-X(11))+3*ABS(X(7)-X(12))
1331 P21B=0*ABS(X(8)-X(9))+0*ABS(X(8)-X(10))+5*ABS(X(8)-X(11))+0*ABS(X(8)-X(12))
1332 P22B=0*ABS(X(9)-X(10))+10*ABS(X(9)-X(11))+10*ABS(X(9)-X(12))
1333 P23B=5*ABS(X(10)-X(11))+0*ABS(X(10)-X(12))
1334 P24B=2*ABS(X(11)-X(12))
1351 P25B=5*ABS(X(13)-X(14))+2*ABS(X(13)-X(15))+4*ABS(X(13)-X(16))+1*ABS(X(13)-X(17))+0*ABS(X(13)-X(18))
1352 P26B=0*ABS(X(13)-X(19))+6*ABS(X(13)-X(20))+2*ABS(X(13)-X(21))+1*ABS(X(13)-X(22))+1*ABS(X(13)-X(23))+1*ABS(X(13)-X(24))
1353 P27B=3*ABS(X(14)-X(15))+0*ABS(X(14)-X(16))+2*ABS(X(14)-X(17))+2*ABS(X(14)-X(18))+2*ABS(X(14)-X(19))
1354 P28B=0*ABS(X(14)-X(20))+4*ABS(X(14)-X(21))+5*ABS(X(14)-X(22))+0*ABS(X(14)-X(23))+0*ABS(X(14)-X(24))
1355 P29B=0*ABS(X(15)-X(16))+0*ABS(X(15)-X(17))+0*ABS(X(15)-X(18))+0*ABS(X(15)-X(19))+5*ABS(X(15)-X(20))
1356 P30B=5*ABS(X(15)-X(21))+2*ABS(X(15)-X(22))+2*ABS(X(15)-X(23))+2*ABS(X(15)-X(24))
1367 P31B=5*ABS(X(16)-X(17))+2*ABS(X(16)-X(18))+2*ABS(X(16)-X(19))+10*ABS(X(16)-X(20))+0*ABS(X(16)-X(21))+0*ABS(X(16)-X(22))+5*ABS(X(16)-X(23))+5*ABS(X(16)-X(24))
1368 P32B=10*ABS(X(17)-X(18))+0*ABS(X(17)-X(19))+0*ABS(X(17)-X(20))+0*ABS(X(17)-X(21))+5*ABS(X(17)-X(22))+1*ABS(X(17)-X(23))+1*ABS(X(17)-X(24))
1369 P33B=5*ABS(X(18)-X(19))+1*ABS(X(18)-X(20))+1*ABS(X(18)-X(21))+5*ABS(X(18)-X(22))+4*ABS(X(18)-X(23))+0*ABS(X(18)-X(24))
1370 P34B=10*ABS(X(19)-X(20))+5*ABS(X(19)-X(21))+2*ABS(X(19)-X(22))+3*ABS(X(19)-X(23))+3*ABS(X(19)-X(24))
1371 P35B=0*ABS(X(20)-X(21))+0*ABS(X(20)-X(22))+5*ABS(X(20)-X(23))+0*ABS(X(20)-X(24))
1372 P36B=0*ABS(X(21)-X(22))+10*ABS(X(21)-X(23))+10*ABS(X(21)-X(24))
1373 P37B=5*ABS(X(22)-X(23))+0*ABS(X(22)-X(24))
1374 P38B=2*ABS(X(23)-X(24))
1443 P1=P11B+P12B+P13B+P14B+P15B+P16B+P17B+P18B+P19B+P20B
1444 P2=P21B+P22B+P23B+P24B+P25B+P26B+P27B+P28B+P29B+P30B
1445 P3=P31B+P32B+P33B+P34B+P35B+P36B+P37B+P38B
1448 P4=P1+P2+P3
1450 P=-P4+PS1
1451 IF P<=M THEN 1670
1452 M=P
1453 PP1=P4
1454 FOR KLX=1 TO 24
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1457 GOTO 128
1670 NEXT I
1702 NEXT JJ
1706 NEXT J
1777 NEXT INEW
1888 NEXT JJJ
1890 IF M>-300 THEN 1916 ELSE 1999
1916 PRINT JJJJ,M,PP1
1917 PRINT A(1),A(2),A(3),A(4),A(5)
1918 PRINT A(6),A(7),A(8),A(9),A(10)
1920 PRINT A(11),A(12)
1922 PRINT A(13),A(14),A(15),A(16),A(17)
1924 PRINT A(18),A(19),A(20),A(21),A(22)
1926 PRINT A(23),A(24)
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and its output through JJJJ=-31968 (in compressed form and to be interpreted in accordance with line 1916 through line 1926; copied manually from the computer monitor) is presented below.
-31985 -295 295
0 2 2 0 2
1 1 0 1 2
1 0
1 1 0 3 3
3 2 2 0 2
1 0
-31974 -295 -295
0 0 0 3 3
2 2 2 1 1
1 1
1 0 2 1 0
0 2 1 2 0
1 3
-31968 -289 289
3 3 3 0 0
1 1 1 2 2
2 0
1 2 0 1 2
2 0 1 0 2
1 0
The best candidate solution above is at JJJJ=-31968 with the objective function value of 289.
The output above was obtained in 2.6 hours on a personal computer with an Intel 2.66 GHz. chip and the IBM interpreter, which is slower than the corresponding compiler.
References
[1] F.S. Hillier, Quantitative tools for plant layout analysis, J. Indust. Eng. 14 (1963) 33-40.
[2] C.E. Nugent, T.E. Vollmann, J. Ruml, An experimental comparison of techniques for the assignment of facilities to locations, Operations Research 16 (1968) 150-173.
[3] S.S. Heragu, A. Kusiak, Efficient models for the facility layut problem, European Journal of Operational Research 53 (1991) 1-13.
[4] S.S. Heragu, Recent models and techniques for solving the layout problem, European Journal of Operational Research 57 (1992) 136-144.

[5] W.C. Conley, Optimization: A Simplified Approach, Petrocelli, Princeton, New Jersey, 1981.

A General Integer Programming Computer Program Applied to a 20-Facility Space Allocation Problem

Jsun Yui Wong
The problem considered is problem 7 of Heragu and Kusiak [3, p. 9]. The computer program listed below follows the mathematical formulation appearing on their page 4 [3] and on page 139 of Heragu [4]. The lengths of the twenty facilities are from their page 9 [3] and are used in line 561 through line 750 of the computer program below; the inter-facility flows are from Nugent et al. [5, p. 169] and are used in line 1238 through line 1317 of the computer program below.
The following computer program benefits from the computer programs of the present blog and the computer program of Conley [2, pp. 229-232].
2 DEFINT I,J,K
5 DIM B(99),N(99),A(99),H(99),L(99),U(99),X(1111),D(111),P(222)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
25 B(1)=0:B(2)=0:B(3)=0:B(4)=0:B(5)=0:B(6)=0
26 B(7)=0:B(8)=0:B(9)=0:B(10)=0:B(11)=0
27 B(12)=0:B(13)=0:B(14)=0:B(15)=0
31 B(16)=0:B(17)=0:B(18)=0:B(19)=0:B(20)=0
37 N(1)=99200!:N(2)=99200!:N(3)=99200!:N(4)=99200!:N(5)=99200!:N(6)=99200!
38 N(7)=99200!:N(8)=99200!:N(9)=99200!:N(10)=99200!:N(11)=92900!
39 N(12)=99200!:N(13)=99200!:N(14)=99200!:N(15)=99200!
41 N(16)=99200!:N(17)=99200!:N(18)=99200!:N(19)=99200!:N(20)=92900!
43 GOTO 61
51 FOR IOCTT=1 TO 20
53 N(IOCTT)=999999!
57 NEXT IOCTT
61 FOR KLQ=1 TO 20
62 A(KLQ)=B(KLQ)+RND*(N(KLQ)-B(KLQ))
63 NEXT KLQ
71 FOR KLR=1 TO 20
72 H(KLR)=3
73 NEXT KLR
88 FOR JJJ=1 TO 1000 STEP 10
90 FOR INEW=1 TO 13
94 FOR J=INEW*2 TO 0 STEP -1
102 FOR JJ=0 TO 20
111 REM
128 FOR I=1 TO 2
129 FOR KKQQ=1 TO 20
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
132 FOR K=1 TO 20
133 IF RND<=.5 THEN 298 ELSE 230
230 IF A(K)-(N(K)-B(K))/H(K)^J250 L(K)=B(K)
255 GOTO 265
260 L(K)=A(K)-(N(K)-B(K))/H(K)^J
265 IF A(K)+(N(K)-B(K))/H(K)^J>N(K) THEN 266 ELSE 268
266 U(K)=N(K)-L(K)
267 GOTO 272
268 U(K)=A(K)+(N(K)-B(K))/H(K)^J-L(K)
272 GOTO 300
298 X(K)=A(K)+2*RND*(2*RND-1)*(1/(1+RND*JJJ))*.05*A(K)
299 GOTO 302
300 X(K)=(L(K)+2*RND*RND*U(K))
302 NEXT K
304 X(JJ)=A(JJ)
305 REM
306 KLPS=FIX(1+RND*60)
307 FOR KLA1=1 TO KLPS
308 KLA2=FIX(1+20*RND)
309 X(KLA2)=A(KLA2)
310 NEXT KLA1
343 IF RND>.1 GOTO 461
352 IF RND<=.9 THEN 353 ELSE 355
353 X(JJ)=B(JJ)
354 GOTO 461
355 X(JJ)=N(JJ)
461 IF RND>.1 GOTO 561
471 IOCT1=1+FIX(RND*20)
474 IOCT2=1+FIX(RND*20)
477 X(IOCT1)=A(IOCT2)
480 X(IOCT2)=A(IOCT1)
561 P(11)=ABS(X(1)-X(2))-11.5
562 P(12)=ABS(X(1)-X(3))-14.5
563 P(13)=ABS(X(1)-X(4))-11.5
564 P(14)=ABS(X(1)-X(5))-13.5
565 P(15)=ABS(X(1)-X(6))-11.5
566 P(16)=ABS(X(1)-X(7))-13.5
567 P(17)=ABS(X(1)-X(8))-12.5
568 P(18)=ABS(X(1)-X(9))-14.5
569 P(19)=ABS(X(1)-X(10))-13
570 P(20)=ABS(X(1)-X(11))-12.5
571 P(21)=ABS(X(1)-X(12))-11.5
572 P(22)=ABS(X(1)-X(13))-14.5
573 P(23)=ABS(X(1)-X(14))-11.5
574 P(24)=ABS(X(1)-X(15))-13.5
575 P(25)=ABS(X(1)-X(16))-11.5
576 P(26)=ABS(X(1)-X(17))-13.5
577 P(27)=ABS(X(1)-X(18))-12.5
578 P(28)=ABS(X(1)-X(19))-14.5
579 P(29)=ABS(X(1)-X(20))-13
580 P(30)=ABS(X(2)-X(3))-6
581 P(31)=ABS(X(2)-X(4))-3
582 P(32)=ABS(X(2)-X(5))-5
583 P(33)=ABS(X(2)-X(6))-3
584 P(34)=ABS(X(2)-X(7))-5
585 P(35)=ABS(X(2)-X(8))-4
586 P(36)=ABS(X(2)-X(9))-6
587 P(37)=ABS(X(2)-X(10))-4.5
588 P(38)=ABS(X(2)-X(11))-4
589 P(39)=ABS(X(2)-X(12))-3
590 P(40)=ABS(X(2)-X(13))-6
591 P(41)=ABS(X(2)-X(14))-3
592 P(42)=ABS(X(2)-X(15))-5
593 P(43)=ABS(X(2)-X(16))-3
594 P(44)=ABS(X(2)-X(17))-5
595 P(45)=ABS(X(2)-X(18))-4
596 P(46)=ABS(X(2)-X(19))-6
597 P(47)=ABS(X(2)-X(20))-4.5
598 P(48)=ABS(X(3)-X(4))-6
599 P(49)=ABS(X(3)-X(5))-8
600 P(50)=ABS(X(3)-X(6))-6
601 P(51)=ABS(X(3)-X(7))-8
602 P(52)=ABS(X(3)-X(8))-7
603 P(53)=ABS(X(3)-X(9))-9
604 P(54)=ABS(X(3)-X(10))-7.5
605 P(55)=ABS(X(3)-X(11))-7
606 P(56)=ABS(X(3)-X(12))-6
607 P(57)=ABS(X(3)-X(13))-9
608 P(58)=ABS(X(3)-X(14))-6
609 P(59)=ABS(X(3)-X(15))-8
610 P(60)=ABS(X(3)-X(16))-6
611 P(61)=ABS(X(3)-X(17))-8
612 P(62)=ABS(X(3)-X(18))-7
613 P(63)=ABS(X(3)-X(19))-9
614 P(64)=ABS(X(3)-X(20))-7.5
615 P(65)=ABS(X(4)-X(5))-5
616 P(66)=ABS(X(4)-X(6))-3
617 P(67)=ABS(X(4)-X(7))-5
618 P(68)=ABS(X(4)-X(8))-4
619 P(69)=ABS(X(4)-X(9))-6
620 P(70)=ABS(X(4)-X(10))-4.5
621 P(71)=ABS(X(4)-X(11))-4
622 P(72)=ABS(X(4)-X(12))-3
623 P(73)=ABS(X(4)-X(13))-6
624 P(74)=ABS(X(4)-X(14))-3
625 P(75)=ABS(X(4)-X(15))-5
626 P(76)=ABS(X(4)-X(16))-3
627 P(77)=ABS(X(4)-X(17))-5
628 P(78)=ABS(X(4)-X(18))-4
629 P(79)=ABS(X(4)-X(19))-6
630 P(80)=ABS(X(4)-X(20))-4.5
631 P(81)=ABS(X(5)-X(6))-5
632 P(82)=ABS(X(5)-X(7))-7
633 P(83)=ABS(X(5)-X(8))-6
634 P(84)=ABS(X(5)-X(9))-8
635 P(85)=ABS(X(5)-X(10))-6.5
636 P(86)=ABS(X(5)-X(11))-6
637 P(87)=ABS(X(5)-X(12))-5
638 P(88)=ABS(X(5)-X(13))-8
639 P(89)=ABS(X(5)-X(14))-5
640 P(90)=ABS(X(5)-X(15))-7
641 P(91)=ABS(X(5)-X(16))-5
642 P(92)=ABS(X(5)-X(17))-7
643 P(93)=ABS(X(5)-X(18))-6
644 P(94)=ABS(X(5)-X(19))-8
645 P(95)=ABS(X(5)-X(20))-6.5
646 P(96)=ABS(X(6)-X(7))-5
647 P(97)=ABS(X(6)-X(8))-4
648 P(98)=ABS(X(6)-X(9))-6
649 P(99)=ABS(X(6)-X(10))-4.5
650 P(100)=ABS(X(6)-X(11))-4
651 P(101)=ABS(X(6)-X(12))-3
652 P(102)=ABS(X(6)-X(13))-6
653 P(103)=ABS(X(6)-X(14))-3
654 P(104)=ABS(X(6)-X(15))-5
655 P(105)=ABS(X(6)-X(16))-3
656 P(106)=ABS(X(6)-X(17))-5
657 P(107)=ABS(X(6)-X(18))-4
658 P(108)=ABS(X(6)-X(19))-6
659 P(109)=ABS(X(6)-X(20))-4.5
660 P(110)=ABS(X(7)-X(8))-6
661 P(111)=ABS(X(7)-X(9))-8
662 P(112)=ABS(X(7)-X(10))-6.5
663 P(113)=ABS(X(7)-X(11))-6
664 P(114)=ABS(X(7)-X(12))-5
665 P(115)=ABS(X(7)-X(13))-8
666 P(116)=ABS(X(7)-X(14))-5
667 P(117)=ABS(X(7)-X(15))-7
668 P(118)=ABS(X(7)-X(16))-5
669 P(119)=ABS(X(7)-X(17))-7
670 P(120)=ABS(X(7)-X(18))-6
671 P(121)=ABS(X(7)-X(19))-8
672 P(122)=ABS(X(7)-X(20))-6.5
673 P(123)=ABS(X(8)-X(9))-7
674 P(124)=ABS(X(8)-X(10))-5.5
675 P(125)=ABS(X(8)-X(11))-5
676 P(126)=ABS(X(8)-X(12))-4
677 P(127)=ABS(X(8)-X(13))-7
678 P(128)=ABS(X(8)-X(14))-4
679 P(129)=ABS(X(8)-X(15))-6
680 P(130)=ABS(X(8)-X(16))-4
681 P(131)=ABS(X(8)-X(17))-6
682 P(132)=ABS(X(8)-X(18))-5
683 P(133)=ABS(X(8)-X(19))-7
684 P(134)=ABS(X(8)-X(20))-5.5
685 P(135)=ABS(X(9)-X(10))-7.5
686 P(136)=ABS(X(9)-X(11))-7
687 P(137)=ABS(X(9)-X(12))-6
688 P(138)=ABS(X(9)-X(13))-9
689 P(139)=ABS(X(9)-X(14))-6
690 P(140)=ABS(X(9)-X(15))-8
691 P(141)=ABS(X(9)-X(16))-6
692 P(142)=ABS(X(9)-X(17))-8
693 P(143)=ABS(X(9)-X(18))-7
694 P(144)=ABS(X(9)-X(19))-9
695 P(145)=ABS(X(9)-X(20))-7.5
696 P(146)=ABS(X(10)-X(11))-5.5
697 P(147)=ABS(X(10)-X(12))-4.5
698 P(148)=ABS(X(10)-X(13))-7.5
699 P(149)=ABS(X(10)-X(14))-4.5
700 P(150)=ABS(X(10)-X(15))-6.5
701 P(151)=ABS(X(10)-X(16))-4.5
702 P(152)=ABS(X(10)-X(17))-6.5
703 P(153)=ABS(X(10)-X(18))-5.5
704 P(154)=ABS(X(10)-X(19))-7.5
705 P(155)=ABS(X(10)-X(20))-6
706 P(156)=ABS(X(11)-X(12))-4
707 P(157)=ABS(X(11)-X(13))-7
708 P(158)=ABS(X(11)-X(14))-4
709 P(159)=ABS(X(11)-X(15))-6
710 P(160)=ABS(X(11)-X(16))-4
711 P(161)=ABS(X(11)-X(17))-6
712 P(162)=ABS(X(11)-X(18))-5
713 P(163)=ABS(X(11)-X(19))-7
714 P(164)=ABS(X(11)-X(20))-5.5
715 P(165)=ABS(X(12)-X(13))-6
716 P(166)=ABS(X(12)-X(14))-3
717 P(167)=ABS(X(12)-X(15))-5
718 P(168)=ABS(X(12)-X(16))-3
719 P(169)=ABS(X(12)-X(17))-5
720 P(170)=ABS(X(12)-X(18))-4
721 P(171)=ABS(X(12)-X(19))-6
722 P(172)=ABS(X(12)-X(20))-4.5
723 P(173)=ABS(X(13)-X(14))-6
724 P(174)=ABS(X(13)-X(15))-8
725 P(175)=ABS(X(13)-X(16))-6
726 P(176)=ABS(X(13)-X(17))-8
727 P(177)=ABS(X(13)-X(18))-7
728 P(178)=ABS(X(13)-X(19))-9
729 P(179)=ABS(X(13)-X(20))-7.5
730 P(180)=ABS(X(14)-X(15))-5
731 P(181)=ABS(X(14)-X(16))-3
732 P(182)=ABS(X(14)-X(17))-5
733 P(183)=ABS(X(14)-X(18))-4
734 P(184)=ABS(X(14)-X(19))-6
735 P(185)=ABS(X(14)-X(20))-4.5
736 P(186)=ABS(X(15)-X(16))-5
737 P(187)=ABS(X(15)-X(17))-7
738 P(188)=ABS(X(15)-X(18))-6
739 P(189)=ABS(X(15)-X(19))-8
740 P(190)=ABS(X(15)-X(20))-6.5
741 P(191)=ABS(X(16)-X(17))-5
742 P(192)=ABS(X(16)-X(18))-4
743 P(193)=ABS(X(16)-X(19))-6
744 P(194)=ABS(X(16)-X(20))-4.5
745 P(195)=ABS(X(17)-X(18))-6
746 P(196)=ABS(X(17)-X(19))-8
747 P(197)=ABS(X(17)-X(20))-6.5
748 P(198)=ABS(X(18)-X(19))-7
749 P(199)=ABS(X(18)-X(20))-5.5
750 P(200)=ABS(X(19)-X(20))-7.5
788 FOR INSI=11 TO 200
791 IF P(INSI)<0 THEN P(INSI)=P(INSI) ELSE P(INSI)=0
795 NEXT INSI
1111 PSUM=0
1115 FOR IOCT=11 TO 200
1118 PSUM=PSUM+P(IOCT)
1121 NEXT IOCT
1131 PS1=99*555555!*PSUM
1238 P11B=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))
1239 P12B=5*ABS(X(1)-X(12))+0*ABS(X(1)-X(13))+0*ABS(X(1)-X(14))+5*ABS(X(1)-X(15))
1240 P13B=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))
1241 P14B=5*ABS(X(2)-X(12))+0*ABS(X(2)-X(13))+10*ABS(X(2)-X(14))+10*ABS(X(2)-X(15))
1243 P15B=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))
1244 P16B=0*ABS(X(3)-X(12))+0*ABS(X(3)-X(13))+5*ABS(X(3)-X(14))+1*ABS(X(3)-X(15))
1245 P17B=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))
1246 P18B=2*ABS(X(4)-X(12))+2*ABS(X(4)-X(13))+0*ABS(X(4)-X(14))+2*ABS(X(4)-X(15))
1248 P19B=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))
1249 P20B=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))
1250 P21B=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))
1251 P22B=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))
1255 P23B=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))
1257 P24B=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))
1258 P25B=5*ABS(X(11)-X(12))+2*ABS(X(11)-X(13))+5*ABS(X(11)-X(14))+1*ABS(X(11)-X(15))
1259 P26B=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))
1301 P27B=4*ABS(X(1)-X(16))+4*ABS(X(1)-X(17))+0*ABS(X(1)-X(18))+0*ABS(X(1)-X(18))+1*ABS(X(1)-X(20))
1302 P28B=3*ABS(X(2)-X(16))+0*ABS(X(2)-X(17))+5*ABS(X(2)-X(18))+10*ABS(X(2)-X(19))+5*ABS(X(2)-X(20))
1303 P29B=0*ABS(X(3)-X(16))+0*ABS(X(3)-X(17))+5*ABS(X(3)-X(18))+0*ABS(X(3)-X(19))+0*ABS(X(3)-X(20))
1304 P30B=1*ABS(X(4)-X(16))+5*ABS(X(4)-X(17))+2*ABS(X(4)-X(18))+5*ABS(X(4)-X(19))+5*ABS(X(4)-X(20))
1305 P31B=1*ABS(X(5)-X(16))+5*ABS(X(5)-X(17))+2*ABS(X(5)-X(18))+5*ABS(X(5)-X(19))+1*ABS(X(5)-X(20))
1306 P32B=0*ABS(X(6)-X(16))+1*ABS(X(6)-X(17))+0*ABS(X(6)-X(18))+1*ABS(X(6)-X(19))+5*ABS(X(6)-X(20))
1307 P33B=1*ABS(X(7)-X(16))+2*ABS(X(7)-X(17))+1*ABS(X(7)-X(18))+0*ABS(X(7)-X(19))+10*ABS(X(7)-X(20))
1308 P34B=2*ABS(X(8)-X(16))+5*ABS(X(8)-X(17))+2*ABS(X(8)-X(18))+2*ABS(X(8)-X(19))+10*ABS(X(8)-X(20))
1309 P35B=5*ABS(X(9)-X(16))+0*ABS(X(9)-X(17))+0*ABS(X(9)-X(18))+0*ABS(X(9)-X(19))+2*ABS(X(9)-X(20))
1310 P36B=0*ABS(X(10)-X(16))+0*ABS(X(10)-X(17))+5*ABS(X(10)-X(18))+5*ABS(X(10)-X(19))+2*ABS(X(10)-X(20))
1311 P37B=10*ABS(X(11)-X(16))+0*ABS(X(11)-X(17))+2*ABS(X(11)-X(18))+2*ABS(X(11)-X(19))+5*ABS(X(11)-X(20))
1312 P38B=0*ABS(X(12)-X(16))+1*ABS(X(12)-X(17))+1*ABS(X(12)-X(18))+2*ABS(X(12)-X(19))+5*ABS(X(12)-X(20))
1313 P39B=1*ABS(X(13)-X(16))+0*ABS(X(13)-X(17))+0*ABS(X(13)-X(18))+0*ABS(X(13)-X(19))+5*ABS(X(13)-X(20))
1314 P40B=5*ABS(X(14)-X(16))+1*ABS(X(14)-X(17))+5*ABS(X(14)-X(18))+5*ABS(X(14)-X(19))+0*ABS(X(14)-X(20))
1315 P41B=3*ABS(X(15)-X(16))+0*ABS(X(15)-X(17))+5*ABS(X(15)-X(18))+10*ABS(X(15)-X(19))+10*ABS(X(15)-X(20))
1316 P42B=0*ABS(X(16)-X(17))+0*ABS(X(16)-X(18))+2*ABS(X(16)-X(19))+0*ABS(X(16)-X(20))
1317 P43B=5*ABS(X(17)-X(18))+2*ABS(X(17)-X(19))+0*ABS(X(17)-X(20))+1*ABS(X(18)-X(19))+1*ABS(X(18)-X(20))+6*ABS(X(19)-X(20))
1445 P1=P11B+P12B+P13B+P14B+P15B+P16B+P17B+P18B+P19B+P20B+P21B+P22B+P23B+P24B+P25B+P26B
1447 P2=P27B+P28B+P29B+P30B+P31B+P32B+P33B+P34B+P35B+P36B+P37B+P38B+P39B+P40B+P41B+P42B+P43B
1448 P3=P1+P2
1449 REM
1450 P=-P3+PS1
1451 IF P<=M THEN 1670
1452 M=P
1453 PP1=P3
1454 FOR KLX=1 TO 20
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1457 GOTO 128
1670 NEXT I
1702 NEXT JJ
1706 NEXT J
1777 NEXT INEW
1778 REM PRINT JJJJ,A(1),A(2),A(3),A(4),A(5),M,PP1
1888 NEXT JJJ
1890 IF M>-16200 THEN 1916 ELSE 1999
1916 PRINT JJJJ,A(1),A(2),A(3),A(4),A(5),M,PP1
1918 PRINT A(6),A(7),A(8),A(9),A(10)
1920 PRINT A(11),A(12),A(13),A(14),A(15)
1922 PRINT A(16),A(17),A(18),A(19),A(20)
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and its best candidate solutions from JJJJ=-32000 through JJJJ=-31869 (in compressed form and to be interpreted in accordance with line 1916 through line 1922; copied manually from the computer monitor) are presented below.
-31994 31277.27 31353.78 31382.79 31342.78
31309.77 -15792.07 15792.07
31304.77 31316.77 31335.77 31391.79 31366.28
31346.78 31339.77 31298.77 31361.78 31329.77
31350.78 31290.77 31357.78 31373.79 31323.27
-31870 56521.45 56444.94 56415.94 56450.94
56491.95 -15718.27 15718.27
56486.95 56481.95 56469.95 56406.94 56437.44
56454.94 56465.95 56506.95 56441.94 56460.95
56447.94 56498.95 56422.94 56429.94 56475.45
In summary, this computer run produced candidate solutions with objective function value of 15792.07 at JJJJ=-31994, 15823 at JJJJ=-31980, 15718.27 at JJJJ=-31870, and 15993 at JJJJ=-31869.
The total time for the output above was obtained in 57 hours on a personal computer with an Intel 2.66 GHz. chip and the IBM interpreter, which is slower the corresponding compiler.
If one makes changes to the computer program above, such as a change of changing line 128 to, for example, 128 FOR I=1 TO 3, one may or may not obtain the best objective function value of the output above, 15718.27. For this problem, the optimal objective function value is 15549.0, Amaral [1]. Generally speaking, in order to increase the probability of getting an optimal solution, one preferably should run several computers simultaneously, each with a different line 128, for example; instead of line 128, another line can be chosen. This multicomputer approach can mitigate the possible danger of missed optimality and can produce a usable solution faster than just running one computer.
References
[1] A.R.S. Amaral, A new lower bound for the single row facility layout problem, Discrete Applied Mathematics, in press.
[2] W.C. Conley, Optimization: A Simplified Approach, Petrocelli, Princeton, New Jersey, 1981.
[3] S.S. Heragu, A. Kusiak, Efficient models for the facility layut problem, European Journal of Operational Research 53 (1991) 1-13.
[4] S.S. Heragu, Recent models and techniques for solving the layout problem, European Journal of Operational Research 57 (1992) 136-144.
[5] C.E. Nugent, T.E. Vollmann, J. Ruml, An experimental comparison of techniques for the assignment of facilities to locations, Operations Research 16 (1968) 150-173.
[6] D.M. Simmons, One-dimensional space allocation: An ordering algorithm, Operations Research 17 (1969) 812-826.