Jsun Yui Wong
The computer program listed below seeks to solve the formulation on page 138 of Heragu (1997) without office 4 and office five and without making the assumption that the longer sides are horizontal. In order to have integer locations, the office lengths and widths used in the following computer program have been made twice as long as the given office lengths and widths, respectively.
0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(166),A(166),L(166),K(166),P(166),B(166),S(166)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 6
113 A(K)=FIX(RND*699)
115 NEXT K
121 FOR KF=7 TO 30
123 A(KF)=FIX(RND*2)
125 NEXT KF
126 IMAR=10+FIX(RND*500)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 30
131 X(KK)=A(KK)
132 NEXT KK
151 IF RND<.7 GOTO 222 ELSE IF RND<.5 GOTO 236 ELSE GOTO 241
222 IJL=1+FIX(RND*6)
233 IF RND<.95 THEN X(IJL)=FIX(RND*699) ELSE X(IJL)=A(IJL)-1
235 GOTO 1001
236 IJR=7+FIX(RND*24)
238 X(IJR)=FIX(RND*2)
239 GOTO 1001
241 IF RND<.5 THEN 243 ELSE 248
243 IJU=1+FIX(RND*6):IJV=1+FIX(RND*6)
244 X(IJU)=A(IJV):X(IJV)=A(IJU)
245 GOTO 1001
248 IJW=7+FIX(RND*24):IJX=7+FIX(RND*24)
249 X(IJW)=A(IJX):X(IJX)=A(IJW)
501 GOTO 1001
1001 S(1)=ABS(X(1)-X(2))-50+9999*X(7)
1002 S(2)=ABS(X(1)-X(2))-45+9999*X(8)
1003 S(3)=ABS(X(1)-X(2))-45+9999*X(9)
1004 S(4)=ABS(X(1)-X(2))-40+9999*X(10)
1005 S(5)=ABS(X(4)-X(5))-50+9999*X(11)
1006 S(6)=ABS(X(4)-X(5))-45+9999*X(12)
1007 S(7)=ABS(X(4)-X(5))-45+9999*X(13)
1008 S(8)=ABS(X(4)-X(5))-40+9999*X(14)
1009 S(9)=ABS(X(1)-X(3))-60+9999*X(15)
1010 S(10)=ABS(X(1)-X(3))-55+9999*X(16)
1011 S(11)=ABS(X(1)-X(3))-55+9999*X(17)
1012 S(12)=ABS(X(1)-X(3))-50+9999*X(18)
1013 S(13)=ABS(X(4)-X(6))-60+9999*X(19)
1014 S(14)=ABS(X(4)-X(6))-55+9999*X(20)
1015 S(15)=ABS(X(4)-X(6))-55+9999*X(21)
1016 S(16)=ABS(X(4)-X(6))-50+9999*X(22)
1017 S(17)=ABS(X(2)-X(3))-60+9999*X(23)
1018 S(18)=ABS(X(2)-X(3))-55+9999*X(24)
1019 S(19)=ABS(X(2)-X(3))-55+9999*X(25)
1020 S(20)=ABS(X(2)-X(3))-50+9999*X(26)
1021 S(21)=ABS(X(5)-X(6))-60+9999*X(27)
1022 S(22)=ABS(X(5)-X(6))-55+9999*X(28)
1023 S(23)=ABS(X(5)-X(6))-55+9999*X(29)
1024 S(24)=ABS(X(5)-X(6))-50+9999*X(30)
1049 SSS(1)=X(7)+X(8)+X(9)+X(10)+X(11)+X(12)+X(13)+X(14)-7
1050 SSS(2)=X(15)+X(16)+X(17)+X(18)+X(19)+X(20)+X(21)+X(22)-7
1055 SSS(3)=X(23)+X(24)+X(25)+X(26)+X(27)+X(28)+X(29)+X(30)-7
1107 FOR IJUL=1 TO 24
1111 IF S(IJUL)<0 THEN S(IJUL)=ABS(S(IJUL)) ELSE S(IJUL)=0
1115 NEXT IJUL
1121 IF SSS(1)=0 THEN SSS(1)=0 ELSE SSS(1)=ABS(SSS(1))
1122 IF SSS(2)=0 THEN SSS(2)=0 ELSE SSS(2)=ABS(SSS(2))
1123 IF SSS(3)=0 THEN SSS(3)=0 ELSE SSS(3)=ABS(SSS(3))
1285 PL11=-333333!*(S(1)+S(2)+S(3)+S(4)+S(5)+S(6)+S(7)+S(8)+S(9)+S(10)+S(11))
1286 PL12=-333333!*(S(12)+S(13)+S(14)+S(15)+S(16)+S(17)+S(18)+S(19)+S(20))
1287 PL13=-333333!*(S(21)+S(22)+S(23)+S(24))
1380 PH=-10*(ABS(X(1)-X(2))+ABS(X(4)-X(5)))-15*(ABS(X(1)-X(3))+ABS(X(4)-X(6)))-30*(ABS(X(2)-X(3))+ABS(X(5)-X(6)))
1587 PK=PH
1588 P=PK-333333!*(SSS(1))-333333!*(SSS(2))-333333!*(SSS(3))+PL11+PL12+PL13
1599 PR=PK
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 30
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-3270 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5),A(6)
1913 PRINT A(7),A(8),A(9),A(10)
1914 PRINT A(11),A(12),A(13),A(14)
1915 PRINT A(15),A(16),A(17),A(18)
1916 PRINT A(19),A(20),A(21),A(22)
1917 PRINT A(23),A(24),A(25),A(26)
1918 PRINT A(27),A(28),A(29),A(30)
1927 PRINT M,MM,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 3 minutes of running is presented below. (What immediately follows is a manual copy from the computer screen.)
379 429 379 323 273
273
1 1 0 1
1 1 1 1
1 1 1 1
1 1 1 0
1 1 1 0
1 1 1 1
-3250 -3250 -31978
285 285 235 370 330
330
1 1 1 1
1 1 1 0
1 1 1 0
1 1 1 1
1 1 1 0
1 1 1 1
-3250 -3250 -31798
346 296 296 113 163
113
1 1 1 0
1 1 1 1
1 1 1 0
1 1 1 1
1 1 1 1
1 1 1 0
-3250 -3250 -31784
433 383 383 130 180
130
1 1 1 1
1 0 1 1
1 1 1 0
1 1 1 1
1 1 1 1
1 1 1 0
-3250 -3250 -31766
318 368 368 443 493
443
1 1 0 1
1 1 1 1
1 1 1 0
1 1 1 1
1 1 1 1
1 1 1 0
-3250 -3250 -31758
544 494 494 87 135
85
1 1 0 1
1 1 1 1
1 1 1 0
1 1 1 1
1 1 1 1
1 1 1 0
-3250 -3250 -31718
551 501 551 270 220
220
0 1 1 1
1 1 1 1
1 1 1 1
1 1 1 0
1 1 1 0
1 1 1 1
-3250 -3250 -31640
338 388 388 465 415
465
0 1 1 1
1 1 1 1
1 1 1 0
1 1 1 1
1 1 1 1
1 1 1 0
-3250 -3250 -31577
250 200 200 159 109
159
1 0 1 1
1 1 1 1
1 1 1 0
1 1 1 1
1 1 1 1
1 1 1 0
-3250 -3250 -31544
140 140 140 174 134
84
1 1 1 1
1 1 1 0
1 1 1 1
1 0 1 1
1 1 1 1
1 1 1 0
-3250 -3250 -31543
The candidate solution above at JJJJ=-31543 is a usable layout of the three offices. Interpreted in accordance with line 1912 through line 1927, the output through JJJJ=-31543 was produced in the first 3 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Heragu, S. S.: "Facilities Design," PWS Publishing Co., Boston, 1997.
Hillier, F. S., and G. J. Lieberman: "Introduction to Operations Research," Sixth Edition, pp. 498-499, McGraw-Hill, Inc., New York, 1995.
