The specific problem used by the computer program listed here is the 11-facility layout problem in Amaral [1, p. 517] and in Heragu [4, pp. 231-232 and pp. 276-279]. This computer program benefits from the computer programs of the present blog, the computer program of Conley [3, pp. 229-232], and the mathematical formulation on page 117 of Heragu [4]. The output of the computer program listed below is also presented here.
2 DEFINT I,J,K
5 DIM B(99),N(99),A(99),H(99),L(99),U(99),X(1111),D(111),P(111)
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
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)=99200!
61 FOR KLQ=1 TO 11
62 A(KLQ)=B(KLQ)+RND*(N(KLQ)-B(KLQ))
63 NEXT KLQ
71 FOR KLR=1 TO 11
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 11
111 KKLL=FIX(1+33*RND)
128 FOR I=1 TO 1
129 FOR KKQQ=1 TO 11
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
132 FOR K=1 TO 11
133 IF RND<=.5 THEN 298 ELSE 230
230 IF A(K)-(N(K)-B(K))/H(K)^J
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 KLPS=FIX(1+KKLL*RND)
307 FOR KLA1=1 TO KLPS
308 KLA2=FIX(1+11*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*11)
474 IOCT2=1+FIX(RND*11)
477 X(IOCT1)=A(IOCT2)
480 X(IOCT2)=A(IOCT1)
561 P11=ABS(X(1)-X(2))-6
562 P12=ABS(X(1)-X(3))-3
563 P13=ABS(X(1)-X(4))-5
564 P14=ABS(X(1)-X(5))-3
565 P15=ABS(X(1)-X(6))-5
566 P16=ABS(X(1)-X(7))-4
567 P17=ABS(X(1)-X(8))-6
568 P18=ABS(X(1)-X(9))-4.5
569 P19=ABS(X(1)-X(10))-4
570 P20=ABS(X(1)-X(11))-6.5
571 P21=ABS(X(2)-X(3))-6
572 P22=ABS(X(2)-X(4))-8
573 P23=ABS(X(2)-X(5))-6
574 P24=ABS(X(2)-X(6))-8
575 P25=ABS(X(2)-X(7))-7
576 P26=ABS(X(2)-X(8))-9
577 P27=ABS(X(2)-X(9))-7.5
578 P28=ABS(X(2)-X(10))-7
579 P29=ABS(X(2)-X(11))-9.5
583 P30=ABS(X(3)-X(4))-5
584 P31=ABS(X(3)-X(5))-3
585 P32=ABS(X(3)-X(6))-5
586 P33=ABS(X(3)-X(7))-4
587 P34=ABS(X(3)-X(8))-6
588 P35=ABS(X(3)-X(9))-4.5
589 P36=ABS(X(3)-X(10))-4
590 P37=ABS(X(3)-X(11))-6.5
594 P38=ABS(X(4)-X(5))-5
595 P39=ABS(X(4)-X(6))-7
596 P40=ABS(X(4)-X(7))-6
597 P41=ABS(X(4)-X(8))-8
598 P42=ABS(X(4)-X(9))-6.5
599 P43=ABS(X(4)-X(10))-6
600 P44=ABS(X(4)-X(11))-8.5
601 P45=ABS(X(5)-X(6))-5
602 P46=ABS(X(5)-X(7))-4
603 P47=ABS(X(5)-X(8))-6
604 P48=ABS(X(5)-X(9))-4.5
605 P49=ABS(X(5)-X(10))-4
606 P50=ABS(X(5)-X(11))-6.5
607 P51=ABS(X(6)-X(7))-6
608 P52=ABS(X(6)-X(8))-8
609 P53=ABS(X(6)-X(9))-6.5
610 P54=ABS(X(6)-X(10))-6
611 P55=ABS(X(6)-X(11))-8.5
612 P56=ABS(X(7)-X(8))-7
613 P57=ABS(X(7)-X(9))-5.5
614 P58=ABS(X(7)-X(10))-5
615 P59=ABS(X(7)-X(11))-7.5
616 P60=ABS(X(8)-X(9))-7.5
617 P61=ABS(X(8)-X(10))-7
618 P62=ABS(X(8)-X(11))-9.5
619 P63=ABS(X(9)-X(10))-5.5
620 P64=ABS(X(9)-X(11))-8
621 P65=ABS(X(10)-X(11))-7.5
801 IF P11>=0 THEN P11=0 ELSE P11=P11
802 IF P12>=0 THEN P12=0 ELSE P12=P12
803 IF P13>=0 THEN P13=0 ELSE P13=P13
804 IF P14>=0 THEN P14=0 ELSE P14=P14
805 IF P15>=0 THEN P15=0 ELSE P15=P15
806 IF P16>=0 THEN P16=0 ELSE P16=P16
807 IF P17>=0 THEN P17=0 ELSE P17=P17
808 IF P18>=0 THEN P18=0 ELSE P18=P18
809 IF P19>=0 THEN P19=0 ELSE P19=P19
810 IF P20>=0 THEN P20=0 ELSE P20=P20
811 IF P21>=0 THEN P21=0 ELSE P21=P21
812 IF P22>=0 THEN P22=0 ELSE P22=P22
813 IF P23>=0 THEN P23=0 ELSE P23=P23
814 IF P24>=0 THEN P24=0 ELSE P24=P24
815 IF P25>=0 THEN P25=0 ELSE P25=P25
816 IF P26>=0 THEN P26=0 ELSE P26=P26
817 IF P27>=0 THEN P27=0 ELSE P27=P27
818 IF P28>=0 THEN P28=0 ELSE P28=P28
819 IF P29>=0 THEN P29=0 ELSE P29=P29
820 IF P30>=0 THEN P30=0 ELSE P30=P30
821 IF P31>=0 THEN P31=0 ELSE P31=P31
822 IF P32>=0 THEN P32=0 ELSE P32=P32
823 IF P33>=0 THEN P33=0 ELSE P33=P33
824 IF P34>=0 THEN P34=0 ELSE P34=P34
825 IF P35>=0 THEN P35=0 ELSE P35=P35
826 IF P36>=0 THEN P36=0 ELSE P36=P36
827 IF P37>=0 THEN P37=0 ELSE P37=P37
828 IF P38>=0 THEN P38=0 ELSE P38=P38
829 IF P39>=0 THEN P39=0 ELSE P39=P39
830 IF P40>=0 THEN P40=0 ELSE P40=P40
831 IF P41>=0 THEN P41=0 ELSE P41=P41
832 IF P42>=0 THEN P42=0 ELSE P42=P42
833 IF P43>=0 THEN P43=0 ELSE P43=P43
834 IF P44>=0 THEN P44=0 ELSE P44=P44
835 IF P45>=0 THEN P45=0 ELSE P45=P45
836 IF P46>=0 THEN P46=0 ELSE P46=P46
837 IF P47>=0 THEN P47=0 ELSE P47=P47
838 IF P48>=0 THEN P48=0 ELSE P48=P48
839 IF P49>=0 THEN P49=0 ELSE P49=P49
840 IF P50>=0 THEN P50=0 ELSE P50=P50
841 IF P51>=0 THEN P51=0 ELSE P51=P51
842 IF P52>=0 THEN P52=0 ELSE P52=P52
843 IF P53>=0 THEN P53=0 ELSE P53=P53
844 IF P54>=0 THEN P54=0 ELSE P54=P54
845 IF P55>=0 THEN P55=0 ELSE P55=P55
846 IF P56>=0 THEN P56=0 ELSE P56=P56
847 IF P57>=0 THEN P57=0 ELSE P57=P57
848 IF P58>=0 THEN P58=0 ELSE P58=P58
849 IF P59>=0 THEN P59=0 ELSE P59=P59
850 IF P60>=0 THEN P60=0 ELSE P60=P60
851 IF P61>=0 THEN P61=0 ELSE P61=P61
852 IF P62>=0 THEN P62=0 ELSE P62=P62
853 IF P63>=0 THEN P63=0 ELSE P63=P63
854 IF P64>=0 THEN P64=0 ELSE P64=P64
855 IF P65>=0 THEN P65=0 ELSE P65=P65
1201 PS11=555555!*P11+555555!*P12+555555!*P13+555555!*P14+555555!*P15+555555!*P16+555555!*P17+555555!*P18+555555!*P19+555555!*P20
1202 PS12=555555!*P21+555555!*P22+555555!*P23+555555!*P24+555555!*P25+555555!*P26+555555!*P27+555555!*P28+555555!*P29+555555!*P30
1203 PS13=555555!*P31+555555!*P32+555555!*P33+555555!*P34+555555!*P35+555555!*P36+555555!*P37+555555!*P38+555555!*P39+555555!*P40
1204 PS14=555555!*P41+555555!*P42+555555!*P43+555555!*P44+555555!*P45+555555!*P46+555555!*P47+555555!*P48+555555!*P49+555555!*P50
1205 PS15=555555!*P51+555555!*P52+555555!*P53+555555!*P54+555555!*P55+555555!*P56+555555!*P57+555555!*P58+555555!*P59+555555!*P60
1206 PS16=555555!*P61+555555!*P62+555555!*P63+555555!*P64+555555!*P65
1222 PS1=99*(PS11+PS12+PS13+PS14+PS15+PS16)
1248 P11=20*ABS(X(1)-X(2))+2*ABS(X(1)-X(3))+8*ABS(X(1)-X(4))+0*ABS(X(1)-X(5))+9*ABS(X(1)-X(6))+5*ABS(X(1)-X(7))+7*ABS(X(1)-X(8))+0*ABS(X(1)-X(9))+20*ABS(X(1)-X(10))+3*ABS(X(1)-X(11))
1252 P12=8*ABS(X(2)-X(3))+9*ABS(X(2)-X(4))+13*ABS(X(2)-X(5))+17*ABS(X(2)-X(6))+16*ABS(X(2)-X(7))+1*ABS(X(2)-X(8))+8*ABS(X(2)-X(9))+6*ABS(X(2)-X(10))+7*ABS(X(2)-X(11))
1253 P13=18*ABS(X(3)-X(4))+0*ABS(X(3)-X(5))+10*ABS(X(3)-X(6))+4*ABS(X(3)-X(7))+18*ABS(X(3)-X(8))+5*ABS(X(3)-X(9))+8*ABS(X(3)-X(10))+0*ABS(X(3)-X(11))
1254 P14=6*ABS(X(4)-X(5))+16*ABS(X(4)-X(6))+10*ABS(X(4)-X(7))+4*ABS(X(4)-X(8))+2*ABS(X(4)-X(9))+14*ABS(X(4)-X(10))+6*ABS(X(4)-X(11))
1255 P15=6*ABS(X(5)-X(6))+0*ABS(X(5)-X(7))+11*ABS(X(5)-X(8))+0*ABS(X(5)-X(9))+8*ABS(X(5)-X(10))+2*ABS(X(5)-X(11))
1256 P16=6*ABS(X(6)-X(7))+13*ABS(X(6)-X(8))+2*ABS(X(6)-X(9))+7*ABS(X(6)-X(10))+18*ABS(X(6)-X(11))+1*ABS(X(7)-X(8))+11*ABS(X(7)-X(9))+15*ABS(X(7)-X(10))+7*ABS(X(7)-X(11))
1257 P17=1*ABS(X(8)-X(9))+7*ABS(X(8)-X(10))+2*ABS(X(8)-X(11))+12*ABS(X(9)-X(10))+0*ABS(X(9)-X(11))+3*ABS(X(10)-X(11))
1447 P1=P11+P12+P13+P14+P15+P16+P17
1449 P=-P1+PS1
1451 IF P<=M THEN 1670
1452 M=P
1453 PP1=P1
1454 FOR KLX=1 TO 11
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>-7033 THEN 1916 ELSE 1999
1916 PRINT JJJJ,A(1),A(2),A(3),A(4),A(5),A(6),M,PP1
1918 PRINT A(7),A(8),A(9),A(10),A(11)
1919 REM PRINT JJJJ,A(11)
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=-31848 (in compressed form and to be interpreted in accordance with line 1916 and line 1918; copied manually from the computer monitor) are presented below.
-31948 20657.77 20651.77 20672.77 20667.77
20682.77 20677.77 -6933.58 6933.58
20644.77 20688.77 20639.27 20661.77 20698.27
-31940 54873.46 54862.46 54888.53 54883.53
54898.53 54893.53 -6978.203 6978.203
54869.46 54904.53 54854.95 54877.46 54914.03
-31886 54930.57 54919.57 54933.58 54938.58
54950.58 54945.58 -6997.481 6997.481
54912.57 54956.58 54907.07 54926.57 54966.08
-31883 12170.89 12176.89 12155.84 12160.84
12152.84 12147.84 -6953.424 6953.424
12183.9 12139.84 12189.41 12166.89 12130.34
-31848 35864.78 35975.78 35954.68 35959.68
35944.66 35949.67 -6979.793 6979.793
35982.78 35938.63 35988.29 35968.78 35929.12
The best candidate solution above is at JJJJ=-31948 with 6933.58 as the objective function value, and the output above was obtained in 6.2 hours on a personal computer with an Intel 2.66 GHz. chip and the IBM interpreter.
If one makes changes to the computer program above, such as a change of changing line 90 to, for example, 90 FOR INEW=1 TO 12, one may or may not obtain 6933.58. This point is relevant to the present problem and beyond it. 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. Running several computers simultaneously 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, "On the Exact Solution of a Facility Layout Problem," European Journal of Operational Research, 173(2) 508-518 (2006).
[2] A. R. S. Amaral, "An Exact Approach to the One-Dimensional Facility Layout Problem," Operations Research, Vol. 56, No. 4, July-August 2008, pp. 1026-1033.
[3] W. C. Conley, Optimization: A Simplified Approach. Petrocelli, Princeton, New Jersey, 1981, pp. 229-232.
[4] S. Heragu, Facilities Design. PWS Publishing Company, a division of International Thomson Publishing Inc., Boston, MA 02116, 1997.
