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

Jsun Yui Wong

The complete computer program listed below is concerned with a three-dimensional layout problem based on the two-dimensional problem of Armour and Buffa (1963). The facility sizes for facility 1 through facility 5 are 25x20x40, 25x20x40, 35x30x40,
30x20x50, and 35x20x50, respectively; the flows are shown in line 1621 through line 1632 of the following program. The data for the first two dimensions are from Heragu (2008, page 220). In order to have integer solutions, these original lengths and widths are multiplied by 4; then these longer lengths and widths are used in line 551 through line 589 of the following program.

0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466),HS(99)
6 DIM T(11,11,5),TZ(11,11),TL(33)
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 15
88 A(I)=FIX(RND*1000)
89 NEXT I
126 IMAR=10+FIX(RND*20000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 15
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*15)
234 X(IJL)=FIX(RND*1000)
291 HS(1)=ABS(X(1)-X(2))
292 HS(2)=ABS(X(1)-X(3))
293 HS(3)=ABS(X(1)-X(4))
294 HS(4)=ABS(X(1)-X(5))
322 HS(5)=ABS(X(2)-X(3))
323 HS(6)=ABS(X(2)-X(4))
324 HS(7)=ABS(X(2)-X(5))
325 HS(8)=ABS(X(3)-X(4))
326 HS(9)=ABS(X(3)-X(5))
336 HS(10)=ABS(X(4)-X(5))
383 HS(11)=ABS(X(6)-X(7))
384 HS(12)=ABS(X(6)-X(8))
385 HS(13)=ABS(X(6)-X(9))
386 HS(14)=ABS(X(6)-X(10))
391 HS(15)=ABS(X(7)-X(8))
392 HS(16)=ABS(X(7)-X(9))
393 HS(17)=ABS(X(7)-X(10))
401 HS(18)=ABS(X(8)-X(9))
402 HS(19)=ABS(X(8)-X(10))
406 HS(20)=ABS(X(9)-X(10))
441 HS(21)=ABS(X(11)-X(12))
442 HS(22)=ABS(X(11)-X(13))
443 HS(23)=ABS(X(11)-X(14))
444 HS(24)=ABS(X(11)-X(15))
448 HS(25)=ABS(X(12)-X(13))
449 HS(26)=ABS(X(12)-X(14))
450 HS(27)=ABS(X(12)-X(15))
454 HS(28)=ABS(X(13)-X(14))
455 HS(29)=ABS(X(13)-X(15))
456 HS(30)=ABS(X(14)-X(15))
551 IF HS(1)-100<-.0001 AND HS(11)-80<-.0001 AND HS(21)-160<-.0001 THEN HS(1)=999999!
553 IF HS(2)-120<-.0001 AND HS(12)-100<-.0001 AND HS(22)-160<-.0001 THEN HS(2)=999999!
554 IF HS(3)-110<-.0001 AND HS(13)-80<-.0001 AND HS(23)-180<-.0001 THEN HS(3)=999999!
555 IF HS(4)-120<-.0001 AND HS(14)-80<-.0001 AND HS(24)-180<-.0001 THEN HS(4)=999999!
565 IF HS(5)-120<-.0001 AND HS(15)-100<-.0001 AND HS(25)-160<-.0001 THEN HS(5)=999999!
568 IF HS(6)-110<-.0001 AND HS(16)-80<-.0001 AND HS(26)-180<-.0001 THEN HS(6)=999999!
569 IF HS(7)-120<-.0001 AND HS(17)-80<-.0001 AND HS(27)-180<-.0001 THEN HS(7)=999999!
584 IF HS(8)-130<-.0001 AND HS(18)-100<-.0001 AND HS(28)-180<-.0001 THEN HS(8)=999999!
585 IF HS(9)-140<-.0001 AND HS(19)-100<-.0001 AND HS(29)-180<-.0001 THEN HS(9)=999999!
589 IF HS(10)-130<-.0001 AND HS(20)-80<-.0001 AND HS(30)-200<-.0001 THEN HS(10)=999999!
1621 PR1=-10*(HS(1)+HS(11)+HS(21))-15*(HS(2)+HS(12)+HS(22))-20*(HS(3)+HS(13)+HS(23))-.01*(HS(4)+HS(14)+HS(24))
1622 PR2=-30*(HS(5)+HS(15)+HS(25))-35*(HS(6)+HS(16)+HS(26))-10*(HS(7)+HS(17)+HS(27))
1631 PR3=-10*(HS(8)+HS(18)+HS(28))-20*(HS(9)+HS(19)+HS(29))
1632 PR4=-15*(HS(10)+HS(20)+HS(30))
1655 P=PR1+PR2+PR3+PR4
1656 IF P<=M THEN 1670
1657 FOR KEW=1 TO 15
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-22200 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),A(9),A(10)
1915 PRINT A(11),A(12),A(13),A(14),A(15)
1919 PRINT M,JJJJ
1999 NEXT JJJJ

One notes that the flow of .01 in line 1621 above is an artificial flow.

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, and the output produced in the first ten hours of running is presented below. What immediately follows is a manual copy from the computer screen.

149 268 269 158 268
192 111 211 111 31
194 194 194 194 194
-22147.8 -31580

445 445 565 445 575
643 723 702 803 802
137 137 137 137 137
-22182.89 -28684

578 459 458 569 459
337 257 357 257 177
322 322 322 322 322
-22132.79 -25897

739 619 619 729 619
432 512 412 512 592
352 352 352 352 352
-22102.8 -24282

388 507 508 397 508
575 655 555 655 735
327 327 327 327 326
-22182.81 -24229

Interpreted in accordance with line 1912 through line 1919, the output above was produced in the first ten hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter, which is not a compiler.

References

G. C. Armour and E. S. Buffa, "A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities," Management Science 9, 294-309 (1963).

S. S. Heragu. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.

An Illustration of a Computer Program for Relative Location of Three-Dimensional Facilities

Jsun Yui Wong

The complete computer program listed below is concerned with a three-dimensional layout problem based on the two-dimensional problem of Armour and Buffa (1963). The facility sizes for facility 1 through facility 3 are 25x20x40, 25x20x40,
and 35x30x70, respectively; the flows are shown in line 1621 of the following program. Some of these given data are from Heragu (2008, page 220). In order to have integer solutions, these original lengths and widths are multiplied by 4; then these longer lengths and widths are used in line 551 through line 554 of the following program.

0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466),HS(99)
6 DIM T(11,11,5),TZ(11,11),TL(33)
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 9
88 A(I)=FIX(RND*1000)
89 NEXT I
126 IMAR=10+FIX(RND*2000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 9
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*9)
234 X(IJL)=FIX(RND*1000)
291 HS(1)=ABS(X(1)-X(2))
292 HS(2)=ABS(X(1)-X(3))
293 HS(3)=ABS(X(2)-X(3))
294 HS(4)=ABS(X(4)-X(5))
295 HS(5)=ABS(X(4)-X(6))
296 HS(6)=ABS(X(5)-X(6))
297 HS(7)=ABS(X(7)-X(8))
307 HS(8)=ABS(X(7)-X(9))
308 HS(9)=ABS(X(8)-X(9))
551 IF HS(1)-100<-.0001 AND HS(4)-80<-.0001 AND HS(7)-160<-.0001 THEN HS(1)=99999!
553 IF HS(2)-120<-.0001 AND HS(5)-100<-.0001 AND HS(8)-220<-.0001 THEN HS(2)=99999!
554 IF HS(3)-120<-.0001 AND HS(6)-100<-.0001 AND HS(9)-220<-.0001 THEN HS(3)=99999!
1621 PR1=-10*(HS(1)+HS(4)+HS(7))-75*(HS(2)+HS(5)+HS(8))-20*(HS(3)+HS(6)+HS(9))
1655 P=PR1
1656 IF P<=M THEN 1670
1657 FOR KEW=1 TO 9
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-11561 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),A(9)
1919 PRINT M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, and the output through JJJJ=-31839 is presented below. What immediately follows is a manual copy from the computer screen.

756 756 756 504 705
604 682 681 682
-11560 -31979

831 831 831 660 862
760 609 609 609
-11560 -31939

740 740 740 94 294
194 46 46 46
-11500 -31927

146 146 146 562 763
662 639 639 639
-11530 -31903

520 520 520 387 187
287 249 249 249
-11500 -31839

Interpreted in accordance with line 1912 through line 1919, the output above was produced in thirty seconds on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter, which is not a compiler.

References

G. C. Armour and E. S. Buffa, "A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities," Management Science 9, 294-309 (1963).

S. S. Heragu. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.

A Computer Program for Relative Location of Three-Dimensional Facilities, Second Edition

Jsun Yui Wong

The complete computer program listed below is concerned with an extension of the layout problem of Armour and Buffa (1963), from a two-dimensional problem to a three-dimensional problem. The departmment sizes for department 1 through department 8 are 25x20x40, 25x20x40, 35x30x40, 30x20x50, 35x20x50, 60x40x50, 40x10x70, and 20x10x70, respectively; the interdepartmental flows are shown in line 1621 through line 1654 of the following program. Most of the given data are based on those of Heragu (2008, page 220) and of Amaral (2008, page 1032). In order to have integer solutions, these original lengths and widths are multiplied by 4; then these longer lengths and widths are used in line 291 through line 468 of the following program.

0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466),HS(99)
6 DIM T(11,11,5),TZ(11,11),TL(33)
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 24
88 A(I)=FIX(RND*1000)
89 NEXT I
126 IMAR=10+FIX(RND*20000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 24
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*24)
234 X(IJL)=FIX(RND*1000)
291 HS(1)=ABS(X(1)-X(2))-100
292 HS(2)=ABS(X(1)-X(3))-120
293 HS(3)=ABS(X(1)-X(4))-110
294 HS(4)=ABS(X(1)-X(5))-120
295 HS(5)=ABS(X(1)-X(6))-170
296 HS(6)=ABS(X(1)-X(7))-130
297 HS(7)=ABS(X(1)-X(8))-90
307 HS(8)=ABS(X(2)-X(3))-120
308 HS(9)=ABS(X(2)-X(4))-110
309 HS(10)=ABS(X(2)-X(5))-120
310 HS(11)=ABS(X(2)-X(6))-170
311 HS(12)=ABS(X(2)-X(7))-130
312 HS(13)=ABS(X(2)-X(8))-90
322 HS(14)=ABS(X(3)-X(4))-130
323 HS(15)=ABS(X(3)-X(5))-140
324 HS(16)=ABS(X(3)-X(6))-190
325 HS(17)=ABS(X(3)-X(7))-150
326 HS(18)=ABS(X(3)-X(8))-110
336 HS(19)=ABS(X(4)-X(5))-130
337 HS(20)=ABS(X(4)-X(6))-180
338 HS(21)=ABS(X(4)-X(7))-140
339 HS(22)=ABS(X(4)-X(8))-100
349 HS(23)=ABS(X(5)-X(6))-190
350 HS(24)=ABS(X(5)-X(7))-150
351 HS(25)=ABS(X(5)-X(8))-110
369 HS(26)=ABS(X(6)-X(7))-200
370 HS(27)=ABS(X(6)-X(8))-160
371 HS(28)=ABS(X(7)-X(8))-120
383 HS(29)=ABS(X(9)-X(10))-80
384 HS(30)=ABS(X(9)-X(11))-100
385 HS(31)=ABS(X(9)-X(12))-80
386 HS(32)=ABS(X(9)-X(13))-80
387 HS(33)=ABS(X(9)-X(14))-120
388 HS(34)=ABS(X(9)-X(15))-60
389 HS(35)=ABS(X(9)-X(16))-60
391 HS(36)=ABS(X(10)-X(11))-100
392 HS(37)=ABS(X(10)-X(12))-80
393 HS(38)=ABS(X(10)-X(13))-80
394 HS(39)=ABS(X(10)-X(14))-120
395 HS(40)=ABS(X(10)-X(15))-60
396 HS(41)=ABS(X(10)-X(16))-60
401 HS(42)=ABS(X(11)-X(12))-100
402 HS(43)=ABS(X(11)-X(13))-100
403 HS(44)=ABS(X(11)-X(14))-140
404 HS(45)=ABS(X(11)-X(15))-80
405 HS(46)=ABS(X(11)-X(16))-80
406 HS(47)=ABS(X(12)-X(13))-80
407 HS(48)=ABS(X(12)-X(14))-120
408 HS(49)=ABS(X(12)-X(15))-60
409 HS(50)=ABS(X(12)-X(16))-60
412 HS(51)=ABS(X(13)-X(14))-120
413 HS(52)=ABS(X(13)-X(15))-60
414 HS(53)=ABS(X(13)-X(16))-60
415 HS(54)=ABS(X(14)-X(15))-100
416 HS(55)=ABS(X(14)-X(16))-100
417 HS(56)=ABS(X(15)-X(16))-40
441 HS(57)=ABS(X(17)-X(18))-160
442 HS(58)=ABS(X(17)-X(19))-160
443 HS(59)=ABS(X(17)-X(20))-180
444 HS(60)=ABS(X(17)-X(21))-180
445 HS(61)=ABS(X(17)-X(22))-180
446 HS(62)=ABS(X(17)-X(23))-220
447 HS(63)=ABS(X(17)-X(24))-220
448 HS(64)=ABS(X(18)-X(19))-160
449 HS(65)=ABS(X(18)-X(20))-180
450 HS(66)=ABS(X(18)-X(21))-180
451 HS(67)=ABS(X(18)-X(22))-180
452 HS(68)=ABS(X(18)-X(23))-220
453 HS(69)=ABS(X(18)-X(24))-220
454 HS(70)=ABS(X(19)-X(20))-180
455 HS(71)=ABS(X(19)-X(21))-180
456 HS(72)=ABS(X(19)-X(22))-180
457 HS(73)=ABS(X(19)-X(23))-220
458 HS(74)=ABS(X(19)-X(24))-220
459 HS(75)=ABS(X(20)-X(21))-200
460 HS(76)=ABS(X(20)-X(22))-200
461 HS(77)=ABS(X(20)-X(23))-240
462 HS(78)=ABS(X(20)-X(24))-240
463 HS(79)=ABS(X(21)-X(22))-200
464 HS(80)=ABS(X(21)-X(23))-240
465 HS(81)=ABS(X(21)-X(24))-240
466 HS(82)=ABS(X(22)-X(23))-240
467 HS(83)=ABS(X(22)-X(24))-240
468 HS(84)=ABS(X(23)-X(24))-280
551 IF HS(1)<-.0001 AND HS(29)<-.0001 AND HS(57)<-.0001 THEN TL(1)=999999! ELSE TL(1)=0
553 IF HS(2)<-.0001 AND HS(30)<-.0001 AND HS(58)<-.0001 THEN TL(2)=999999! ELSE TL(2)=0
554 IF HS(3)<-.0001 AND HS(31)<-.0001 AND HS(59)<-.0001 THEN TL(3)=999999! ELSE TL(3)=0
555 IF HS(4)<-.0001 AND HS(32)<-.0001 AND HS(60)<-.0001 THEN TL(4)=999999! ELSE TL(4)=0
557 IF HS(5)<-.0001 AND HS(33)<-.0001 AND HS(61)<-.0001 THEN TL(5)=999999! ELSE TL(5)=0
559 IF HS(6)<-.0001 AND HS(34)<-.0001 AND HS(62)<-.0001 THEN TL(6)=999999! ELSE TL(6)=0
560 IF HS(7)<-.0001 AND HS(35)<-.0001 AND HS(63)<-.0001 THEN TL(7)=999999! ELSE TL(7)=0
565 IF HS(8)<-.0001 AND HS(36)<-.0001 AND HS(64)<-.0001 THEN TL(8)=999999! ELSE TL(8)=0
568 IF HS(9)<-.0001 AND HS(37)<-.0001 AND HS(65)<-.0001 THEN TL(9)=999999! ELSE TL(9)=0
569 IF HS(10)<-.0001 AND HS(38)<-.0001 AND HS(66)<-.0001 THEN TL(10)=999999! ELSE TL(10)=0
581 IF HS(11)<-.0001 AND HS(39)<-.0001 AND HS(67)<-.0001 THEN TL(11)=999999! ELSE TL(11)=0
582 IF HS(12)<-.0001 AND HS(40)<-.0001 AND HS(68)<-.0001 THEN TL(12)=999999! ELSE TL(12)=0
583 IF HS(13)<-.0001 AND HS(41)<-.0001 AND HS(69)<-.0001 THEN TL(13)=999999! ELSE TL(13)=0
584 IF HS(14)<-.0001 AND HS(42)<-.0001 AND HS(70)<-.0001 THEN TL(14)=999999! ELSE TL(14)=0
585 IF HS(15)<-.0001 AND HS(43)<-.0001 AND HS(71)<-.0001 THEN TL(15)=999999! ELSE TL(15)=0
586 IF HS(16)<-.0001 AND HS(44)<-.0001 AND HS(72)<-.0001 THEN TL(16)=999999! ELSE TL(16)=0
587 IF HS(17)<-.0001 AND HS(45)<-.0001 AND HS(73)<-.0001 THEN TL(17)=999999! ELSE TL(17)=0
588 IF HS(18)<-.0001 AND HS(46)<-.0001 AND HS(74)<-.0001 THEN TL(18)=999999! ELSE TL(18)=0
589 IF HS(19)<-.0001 AND HS(47)<-.0001 AND HS(75)<-.0001 THEN TL(19)=999999! ELSE TL(19)=0
590 IF HS(20)<-.0001 AND HS(48)<-.0001 AND HS(76)<-.0001 THEN TL(20)=999999! ELSE TL(20)=0
591 IF HS(21)<-.0001 AND HS(49)<-.0001 AND HS(77)<-.0001 THEN TL(21)=999999! ELSE TL(21)=0
592 IF HS(22)<-.0001 AND HS(50)<-.0001 AND HS(78)<-.0001 THEN TL(22)=999999! ELSE TL(22)=0
593 IF HS(23)<-.0001 AND HS(51)<-.0001 AND HS(79)<-.0001 THEN TL(23)=999999! ELSE TL(23)=0
594 IF HS(24)<-.0001 AND HS(52)<-.0001 AND HS(80)<-.0001 THEN TL(24)=999999! ELSE TL(24)=0
595 IF HS(25)<-.0001 AND HS(53)<-.0001 AND HS(81)<-.0001 THEN TL(25)=999999! ELSE TL(25)=0
596 IF HS(26)<-.0001 AND HS(54)<-.0001 AND HS(82)<-.0001 THEN TL(26)=999999! ELSE TL(26)=0
597 IF HS(27)<-.0001 AND HS(55)<-.0001 AND HS(83)<-.0001 THEN TL(27)=999999! ELSE TL(27)=0
598 IF HS(28)<-.0001 AND HS(56)<-.0001 AND HS(84)<-.0001 THEN TL(28)=999999! ELSE TL(28)=0
1611 SUMTL=0
1613 FOR IR=1 TO 28
1615 SUMTL=SUMTL+TL(IR)
1618 NEXT IR
1621 PR1=-10*ABS(X(1)-X(2))-15*ABS(X(1)-X(3))-20*ABS(X(1)-X(4))-0*ABS(X(1)-X(5))-17*ABS(X(1)-X(6))-0*ABS(X(1)-X(7))-6*ABS(X(1)-X(8))
1622 PR2=-30*ABS(X(2)-X(3))-35*ABS(X(2)-X(4))-10*ABS(X(2)-X(5))-32*ABS(X(2)-X(6))-10*ABS(X(2)-X(7))-2*ABS(X(2)-X(8))
1631 PR3=-10*ABS(X(3)-X(4))-20*ABS(X(3)-X(5))-26*ABS(X(3)-X(6))-0*ABS(X(3)-X(7))-10*ABS(X(3)-X(8))
1632 PR4=-15*ABS(X(4)-X(5))-13*ABS(X(4)-X(6))-10*ABS(X(4)-X(7))-10*ABS(X(4)-X(8))
1633 PR5=-19*ABS(X(5)-X(6))-4*ABS(X(5)-X(7))-10*ABS(X(5)-X(8))-20*ABS(X(6)-X(7))-0*ABS(X(6)-X(8))-0*ABS(X(7)-X(8))
1636 REM
1643 PR8=-10*ABS(X(9)-X(10))-15*ABS(X(9)-X(11))-20*ABS(X(9)-X(12))-0*ABS(X(9)-X(13))-17*ABS(X(9)-X(14))-0*ABS(X(9)-X(15))-6*ABS(X(9)-X(16))
1644 PR9=-30*ABS(X(10)-X(11))-35*ABS(X(10)-X(12))-10*ABS(X(10)-X(13))-32*ABS(X(10)-X(14))-10*ABS(X(10)-X(15))-2*ABS(X(10)-X(16))
1645 PR10=-10*ABS(X(11)-X(12))-20*ABS(X(11)-X(13))-26*ABS(X(11)-X(14))-0*ABS(X(11)-X(15))-10*ABS(X(11)-X(16))
1646 PR11=-15*ABS(X(12)-X(13))-13*ABS(X(12)-X(14))-10*ABS(X(12)-X(15))-10*ABS(X(12)-X(16))
1647 PR12=-19*ABS(X(13)-X(14))-4*ABS(X(13)-X(15))-10*ABS(X(13)-X(16))-20*ABS(X(14)-X(15))-0*ABS(X(14)-X(16))-0*ABS(X(15)-X(16))
1650 PR13=-10*ABS(X(17)-X(18))-15*ABS(X(17)-X(19))-20*ABS(X(17)-X(20))-0*ABS(X(17)-X(21))-17*ABS(X(17)-X(22))-0*ABS(X(17)-X(23))-6*ABS(X(17)-X(24))
1651 PR14=-30*ABS(X(18)-X(19))-35*ABS(X(18)-X(20))-18*ABS(X(18)-X(21))-32*ABS(X(18)-X(22))-10*ABS(X(18)-X(23))-2*ABS(X(18)-X(24))
1652 PR15=-10*ABS(X(19)-X(20))-20*ABS(X(19)-X(21))-26*ABS(X(19)-X(22))-0*ABS(X(19)-X(23))-10*ABS(X(19)-X(24))
1653 PR16=-15*ABS(X(20)-X(21))-13*ABS(X(20)-X(22))-10*ABS(X(20)-X(23))-10*ABS(X(20)-X(24))
1654 PR17=-19*ABS(X(21)-X(22))-4*ABS(X(21)-X(23))-10*ABS(X(21)-X(24))-20*ABS(X(22)-X(23))-0*ABS(X(22)-X(24))-0*ABS(X(23)-X(24))
1655 P=PR1+PR2+PR3+PR4+PR5+PR8+PR9+PR10+PR11+PR12+PR13+PR14+PR15+PR16+PR17-999*SUMTL
1656 IF P<=M THEN 1670
1657 FOR KEW=1 TO 24
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1662 MM=PR1+PR2+PR3+PR4+PR5+PR8+PR9+PR10+PR11+PR12+PR13+PR14+PR15+PR16+PR17
1666 GOTO 128
1670 NEXT I
1890 IF M>-67450! THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),A(9),A(10)
1915 PRINT A(11),A(12),A(13),A(14),A(15)
1916 PRINT A(16),A(17),A(18),A(19),A(20)
1917 PRINT A(21),A(22),A(23),A(24)
1919 PRINT MM,M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, and selected candidate solutions produced through twenty hours of running are presented below. What immediately follows is a manual copy of these solutions from the computer screen.

503 603 603 713 744
603 853 713 371 371
271 371 234 491 372
294 691 691 690 691
690 690 690 691
-67446 -67446 -32000
.
.
.
141 254 261 144 374
254 254 261 424 344
484 344 344 184 284
404 564 564 564 564
564 564 564 564
-65057 -65067 -30779
.
.
.
550 650 648 761 788
650 651 538 206 206
105 206 126 326 426
127 426 426 426 426
426 426 426 426
-64184 -64184 -28727

Interpreted in accordance with line 1912 through line 1919, these selected candidate solutions were produced through twenty hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter, which is not a compiler.

The best candidate solution presented above, at JJJJ=-28727, can be not optimal. To alleviate that problem, one can use the multicomputer approach that uses several personal computers running simultaneously and independently, each running a slightly different computer program. For example, one computer can run with
126 IMAR=10+FIX(RND*21111), another computer can use 126 IMAR=10+FIX(RND*22222), and so forth. Then, speaking generally, one can obtain a better candidate solution in a shorter period of time.

An illustration of the multicomputer approach follows.

In twenty hours of running on a comparable computer, the computer program listed above plus the change of its
126 IMAR=10+FIX(RND*20000) to 126 IMAR=10+FIX(RND*21111) produced two candidate solutions with objective function values of less than 65000. These are shown below.

718 835 838 724 956
835 835 838 620 540
641 540 540 379 479
721 306 306 306 306
306 306 306 306
-64544 -64544 -30801

167 267 397 267 267
267 245 367 487 487
487 567 648 327 427
567 660 660 660 660
660 660 660 660
-63596 -63596 -29071

In twenty hours of running on a comparable computer, the computer program listed above plus the change of its
126 IMAR=10+FIX(RND*20000) to 126 IMAR=10+FIX(RND*22222) produced no candidate solution with an objective function value of less than 65000.

In twenty hours of running on a comparable computer, the computer program listed above plus the change of its
126 IMAR=10+FIX(RND*20000) to 126 IMAR=10+FIX(RND*23333) produced no candidate solution with an objective function value of less than 65000.

References

G. C. Armour and E. S. Buffa, "A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities," Management Science 9, 294-309 (1963).

S. S. Heragu. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.

A. R. S. Amaral, "An Exact Approach to the One-Dimensional Facility Layout Problem," Operations Research 56, 1026-1033 (2008).

A Computer Program for Relative Location of Three-Dimensional Facilities

Jsun Yui Wong

The complete computer program listed below is concerned with an extension of the layout problem of Armour and Buffa (1963), from a two-dimensional problem to a three-dimensional problem. The departmment sizes for department 1 through department 8 are 25x20x40, 25x20x40, 35x30x40, 30x20x50, 35x20x50, 60x40x50, 40x10x70, and 20x10x70, respectively; the interdepartmental flows are shown in line 1621 through line 1654 of the following program. Most of the given data are based on those of Heragu
(2008, page 220) and of Amaral (2008, page 1032). In order to have integer solutions, these original lengths and widths are multiplied by 4; then these longer lengths and widths are used in line 291 through line 468 of the following program.

0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466),HS(99)
6 DIM T(11,11,5),TZ(11,11),TL(33)
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 24
88 A(I)=FIX(RND*1000)
89 NEXT I
126 IMAR=10+FIX(RND*20000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 24
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*24)
234 X(IJL)=FIX(RND*1000)
291 HS(1)=ABS(X(1)-X(2))-100
292 HS(2)=ABS(X(1)-X(3))-120
293 HS(3)=ABS(X(1)-X(4))-110
294 HS(4)=ABS(X(1)-X(5))-120
295 HS(5)=ABS(X(1)-X(6))-170
296 HS(6)=ABS(X(1)-X(7))-130
297 HS(7)=ABS(X(1)-X(8))-90
307 HS(8)=ABS(X(2)-X(3))-120
308 HS(9)=ABS(X(2)-X(4))-110
309 HS(10)=ABS(X(2)-X(5))-120
310 HS(11)=ABS(X(2)-X(6))-170
311 HS(12)=ABS(X(2)-X(7))-130
312 HS(13)=ABS(X(2)-X(8))-90
322 HS(14)=ABS(X(3)-X(4))-130
323 HS(15)=ABS(X(3)-X(5))-140
324 HS(16)=ABS(X(3)-X(6))-190
325 HS(17)=ABS(X(3)-X(7))-150
326 HS(18)=ABS(X(3)-X(8))-110
336 HS(19)=ABS(X(4)-X(5))-130
337 HS(20)=ABS(X(4)-X(6))-180
338 HS(21)=ABS(X(4)-X(7))-140
339 HS(22)=ABS(X(4)-X(8))-100
349 HS(23)=ABS(X(5)-X(6))-190
350 HS(24)=ABS(X(5)-X(7))-150
351 HS(25)=ABS(X(5)-X(8))-110
369 HS(26)=ABS(X(6)-X(7))-200
370 HS(27)=ABS(X(6)-X(8))-160
371 HS(28)=ABS(X(7)-X(8))-120
383 HS(29)=ABS(X(9)-X(10))-80
384 HS(30)=ABS(X(9)-X(11))-100
385 HS(31)=ABS(X(9)-X(12))-80
386 HS(32)=ABS(X(9)-X(13))-80
387 HS(33)=ABS(X(9)-X(14))-120
388 HS(34)=ABS(X(9)-X(15))-60
389 HS(35)=ABS(X(9)-X(16))-60
391 HS(36)=ABS(X(10)-X(11))-100
392 HS(37)=ABS(X(10)-X(12))-80
393 HS(38)=ABS(X(10)-X(13))-80
394 HS(39)=ABS(X(10)-X(14))-120
395 HS(40)=ABS(X(10)-X(15))-60
396 HS(41)=ABS(X(10)-X(16))-60
401 HS(42)=ABS(X(11)-X(12))-100
402 HS(43)=ABS(X(11)-X(13))-100
403 HS(44)=ABS(X(11)-X(14))-140
404 HS(45)=ABS(X(11)-X(15))-80
405 HS(46)=ABS(X(11)-X(16))-80
406 HS(47)=ABS(X(12)-X(13))-80
407 HS(48)=ABS(X(12)-X(14))-120
408 HS(49)=ABS(X(12)-X(15))-60
409 HS(50)=ABS(X(12)-X(16))-60
412 HS(51)=ABS(X(13)-X(14))-120
413 HS(52)=ABS(X(13)-X(15))-60
414 HS(53)=ABS(X(13)-X(16))-60
415 HS(54)=ABS(X(14)-X(15))-100
416 HS(55)=ABS(X(14)-X(16))-100
417 HS(56)=ABS(X(15)-X(16))-40
441 HS(57)=ABS(X(17)-X(18))-160
442 HS(58)=ABS(X(17)-X(19))-160
443 HS(59)=ABS(X(17)-X(20))-180
444 HS(60)=ABS(X(17)-X(21))-180
445 HS(61)=ABS(X(17)-X(22))-180
446 HS(62)=ABS(X(17)-X(23))-220
447 HS(63)=ABS(X(17)-X(24))-220
448 HS(64)=ABS(X(18)-X(19))-160
449 HS(65)=ABS(X(18)-X(20))-180
450 HS(66)=ABS(X(18)-X(21))-180
451 HS(67)=ABS(X(18)-X(22))-180
452 HS(68)=ABS(X(18)-X(23))-220
453 HS(69)=ABS(X(18)-X(24))-220
454 HS(70)=ABS(X(19)-X(20))-180
455 HS(71)=ABS(X(19)-X(21))-180
456 HS(72)=ABS(X(19)-X(22))-180
457 HS(73)=ABS(X(19)-X(23))-220
458 HS(74)=ABS(X(19)-X(24))-220
459 HS(75)=ABS(X(20)-X(21))-200
460 HS(76)=ABS(X(20)-X(22))-200
461 HS(77)=ABS(X(20)-X(23))-240
462 HS(78)=ABS(X(20)-X(24))-240
463 HS(79)=ABS(X(21)-X(22))-200
464 HS(80)=ABS(X(21)-X(23))-240
465 HS(81)=ABS(X(21)-X(24))-240
466 HS(82)=ABS(X(22)-X(23))-240
467 HS(83)=ABS(X(22)-X(24))-240
468 HS(84)=ABS(X(23)-X(24))-280
551 IF HS(1)<-.0001 AND HS(29)<-.0001 AND HS(57)<-.0001 THEN TL(1)=999999! ELSE TL(1)=0
553 IF HS(2)<-.0001 AND HS(30)<-.0001 AND HS(58)<-.0001 THEN TL(2)=999999! ELSE TL(2)=0
554 IF HS(3)<-.0001 AND HS(31)<-.0001 AND HS(59)<-.0001 THEN TL(3)=999999! ELSE TL(3)=0
555 IF HS(4)<-.0001 AND HS(32)<-.0001 AND HS(60)<-.0001 THEN TL(4)=999999! ELSE TL(4)=0
557 IF HS(5)<-.0001 AND HS(33)<-.0001 AND HS(61)<-.0001 THEN TL(5)=999999! ELSE TL(5)=0
559 IF HS(6)<-.0001 AND HS(34)<-.0001 AND HS(62)<-.0001 THEN TL(6)=999999! ELSE TL(6)=0
560 IF HS(7)<-.0001 AND HS(35)<-.0001 AND HS(63)<-.0001 THEN TL(7)=999999! ELSE TL(7)=0
565 IF HS(8)<-.0001 AND HS(36)<-.0001 AND HS(64)<-.0001 THEN TL(8)=999999! ELSE TL(8)=0
568 IF HS(9)<-.0001 AND HS(37)<-.0001 AND HS(65)<-.0001 THEN TL(9)=999999! ELSE TL(9)=0
569 IF HS(10)<-.0001 AND HS(38)<-.0001 AND HS(66)<-.0001 THEN TL(10)=999999! ELSE TL(10)=0
581 IF HS(11)<-.0001 AND HS(39)<-.0001 AND HS(67)<-.0001 THEN TL(11)=999999! ELSE TL(11)=0
582 IF HS(12)<-.0001 AND HS(40)<-.0001 AND HS(68)<-.0001 THEN TL(12)=999999! ELSE TL(12)=0
583 IF HS(13)<-.0001 AND HS(41)<-.0001 AND HS(69)<-.0001 THEN TL(13)=999999! ELSE TL(13)=0
584 IF HS(14)<-.0001 AND HS(42)<-.0001 AND HS(70)<-.0001 THEN TL(14)=999999! ELSE TL(14)=0
585 IF HS(15)<-.0001 AND HS(43)<-.0001 AND HS(71)<-.0001 THEN TL(15)=999999! ELSE TL(15)=0
586 IF HS(16)<-.0001 AND HS(44)<-.0001 AND HS(72)<-.0001 THEN TL(16)=999999! ELSE TL(16)=0
587 IF HS(17)<-.0001 AND HS(45)<-.0001 AND HS(73)<-.0001 THEN TL(17)=999999! ELSE TL(17)=0
588 IF HS(18)<-.0001 AND HS(46)<-.0001 AND HS(74)<-.0001 THEN TL(18)=999999! ELSE TL(18)=0
589 IF HS(19)<-.0001 AND HS(47)<-.0001 AND HS(75)<-.0001 THEN TL(19)=999999! ELSE TL(19)=0
590 IF HS(20)<-.0001 AND HS(48)<-.0001 AND HS(76)<-.0001 THEN TL(20)=999999! ELSE TL(20)=0
591 IF HS(21)<-.0001 AND HS(49)<-.0001 AND HS(77)<-.0001 THEN TL(21)=999999! ELSE TL(21)=0
592 IF HS(22)<-.0001 AND HS(50)<-.0001 AND HS(78)<-.0001 THEN TL(22)=999999! ELSE TL(22)=0
593 IF HS(23)<-.0001 AND HS(51)<-.0001 AND HS(79)<-.0001 THEN TL(23)=999999! ELSE TL(23)=0
594 IF HS(24)<-.0001 AND HS(52)<-.0001 AND HS(80)<-.0001 THEN TL(24)=999999! ELSE TL(24)=0
595 IF HS(25)<-.0001 AND HS(53)<-.0001 AND HS(81)<-.0001 THEN TL(25)=999999! ELSE TL(25)=0
596 IF HS(26)<-.0001 AND HS(54)<-.0001 AND HS(82)<-.0001 THEN TL(26)=999999! ELSE TL(26)=0
597 IF HS(27)<-.0001 AND HS(55)<-.0001 AND HS(83)<-.0001 THEN TL(27)=999999! ELSE TL(27)=0
598 IF HS(28)<-.0001 AND HS(56)<-.0001 AND HS(84)<-.0001 THEN TL(28)=999999! ELSE TL(28)=0
1611 SUMTL=0
1613 FOR IR=1 TO 28
1615 SUMTL=SUMTL+TL(IR)
1618 NEXT IR
1621 PR1=-10*ABS(X(1)-X(2))-15*ABS(X(1)-X(3))-20*ABS(X(1)-X(4))-0*ABS(X(1)-X(5))-17*ABS(X(1)-X(6))-0*ABS(X(1)-X(7))-6*ABS(X(1)-X(8))
1622 PR2=-30*ABS(X(2)-X(3))-35*ABS(X(2)-X(4))-10*ABS(X(2)-X(5))-32*ABS(X(2)-X(6))-10*ABS(X(2)-X(7))-2*ABS(X(2)-X(8))
1631 PR3=-10*ABS(X(3)-X(4))-20*ABS(X(3)-X(5))-26*ABS(X(3)-X(6))-0*ABS(X(3)-X(7))-10*ABS(X(3)-X(8))
1632 PR4=-15*ABS(X(4)-X(5))-13*ABS(X(4)-X(6))-10*ABS(X(4)-X(7))-10*ABS(X(4)-X(8))
1633 PR5=-19*ABS(X(5)-X(6))-4*ABS(X(5)-X(7))-10*ABS(X(5)-X(8))-20*ABS(X(6)-X(7))-0*ABS(X(6)-X(8))-0*ABS(X(7)-X(8))
1636 REM
1643 PR8=-10*ABS(X(9)-X(10))-15*ABS(X(9)-X(11))-20*ABS(X(9)-X(12))-0*ABS(X(9)-X(13))-17*ABS(X(9)-X(14))-0*ABS(X(9)-X(15))-6*ABS(X(9)-X(16))
1644 PR9=-30*ABS(X(10)-X(11))-35*ABS(X(10)-X(12))-10*ABS(X(10)-X(13))-32*ABS(X(10)-X(14))-10*ABS(X(10)-X(15))-2*ABS(X(10)-X(16))
1645 PR10=-10*ABS(X(11)-X(12))-20*ABS(X(11)-X(13))-26*ABS(X(11)-X(14))-0*ABS(X(11)-X(15))-10*ABS(X(11)-X(16))
1646 PR11=-15*ABS(X(12)-X(13))-13*ABS(X(12)-X(14))-10*ABS(X(12)-X(15))-10*ABS(X(12)-X(16))
1647 PR12=-19*ABS(X(13)-X(14))-4*ABS(X(13)-X(15))-10*ABS(X(13)-X(16))-20*ABS(X(14)-X(15))-0*ABS(X(14)-X(16))-0*ABS(X(15)-X(16))
1650 PR13=-10*ABS(X(17)-X(18))-15*ABS(X(17)-X(19))-20*ABS(X(17)-X(20))-0*ABS(X(17)-X(21))-17*ABS(X(17)-X(22))-0*ABS(X(17)-X(23))-6*ABS(X(17)-X(24))
1651 PR14=-30*ABS(X(18)-X(19))-35*ABS(X(18)-X(20))-18*ABS(X(18)-X(21))-32*ABS(X(18)-X(22))-10*ABS(X(18)-X(23))-2*ABS(X(18)-X(24))
1652 PR15=-10*ABS(X(19)-X(20))-20*ABS(X(19)-X(21))-26*ABS(X(19)-X(22))-0*ABS(X(19)-X(23))-10*ABS(X(19)-X(24))
1653 PR16=-15*ABS(X(20)-X(21))-13*ABS(X(20)-X(22))-10*ABS(X(20)-X(23))-10*ABS(X(20)-X(24))
1654 PR17=-19*ABS(X(21)-X(22))-4*ABS(X(21)-X(23))-10*ABS(X(21)-X(24))-20*ABS(X(22)-X(23))-0*ABS(X(22)-X(24))-0*ABS(X(23)-X(24))
1655 P=PR1+PR2+PR3+PR4+PR5+PR8+PR9+PR10+PR11+PR12+PR13+PR14+PR15+PR16+PR17-999*SUMTL
1656 IF P<=M THEN 1670
1657 FOR KEW=1 TO 24
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1662 MM=PR1+PR2+PR3+PR4+PR5+PR8+PR9+PR10+PR11+PR12+PR13+PR14+PR15+PR16+PR17
1666 GOTO 128
1670 NEXT I
1890 IF M>-67450! THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),A(9),A(10)
1915 PRINT A(11),A(12),A(13),A(14),A(15)
1916 PRINT A(16),A(17),A(18),A(19),A(20)
1917 PRINT A(21),A(22),A(23),A(24)
1919 PRINT MM,M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, and selected candidate solutions produced through twenty hours of running are presented below. What immediately follows is a manual copy of these solutions from the computer screen.

503 603 603 713 744
603 853 713 371 371
271 371 234 491 372
294 691 691 690 691
690 690 690 691
-67446 -67446 -32000
.
.
.
141 254 261 144 374
254 254 261 424 344
484 344 344 184 284
404 564 564 564 564
564 564 564 564
-65057 -65067 -30779
.
.
.
550 650 648 761 788
650 651 538 206 206
105 206 126 326 426
127 426 426 426 426
426 426 426 426
-64184 -64184 -28727

Interpreted in accordance with line 1912 through line 1919, these selected candidate solutions were produced through twenty hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter, which is not a compiler.

The best candidate solution presented above, at JJJJ=-28727, can be not optimal. To ameliorate that problem, one can use the multicomputer approach that uses several personal computers running simultaneously and independently, each running a slightly different computer program. For example, one computer can run with 126 IMAR=10+FIX(RND*21111), another computer can use 126 IMAR=10+FIX(RND*22222), and so forth. Then one can obtain a better candidate solution in a shorter period of time.

References

G. C. Armour and E. S. Buffa, "A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities," Management Science 9, 294-309 (1963).

S. S. Heragu. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.

A. R. S. Amaral, "An Exact Approach to the One-Dimensional Facility Layout Problem," Operations Research 56, 1026-1033 (2008).

A Computer Program for Relative Location of Unequal Rectangular Facilities, Second Edition

Jsun Yui Wong

The complete computer program listed below seeks to solve an eight-department layout problem (Armour and Buffa, 1963). The departmment sizes for department 1 through department 8 are 25x20, 25x20, 35x30, 30x20, 35x20, 60x40, 40x10, and 20x10, respectively; the interdepartmental flows are shown in line 1624 through line 1647 of the following program. The sizes and flows of the first five departments are from Heragu (2008, page 220). Most of the other given flows are based on those of Amaral (2008, page 1032). In order to have integer solutions, these original lengths and widths are multiplied by 4; then these longer lengths and widths are used in line 291 through line 417 of the following program.

0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466),HS(99)
6 DIM T(11,11,5),TZ(11,11),TL(33)
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 16
88 A(I)=FIX(RND*1000)
89 NEXT I
126 IMAR=10+FIX(RND*20000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 16
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*16)
234 X(IJL)=FIX(RND*1000)
291 HS(1)=ABS(X(1)-X(2))-100
292 HS(2)=ABS(X(1)-X(3))-120
293 HS(3)=ABS(X(1)-X(4))-110
294 HS(4)=ABS(X(1)-X(5))-120
295 HS(5)=ABS(X(1)-X(6))-170
296 HS(6)=ABS(X(1)-X(7))-130
297 HS(7)=ABS(X(1)-X(8))-90
307 HS(8)=ABS(X(2)-X(3))-120
308 HS(9)=ABS(X(2)-X(4))-110
309 HS(10)=ABS(X(2)-X(5))-120
310 HS(11)=ABS(X(2)-X(6))-170
311 HS(12)=ABS(X(2)-X(7))-130
312 HS(13)=ABS(X(2)-X(8))-90
322 HS(14)=ABS(X(3)-X(4))-130
323 HS(15)=ABS(X(3)-X(5))-140
324 HS(16)=ABS(X(3)-X(6))-190
325 HS(17)=ABS(X(3)-X(7))-150
326 HS(18)=ABS(X(3)-X(8))-110
336 HS(19)=ABS(X(4)-X(5))-130
337 HS(20)=ABS(X(4)-X(6))-180
338 HS(21)=ABS(X(4)-X(7))-140
339 HS(22)=ABS(X(4)-X(8))-100
349 HS(23)=ABS(X(5)-X(6))-190
350 HS(24)=ABS(X(5)-X(7))-150
351 HS(25)=ABS(X(5)-X(8))-110
369 HS(26)=ABS(X(6)-X(7))-200
370 HS(27)=ABS(X(6)-X(8))-160
371 HS(28)=ABS(X(7)-X(8))-120
383 HS(29)=ABS(X(9)-X(10))-80
384 HS(30)=ABS(X(9)-X(11))-100
385 HS(31)=ABS(X(9)-X(12))-80
386 HS(32)=ABS(X(9)-X(13))-80
387 HS(33)=ABS(X(9)-X(14))-120
388 HS(34)=ABS(X(9)-X(15))-60
389 HS(35)=ABS(X(9)-X(16))-60
391 HS(36)=ABS(X(10)-X(11))-100
392 HS(37)=ABS(X(10)-X(12))-80
393 HS(38)=ABS(X(10)-X(13))-80
394 HS(39)=ABS(X(10)-X(14))-120
395 HS(40)=ABS(X(10)-X(15))-60
396 HS(41)=ABS(X(10)-X(16))-60
401 HS(42)=ABS(X(11)-X(12))-100
402 HS(43)=ABS(X(11)-X(13))-100
403 HS(44)=ABS(X(11)-X(14))-140
404 HS(45)=ABS(X(11)-X(15))-80
405 HS(46)=ABS(X(11)-X(16))-80
406 HS(47)=ABS(X(12)-X(13))-80
407 HS(48)=ABS(X(12)-X(14))-120
408 HS(49)=ABS(X(12)-X(15))-60
409 HS(50)=ABS(X(12)-X(16))-60
412 HS(51)=ABS(X(13)-X(14))-120
413 HS(52)=ABS(X(13)-X(15))-60
414 HS(53)=ABS(X(13)-X(16))-60
415 HS(54)=ABS(X(14)-X(15))-100
416 HS(55)=ABS(X(14)-X(16))-100
417 HS(56)=ABS(X(15)-X(16))-40
551 IF HS(1)<-.0001 AND HS(29)<-.0001 THEN TL(1)=999999! ELSE TL(1)=0
553 IF HS(2)<-.0001 AND HS(30)<-.0001 THEN TL(2)=999999! ELSE TL(2)=0
554 IF HS(3)<-.0001 AND HS(31)<-.0001 THEN TL(3)=999999! ELSE TL(3)=0
555 IF HS(4)<-.0001 AND HS(32)<-.0001 THEN TL(4)=999999! ELSE TL(4)=0
557 IF HS(5)<-.0001 AND HS(33)<-.0001 THEN TL(5)=999999! ELSE TL(5)=0
559 IF HS(6)<-.0001 AND HS(34)<-.0001 THEN TL(6)=999999! ELSE TL(6)=0
560 IF HS(7)<-.0001 AND HS(35)<-.0001 THEN TL(7)=999999! ELSE TL(7)=0
565 IF HS(8)<-.0001 AND HS(36)<-.0001 THEN TL(8)=999999! ELSE TL(8)=0
568 IF HS(9)<-.0001 AND HS(37)<-.0001 THEN TL(9)=999999! ELSE TL(9)=0
569 IF HS(10)<-.0001 AND HS(38)<-.0001 THEN TL(10)=999999! ELSE TL(10)=0
581 IF HS(11)<-.0001 AND HS(39)<-.0001 THEN TL(11)=999999! ELSE TL(11)=0
582 IF HS(12)<-.0001 AND HS(40)<-.0001 THEN TL(12)=999999! ELSE TL(12)=0
583 IF HS(13)<-.0001 AND HS(41)<-.0001 THEN TL(13)=999999! ELSE TL(13)=0
584 IF HS(14)<-.0001 AND HS(42)<-.0001 THEN TL(14)=999999! ELSE TL(14)=0
585 IF HS(15)<-.0001 AND HS(43)<-.0001 THEN TL(15)=999999! ELSE TL(15)=0
586 IF HS(16)<-.0001 AND HS(44)<-.0001 THEN TL(16)=999999! ELSE TL(16)=0
587 IF HS(17)<-.0001 AND HS(45)<-.0001 THEN TL(17)=999999! ELSE TL(17)=0
588 IF HS(18)<-.0001 AND HS(46)<-.0001 THEN TL(18)=999999! ELSE TL(18)=0
589 IF HS(19)<-.0001 AND HS(47)<-.0001 THEN TL(19)=999999! ELSE TL(19)=0
590 IF HS(20)<-.0001 AND HS(48)<-.0001 THEN TL(20)=999999! ELSE TL(20)=0
591 IF HS(21)<-.0001 AND HS(49)<-.0001 THEN TL(21)=999999! ELSE TL(21)=0
592 IF HS(22)<-.0001 AND HS(50)<-.0001 THEN TL(22)=999999! ELSE TL(22)=0
593 IF HS(23)<-.0001 AND HS(51)<-.0001 THEN TL(23)=999999! ELSE TL(23)=0
594 IF HS(24)<-.0001 AND HS(52)<-.0001 THEN TL(24)=999999! ELSE TL(24)=0
595 IF HS(25)<-.0001 AND HS(53)<-.0001 THEN TL(25)=999999! ELSE TL(25)=0
596 IF HS(26)<-.0001 AND HS(54)<-.0001 THEN TL(26)=999999! ELSE TL(26)=0
597 IF HS(27)<-.0001 AND HS(55)<-.0001 THEN TL(27)=999999! ELSE TL(27)=0
598 IF HS(28)<-.0001 AND HS(56)<-.0001 THEN TL(28)=999999! ELSE TL(28)=0
1611 SUMTL=0
1613 FOR IR=1 TO 28
1615 SUMTL=SUMTL+TL(IR)
1618 NEXT IR
1621 PR1=-10*ABS(X(1)-X(2))-15*ABS(X(1)-X(3))-20*ABS(X(1)-X(4))-0*ABS(X(1)-X(5))-17*ABS(X(1)-X(6))-0*ABS(X(1)-X(7))-6*ABS(X(1)-X(8))
1622 PR2=-30*ABS(X(2)-X(3))-35*ABS(X(2)-X(4))-10*ABS(X(2)-X(5))-32*ABS(X(2)-X(6))-10*ABS(X(2)-X(7))-2*ABS(X(2)-X(8))
1631 PR3=-10*ABS(X(3)-X(4))-20*ABS(X(3)-X(5))-26*ABS(X(3)-X(6))-0*ABS(X(3)-X(7))-10*ABS(X(3)-X(8))
1632 PR4=-15*ABS(X(4)-X(5))-13*ABS(X(4)-X(6))-10*ABS(X(4)-X(7))-10*ABS(X(4)-X(8))
1633 PR5=-19*ABS(X(5)-X(6))-4*ABS(X(5)-X(7))-10*ABS(X(5)-X(8))-20*ABS(X(6)-X(7))-0*ABS(X(6)-X(8))-0*ABS(X(7)-X(8))
1636 REM
1643 PR8=-10*ABS(X(9)-X(10))-15*ABS(X(9)-X(11))-20*ABS(X(9)-X(12))-0*ABS(X(9)-X(13))-17*ABS(X(9)-X(14))-0*ABS(X(9)-X(15))-6*ABS(X(9)-X(16))
1644 PR9=-30*ABS(X(10)-X(11))-35*ABS(X(10)-X(12))-10*ABS(X(10)-X(13))-32*ABS(X(10)-X(14))-10*ABS(X(10)-X(15))-2*ABS(X(10)-X(16))
1645 PR10=-10*ABS(X(11)-X(12))-20*ABS(X(11)-X(13))-26*ABS(X(11)-X(14))-0*ABS(X(11)-X(15))-10*ABS(X(11)-X(16))
1646 PR11=-15*ABS(X(12)-X(13))-13*ABS(X(12)-X(14))-10*ABS(X(12)-X(15))-10*ABS(X(12)-X(16))
1647 PR12=-19*ABS(X(13)-X(14))-4*ABS(X(13)-X(15))-10*ABS(X(13)-X(16))-20*ABS(X(14)-X(15))-0*ABS(X(14)-X(16))-0*ABS(X(15)-X(16))
1650 P=PR1+PR2+PR3+PR4+PR5+PR8+PR9+PR10+PR11+PR12-999*SUMTL
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 16
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1662 MM=PR1+PR2+PR3+PR4+PR5+PR7+PR8+PR9+PR10+PR11+PR12
1666 GOTO 128
1670 NEXT I
1890 IF M>-64525! THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),A(9),A(10)
1915 PRINT A(11),A(12),A(13),A(14)
1916 PRINT A(15),A(16),MM,M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, and the best candidate solution produced through eleven hours of running is presented below. What immediately follows is a manual copy of this solution from the computer screen.

645 764 765 654 884
764 764 875 483 563
463 563 563 683
783 503 -62151 -62151 -28497

Interpreted in accordance with line 1912 through line 1916, this candidate solution was produced through eleven hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter, which is not a compiler.

References

G. C. Armour and E. S. Buffa, "A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities," Management Science 9, 294-309 (1963).

S. S. Heragu. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.

A. R. S. Amaral, "An Exact Approach to the One-Dimensional Facility Layout Problem," Operations Research 56, 1026-1033 (2008).

A Computer Program for Relative Location of Unequal Rectangular Facilities

Jsun Yui Wong

The complete computer program listed below seeks to solve an eight-department layout problem (Armour and Buffa, 1963). The departmment sizes for department 1 through department 8 are 25x20, 25x20, 35x30, 30x20, 35x20, 60x40, 40x10, and 20x10, respectively; the interdepartmental flows are shown in line 1624 through line 1647 of the following program. The sizes and flows of the first five departments are from Heragu (2008, page 220). Most of the other given flows are based on those of Amaral (2008, page 1032). In order to have integer solutions, these original lengths and widths are multiplied by 4; then these longer lengths and widths are used in line 291 through line 417 of the following program.

0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466),HS(99)
6 DIM T(11,11,5),TZ(11,11),TL(33)
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 16
88 A(I)=FIX(RND*1000)
89 NEXT I
126 IMAR=10+FIX(RND*20000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 16
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*16)
234 X(IJL)=FIX(RND*1000)
291 HS(1)=ABS(X(1)-X(2))-100
292 HS(2)=ABS(X(1)-X(3))-120
293 HS(3)=ABS(X(1)-X(4))-110
294 HS(4)=ABS(X(1)-X(5))-120
295 HS(5)=ABS(X(1)-X(6))-170
296 HS(6)=ABS(X(1)-X(7))-130
297 HS(7)=ABS(X(1)-X(8))-90
307 HS(8)=ABS(X(2)-X(3))-120
308 HS(9)=ABS(X(2)-X(4))-110
309 HS(10)=ABS(X(2)-X(5))-120
310 HS(11)=ABS(X(2)-X(6))-170
311 HS(12)=ABS(X(2)-X(7))-130
312 HS(13)=ABS(X(2)-X(8))-90
322 HS(14)=ABS(X(3)-X(4))-130
323 HS(15)=ABS(X(3)-X(5))-140
324 HS(16)=ABS(X(3)-X(6))-190
325 HS(17)=ABS(X(3)-X(7))-150
326 HS(18)=ABS(X(3)-X(8))-110
336 HS(19)=ABS(X(4)-X(5))-130
337 HS(20)=ABS(X(4)-X(6))-180
338 HS(21)=ABS(X(4)-X(7))-140
339 HS(22)=ABS(X(4)-X(8))-100
349 HS(23)=ABS(X(5)-X(6))-190
350 HS(24)=ABS(X(5)-X(7))-150
351 HS(25)=ABS(X(5)-X(8))-110
369 HS(26)=ABS(X(6)-X(7))-200
370 HS(27)=ABS(X(6)-X(8))-160
371 HS(28)=ABS(X(7)-X(8))-120
383 HS(29)=ABS(X(9)-X(10))-80
384 HS(30)=ABS(X(9)-X(11))-100
385 HS(31)=ABS(X(9)-X(12))-80
386 HS(32)=ABS(X(9)-X(13))-80
387 HS(33)=ABS(X(9)-X(14))-120
388 HS(34)=ABS(X(9)-X(15))-60
389 HS(35)=ABS(X(9)-X(16))-60
391 HS(36)=ABS(X(10)-X(11))-100
392 HS(37)=ABS(X(10)-X(12))-80
393 HS(38)=ABS(X(10)-X(13))-80
394 HS(39)=ABS(X(10)-X(14))-120
395 HS(40)=ABS(X(10)-X(15))-60
396 HS(41)=ABS(X(10)-X(16))-60
401 HS(42)=ABS(X(11)-X(12))-100
402 HS(43)=ABS(X(11)-X(13))-100
403 HS(44)=ABS(X(11)-X(14))-140
404 HS(45)=ABS(X(11)-X(15))-80
405 HS(46)=ABS(X(11)-X(16))-80
406 HS(47)=ABS(X(12)-X(13))-80
407 HS(48)=ABS(X(12)-X(14))-120
408 HS(49)=ABS(X(12)-X(15))-60
409 HS(50)=ABS(X(12)-X(16))-60
412 HS(51)=ABS(X(13)-X(14))-120
413 HS(52)=ABS(X(13)-X(15))-60
414 HS(53)=ABS(X(13)-X(16))-60
415 HS(54)=ABS(X(14)-X(15))-100
416 HS(55)=ABS(X(14)-X(16))-100
417 HS(56)=ABS(X(15)-X(16))-40
551 IF HS(1)<-.0001 AND HS(29)<-.0001 THEN TL(1)=999999! ELSE TL(1)=0
553 IF HS(2)<-.0001 AND HS(30)<-.0001 THEN TL(2)=999999! ELSE TL(2)=0
554 IF HS(3)<-.0001 AND HS(31)<-.0001 THEN TL(3)=999999! ELSE TL(3)=0
555 IF HS(4)<-.0001 AND HS(32)<-.0001 THEN TL(4)=999999! ELSE TL(4)=0
557 IF HS(5)<-.0001 AND HS(33)<-.0001 THEN TL(5)=999999! ELSE TL(5)=0
559 IF HS(6)<-.0001 AND HS(34)<-.0001 THEN TL(6)=999999! ELSE TL(6)=0
560 IF HS(7)<-.0001 AND HS(35)<-.0001 THEN TL(7)=999999! ELSE TL(7)=0
565 IF HS(8)<-.0001 AND HS(36)<-.0001 THEN TL(8)=999999! ELSE TL(8)=0
568 IF HS(9)<-.0001 AND HS(37)<-.0001 THEN TL(9)=999999! ELSE TL(9)=0
569 IF HS(10)<-.0001 AND HS(38)<-.0001 THEN TL(10)=999999! ELSE TL(10)=0
581 IF HS(11)<-.0001 AND HS(39)<-.0001 THEN TL(10)=999999! ELSE TL(11)=0
582 IF HS(12)<-.0001 AND HS(40)<-.0001 THEN TL(10)=999999! ELSE TL(12)=0
583 IF HS(13)<-.0001 AND HS(41)<-.0001 THEN TL(10)=999999! ELSE TL(13)=0
584 IF HS(14)<-.0001 AND HS(42)<-.0001 THEN TL(10)=999999! ELSE TL(14)=0
585 IF HS(15)<-.0001 AND HS(43)<-.0001 THEN TL(10)=999999! ELSE TL(15)=0
586 IF HS(16)<-.0001 AND HS(44)<-.0001 THEN TL(10)=999999! ELSE TL(16)=0
587 IF HS(17)<-.0001 AND HS(45)<-.0001 THEN TL(10)=999999! ELSE TL(17)=0
588 IF HS(18)<-.0001 AND HS(46)<-.0001 THEN TL(10)=999999! ELSE TL(18)=0
589 IF HS(19)<-.0001 AND HS(47)<-.0001 THEN TL(10)=999999! ELSE TL(19)=0
590 IF HS(20)<-.0001 AND HS(48)<-.0001 THEN TL(10)=999999! ELSE TL(20)=0
591 IF HS(21)<-.0001 AND HS(49)<-.0001 THEN TL(10)=999999! ELSE TL(21)=0
592 IF HS(22)<-.0001 AND HS(50)<-.0001 THEN TL(10)=999999! ELSE TL(22)=0
593 IF HS(23)<-.0001 AND HS(51)<-.0001 THEN TL(10)=999999! ELSE TL(23)=0
594 IF HS(24)<-.0001 AND HS(52)<-.0001 THEN TL(10)=999999! ELSE TL(24)=0
595 IF HS(25)<-.0001 AND HS(53)<-.0001 THEN TL(10)=999999! ELSE TL(25)=0
596 IF HS(26)<-.0001 AND HS(54)<-.0001 THEN TL(10)=999999! ELSE TL(26)=0
597 IF HS(27)<-.0001 AND HS(55)<-.0001 THEN TL(10)=999999! ELSE TL(27)=0
598 IF HS(28)<-.0001 AND HS(56)<-.0001 THEN TL(10)=999999! ELSE TL(28)=0
1611 SUMTL=0
1613 FOR IR=1 TO 28
1615 SUMTL=SUMTL+TL(IR)
1618 NEXT IR
1621 PR1=-10*ABS(X(1)-X(2))-15*ABS(X(1)-X(3))-20*ABS(X(1)-X(4))-0*ABS(X(1)-X(5))-17*ABS(X(1)-X(6))-0*ABS(X(1)-X(7))-6*ABS(X(1)-X(8))
1622 PR2=-30*ABS(X(2)-X(3))-35*ABS(X(2)-X(4))-10*ABS(X(2)-X(5))-32*ABS(X(2)-X(6))-10*ABS(X(2)-X(7))-2*ABS(X(2)-X(8))
1631 PR3=-10*ABS(X(3)-X(4))-20*ABS(X(3)-X(5))-26*ABS(X(3)-X(6))-0*ABS(X(3)-X(7))-10*ABS(X(3)-X(8))
1632 PR4=-15*ABS(X(4)-X(5))-13*ABS(X(4)-X(6))-10*ABS(X(4)-X(7))-10*ABS(X(4)-X(8))
1633 PR5=-19*ABS(X(5)-X(6))-4*ABS(X(5)-X(7))-10*ABS(X(5)-X(8))-20*ABS(X(6)-X(7))-0*ABS(X(6)-X(8))-0*ABS(X(7)-X(8))
1636 REM
1643 PR8=-10*ABS(X(9)-X(10))-15*ABS(X(9)-X(11))-20*ABS(X(9)-X(12))-0*ABS(X(9)-X(13))-17*ABS(X(9)-X(14))-0*ABS(X(9)-X(15))-6*ABS(X(9)-X(16))
1644 PR9=-30*ABS(X(10)-X(11))-35*ABS(X(10)-X(12))-10*ABS(X(10)-X(13))-32*ABS(X(10)-X(14))-10*ABS(X(10)-X(15))-2*ABS(X(10)-X(16))
1645 PR10=-10*ABS(X(11)-X(12))-20*ABS(X(11)-X(13))-26*ABS(X(11)-X(14))-0*ABS(X(11)-X(15))-10*ABS(X(11)-X(16))
1646 PR11=-15*ABS(X(12)-X(13))-13*ABS(X(12)-X(14))-10*ABS(X(12)-X(15))-10*ABS(X(12)-X(16))
1647 PR12=-19*ABS(X(13)-X(14))-4*ABS(X(13)-X(15))-10*ABS(X(13)-X(16))-20*ABS(X(14)-X(15))-0*ABS(X(14)-X(16))-0*ABS(X(15)-X(16))
1650 P=PR1+PR2+PR3+PR4+PR5+PR8+PR9+PR10+PR11+PR12-999*SUMTL
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 16
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1662 MM=PR1+PR2+PR3+PR4+PR5+PR7+PR8+PR9+PR10+PR11+PR12
1666 GOTO 128
1670 NEXT I
1890 IF M>-63333! THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),A(9),A(10)
1915 PRINT A(11),A(12),A(13),A(14)
1916 PRINT A(15),A(16),MM,M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, and the output through sixteen hours of running is presented below. What immediately follows is a manual copy from the computer screen.

951 851 863 741 723
851 851 741 293 293
393 293 374 133
233 434 -63142 -63142 -29900

283 383 346 493 486
383 383 486 345 345
245 345 265 465
565 205 -62945 -62945 -26755

Interpreted in accordance with line 1912 through line 1916, this output was produced through sixteen hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter, which is not a compiler.

References

G. C. Armour and E. S. Buffa, "A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities," Management Science 9, 294-309 (1963).

S. S. Heragu. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.

A. R. S. Amaral, "An Exact Approach to the One-Dimensional Facility Layout Problem," Operations Research 56, 1026-1033 (2008).

A Computer Program for Relative Location of Facilities

Jsun Yui Wong

The complete computer program listed below seeks to solve a seven-department layout problem (Armour and Buffa, 1963). The departmment sizes for department 1 through department 7 are 25x20, 25x20, 35x30, 30x20, 35x20, 60x40, and 40x10, respectively; the interdepartmental flows are shown in line 1624 through line 1646 of the following program. The sizes and flows of the first five departments are from Heragu (2008, page 220). The 1-6, 2-6, 3-6, 4-6, 5-6, 1-7, 2-7, 3-7, 4-7, 5-7, and 6-7 flows are 17, 32, 26, 13 19, 0, 10, 0, 10, 4, and 20, respectively. In order to have integer solutions, these original lengths and widths are multiplied by 4. These longer lengths and widths are used in line 391 through line 435 of the following program.

0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466),HS(99)
6 DIM T(11,11,5),TZ(11,11),TL(22)
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 14
88 A(I)=FIX(RND*1000)
89 NEXT I
126 IMAR=10+FIX(RND*20000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 14
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*14)
234 X(IJL)=FIX(RND*1000)
391 HS(1)=ABS(X(1)-X(2))-100
392 HS(2)=ABS(X(1)-X(3))-120
393 HS(3)=ABS(X(1)-X(4))-110
394 HS(4)=ABS(X(1)-X(5))-120
395 HS(5)=ABS(X(1)-X(6))-170
396 HS(6)=ABS(X(1)-X(7))-130
397 HS(7)=ABS(X(2)-X(3))-120
398 HS(8)=ABS(X(2)-X(4))-110
399 HS(9)=ABS(X(2)-X(5))-120
400 HS(10)=ABS(X(2)-X(6))-170
401 HS(11)=ABS(X(2)-X(7))-130
402 HS(12)=ABS(X(3)-X(4))-130
403 HS(13)=ABS(X(3)-X(5))-140
404 HS(14)=ABS(X(3)-X(6))-190
405 HS(15)=ABS(X(3)-X(7))-150
406 HS(16)=ABS(X(4)-X(5))-130
407 HS(17)=ABS(X(4)-X(6))-180
408 HS(18)=ABS(X(4)-X(7))-140
409 HS(19)=ABS(X(5)-X(6))-190
410 HS(20)=ABS(X(5)-X(7))-150
411 HS(21)=ABS(X(6)-X(7))-200
412 HS(22)=ABS(X(8)-X(9))-80
413 HS(23)=ABS(X(8)-X(10))-100
414 HS(24)=ABS(X(8)-X(11))-80
415 HS(25)=ABS(X(8)-X(12))-80
416 HS(26)=ABS(X(8)-X(13))-120
417 HS(27)=ABS(X(8)-X(14))-60
418 HS(28)=ABS(X(9)-X(10))-100
419 HS(29)=ABS(X(9)-X(11))-80
420 HS(30)=ABS(X(9)-X(12))-80
421 HS(31)=ABS(X(9)-X(13))-120
422 HS(32)=ABS(X(9)-X(14))-60
423 HS(33)=ABS(X(10)-X(11))-100
424 HS(34)=ABS(X(10)-X(12))-100
425 HS(35)=ABS(X(10)-X(13))-140
426 HS(36)=ABS(X(10)-X(14))-80
427 HS(37)=ABS(X(11)-X(12))-80
431 HS(38)=ABS(X(11)-X(13))-120
432 HS(39)=ABS(X(11)-X(14))-60
433 HS(40)=ABS(X(12)-X(13))-120
434 HS(41)=ABS(X(12)-X(14))-60
435 HS(42)=ABS(X(13)-X(14))-100
551 IF HS(1)<-.0001 AND HS(22)<-.0001 THEN TL(1)=999999! ELSE TL(1)=0
553 IF HS(2)<-.0001 AND HS(23)<-.0001 THEN TL(2)=999999! ELSE TL(2)=0
554 IF HS(3)<-.0001 AND HS(24)<-.0001 THEN TL(3)=999999! ELSE TL(3)=0
555 IF HS(4)<-.0001 AND HS(25)<-.0001 THEN TL(4)=999999! ELSE TL(4)=0
557 IF HS(5)<-.0001 AND HS(26)<-.0001 THEN TL(5)=999999! ELSE TL(5)=0
559 IF HS(6)<-.0001 AND HS(27)<-.0001 THEN TL(6)=999999! ELSE TL(6)=0
560 IF HS(7)<-.0001 AND HS(28)<-.0001 THEN TL(7)=999999! ELSE TL(7)=0
565 IF HS(8)<-.0001 AND HS(29)<-.0001 THEN TL(8)=999999! ELSE TL(8)=0
568 IF HS(9)<-.0001 AND HS(30)<-.0001 THEN TL(9)=999999! ELSE TL(9)=0
569 IF HS(10)<-.0001 AND HS(31)<-.0001 THEN TL(10)=999999! ELSE TL(10)=0
581 IF HS(11)<-.0001 AND HS(32)<-.0001 THEN TL(10)=999999! ELSE TL(11)=0
582 IF HS(12)<-.0001 AND HS(33)<-.0001 THEN TL(10)=999999! ELSE TL(12)=0
583 IF HS(13)<-.0001 AND HS(34)<-.0001 THEN TL(10)=999999! ELSE TL(13)=0
584 IF HS(14)<-.0001 AND HS(35)<-.0001 THEN TL(10)=999999! ELSE TL(14)=0
585 IF HS(15)<-.0001 AND HS(36)<-.0001 THEN TL(10)=999999! ELSE TL(15)=0
586 IF HS(16)<-.0001 AND HS(37)<-.0001 THEN TL(10)=999999! ELSE TL(16)=0
587 IF HS(17)<-.0001 AND HS(38)<-.0001 THEN TL(10)=999999! ELSE TL(17)=0
588 IF HS(18)<-.0001 AND HS(39)<-.0001 THEN TL(10)=999999! ELSE TL(18)=0
589 IF HS(19)<-.0001 AND HS(40)<-.0001 THEN TL(10)=999999! ELSE TL(19)=0
590 IF HS(20)<-.0001 AND HS(41)<-.0001 THEN TL(10)=999999! ELSE TL(20)=0
591 IF HS(21)<-.0001 AND HS(42)<-.0001 THEN TL(10)=999999! ELSE TL(21)=0
1611 SUMTL=0
1613 FOR IR=1 TO 21
1615 SUMTL=SUMTL+TL(IR)
1618 NEXT IR
1621 PR1=-10*ABS(X(1)-X(2))-15*ABS(X(1)-X(3))-20*ABS(X(1)-X(4))-0*ABS(X(1)-X(5))-17*ABS(X(1)-X(6))-0*ABS(X(1)-X(7))
1622 PR2=-30*ABS(X(2)-X(3))-35*ABS(X(2)-X(4))-10*ABS(X(2)-X(5))-32*ABS(X(2)-X(6))-10*ABS(X(2)-X(7))
1631 PR3=-10*ABS(X(3)-X(4))-20*ABS(X(3)-X(5))-26*ABS(X(3)-X(6))-0*ABS(X(3)-X(7))
1632 PR4=-15*ABS(X(4)-X(5))-13*ABS(X(4)-X(6))-10*ABS(X(4)-X(7))
1633 PR5=-19*ABS(X(5)-X(6))-4*ABS(X(5)-X(7))-20*ABS(X(6)-X(7))
1636 REM
1637 PR7=-10*ABS(X(8)-X(9))-15*ABS(X(8)-X(10))-20*ABS(X(8)-X(11))-0*ABS(X(8)-X(12))-17*ABS(X(8)-X(13))-0*ABS(X(8)-X(14))
1643 PR8=-30*ABS(X(9)-X(10))-35*ABS(X(9)-X(11))-10*ABS(X(9)-X(12))-32*ABS(X(9)-X(13))-10*ABS(X(9)-X(14))
1644 PR9=-10*ABS(X(10)-X(11))-20*ABS(X(10)-X(12))-26*ABS(X(10)-X(13))-0*ABS(X(10)-X(14))
1645 PR10=-15*ABS(X(11)-X(12))-13*ABS(X(11)-X(13))-10*ABS(X(11)-X(14))
1646 PR11=-19*ABS(X(12)-X(13))-4*ABS(X(12)-X(14))-20*ABS(X(13)-X(14))
1650 P=PR1+PR2+PR3+PR4+PR5+PR7+PR8+PR9+PR10+PR11-999*SUMTL
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 14
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1662 MM=PR1+PR2+PR3+PR4+PR5+PR7+PR8+PR9+PR10+PR11
1666 GOTO 128
1670 NEXT I
1890 IF M>-56000! THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),A(9),A(10)
1915 PRINT A(11),A(12),A(13),A(14)
1916 PRINT MM,M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, and the output through fourteen hours of running is presented below. What immediately follows is a manual copy from the computer screen.

641 751 761 641 871
751 751 660 740 640
740 740 860 960
-55300 -55300 -31227

232 352 352 242 472
352 352 202 282 182
282 282 402 502
-55310 -55310 -29831

223 343 343 233 464
343 343 435 515 415
515 515 635 736
-55422 -55422 -26997

Interpreted in accordance with line 1912 through line 1916, this output was produced through fourteen hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter, which is not a compiler.

References

G. C. Armour and E. S. Buffa, "A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities," Management Science 9, 294-309 (1963).

S. S. Heragu. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.

An Integer-Programming Computer Program Applied to a Space Allocation Problem, Second Edition

Jsun Yui Wong

The complete computer program listed below seeks to solve a five-department space allocation problem (Armour and Buffa, 1963). The departmment sizes for department 1 through department 5 are 25x20, 25x20, 35x30, 30x20, and 35x20, respectively; the interdepartmental flows are shown in line 1624, line 1625, and line 1626 of the following program. These sizes and flows are from Heragu (2008, page 220).

0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466),HS(99)
6 DIM T(11,11,5),TZ(11,11),TL(11)
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 10
88 A(I)=(RND*240)
89 NEXT I
126 IMAR=10+FIX(RND*20000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 10
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*10)
234 X(IJL)=(RND*240)
401 HS(1)=ABS(X(1)-X(2))-25
402 HS(2)=ABS(X(1)-X(3))-30
403 HS(3)=ABS(X(1)-X(4))-27.5
404 HS(4)=ABS(X(1)-X(5))-30
405 HS(5)=ABS(X(2)-X(3))-30
406 HS(6)=ABS(X(2)-X(4))-27.5
407 HS(7)=ABS(X(2)-X(5))-30
409 HS(9)=ABS(X(3)-X(4))-32.5
410 HS(10)=ABS(X(3)-X(5))-35
411 HS(11)=ABS(X(4)-X(5))-32.5
413 HS(13)=ABS(X(6)-X(7))-20
414 HS(14)=ABS(X(6)-X(8))-25
415 HS(15)=ABS(X(6)-X(9))-20
416 HS(16)=ABS(X(6)-X(10))-20
417 HS(17)=ABS(X(7)-X(8))-25
418 HS(18)=ABS(X(7)-X(9))-20
419 HS(19)=ABS(X(7)-X(10))-20
420 HS(20)=ABS(X(8)-X(9))-25
421 HS(21)=ABS(X(8)-X(10))-25
422 HS(22)=ABS(X(9)-X(10))-20
551 IF HS(1)<-.0001 AND HS(13)<-.0001 THEN TL(1)=999999! ELSE TL(1)=0
553 IF HS(2)<-.0001 AND HS(14)<-.0001 THEN TL(2)=999999! ELSE TL(2)=0
554 IF HS(3)<-.0001 AND HS(15)<-.0001 THEN TL(3)=999999! ELSE TL(3)=0
555 IF HS(4)<-.0001 AND HS(16)<-.0001 THEN TL(4)=999999! ELSE TL(4)=0
557 IF HS(5)<-.0001 AND HS(17)<-.0001 THEN TL(5)=999999! ELSE TL(5)=0
559 IF HS(6)<-.0001 AND HS(18)<-.0001 THEN TL(6)=999999! ELSE TL(6)=0
560 IF HS(7)<-.0001 AND HS(19)<-.0001 THEN TL(7)=999999! ELSE TL(7)=0
565 IF HS(9)<-.0001 AND HS(20)<-.0001 THEN TL(8)=999999! ELSE TL(8)=0
568 IF HS(10)<-.0001 AND HS(21)<-.0001 THEN TL(9)=999999! ELSE TL(9)=0
569 IF HS(11)<-.0001 AND HS(22)<-.0001 THEN TL(10)=999999! ELSE TL(10)=0
1611 SUMTL=0
1613 FOR IR=1 TO 10
1615 SUMTL=SUMTL+TL(IR)
1618 NEXT IR
1624 PR1=-10*ABS(X(1)-X(2))-15*ABS(X(1)-X(3))-20*ABS(X(1)-X(4))-0*ABS(X(1)-X(5))-30*ABS(X(2)-X(3))-35*ABS(X(2)-X(4))-10*ABS(X(2)-X(5))
1625 PR2=-10*ABS(X(3)-X(4))-20*ABS(X(3)-X(5))-15*ABS(X(4)-X(5))-10*ABS(X(6)-X(7))-15*ABS(X(6)-X(8))-20*ABS(X(6)-X(9))-0*ABS(X(6)-X(10))
1626 PR3=-30*ABS(X(7)-X(8))-35*ABS(X(7)-X(9))-10*ABS(X(7)-X(10))-10*ABS(X(8)-X(9))-20*ABS(X(8)-X(10))-15*ABS(X(9)-X(10))
1650 P=PR1+PR2+PR3-999*SUMTL
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 10
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1662 MM=PR1+PR2+PR3
1666 GOTO 128
1670 NEXT I
1890 IF M>-5700 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),A(9),A(10)
1915 PRINT MM,M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, and the best candidate solution produced in seventeen hours of running is presented below. What immediately follows is a manual copy from the computer screen.

61.23445 91.06744 91.24085 63.56475 91.0558
25.93895 45.94308 20.93797 45.9476 65.97519
-5532.89 -5532.89 -24225

Interpreted in accordance with line 1912 through line 1915, this solution was produced in the first seventeen hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter, which is not a compiler.

References

G. C. Armour and E. S. Buffa, "A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities," Management Science 9, 294-309 (1963).

S. S. Heragu. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.

A Computer Program for a Space Allocation Problem

Jsun Yui Wong

The complete computer program listed below seeks to solve a six-department space allocation problem (Armour and Buffa, 1963). The departmment sizes for department 1 through department 6 are 25x20, 25x20, 35x30, 30x20, 35x20, and 60x40, respectively; the interdepartmental flows are shown in line 1624 through line 1627 of the following program. The sizes and flows of the first five departments are from Heragu (2008). The 1-6, 2-6, 3-6, 4-6, and 5-6 flows are 17, 32, 26, 13, and 19, respectively.

0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466),HS(99)
6 DIM T(11,11,5),TZ(11,11),TL(22)
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 12
88 A(I)=(RND*240)
89 NEXT I
126 IMAR=10+FIX(RND*20000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 12
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*12)
234 X(IJL)=(RND*240)
391 HS(1)=ABS(X(1)-X(2))-25
392 HS(2)=ABS(X(1)-X(3))-30
393 HS(3)=ABS(X(1)-X(4))-27.5
394 HS(4)=ABS(X(1)-X(5))-30
395 HS(5)=ABS(X(1)-X(6))-42.5
405 HS(6)=ABS(X(2)-X(3))-30
406 HS(7)=ABS(X(2)-X(4))-27.5
407 HS(8)=ABS(X(2)-X(5))-30
408 HS(9)=ABS(X(2)-X(6))-42.5
409 HS(10)=ABS(X(3)-X(4))-32.5
410 HS(11)=ABS(X(3)-X(5))-35
411 HS(12)=ABS(X(3)-X(6))-47.5
412 HS(13)=ABS(X(4)-X(5))-32.5
413 HS(14)=ABS(X(4)-X(6))-45
414 HS(15)=ABS(X(5)-X(6))-47.5
415 HS(16)=ABS(X(7)-X(8))-20
416 HS(17)=ABS(X(7)-X(9))-25
417 HS(18)=ABS(X(7)-X(10))-20
418 HS(19)=ABS(X(7)-X(11))-20
419 HS(20)=ABS(X(7)-X(12))-30
420 HS(21)=ABS(X(8)-X(9))-25
421 HS(22)=ABS(X(8)-X(10))-20
422 HS(23)=ABS(X(8)-X(11))-20
423 HS(24)=ABS(X(8)-X(12))-30
424 HS(25)=ABS(X(9)-X(10))-25
425 HS(26)=ABS(X(9)-X(11))-25
426 HS(27)=ABS(X(9)-X(12))-35
427 HS(28)=ABS(X(10)-X(11))-20
431 HS(29)=ABS(X(10)-X(12))-30
432 HS(30)=ABS(X(11)-X(12))-30
551 IF HS(1)<-.0001 AND HS(16)<-.0001 THEN TL(1)=999999! ELSE TL(1)=0
553 IF HS(2)<-.0001 AND HS(17)<-.0001 THEN TL(2)=999999! ELSE TL(2)=0
554 IF HS(3)<-.0001 AND HS(18)<-.0001 THEN TL(3)=999999! ELSE TL(3)=0
555 IF HS(4)<-.0001 AND HS(19)<-.0001 THEN TL(4)=999999! ELSE TL(4)=0
557 IF HS(5)<-.0001 AND HS(20)<-.0001 THEN TL(5)=999999! ELSE TL(5)=0
559 IF HS(6)<-.0001 AND HS(21)<-.0001 THEN TL(6)=999999! ELSE TL(6)=0
560 IF HS(7)<-.0001 AND HS(22)<-.0001 THEN TL(7)=999999! ELSE TL(7)=0
565 IF HS(8)<-.0001 AND HS(23)<-.0001 THEN TL(8)=999999! ELSE TL(8)=0
568 IF HS(9)<-.0001 AND HS(24)<-.0001 THEN TL(9)=999999! ELSE TL(9)=0
569 IF HS(10)<-.0001 AND HS(25)<-.0001 THEN TL(10)=999999! ELSE TL(10)=0
581 IF HS(11)<-.0001 AND HS(26)<-.0001 THEN TL(10)=999999! ELSE TL(11)=0
582 IF HS(12)<-.0001 AND HS(27)<-.0001 THEN TL(10)=999999! ELSE TL(12)=0
583 IF HS(13)<-.0001 AND HS(28)<-.0001 THEN TL(10)=999999! ELSE TL(13)=0
584 IF HS(14)<-.0001 AND HS(29)<-.0001 THEN TL(10)=999999! ELSE TL(14)=0
585 IF HS(15)<-.0001 AND HS(30)<-.0001 THEN TL(10)=999999! ELSE TL(15)=0
1611 SUMTL=0
1613 FOR IR=1 TO 15
1615 SUMTL=SUMTL+TL(IR)
1618 NEXT IR
1624 PR1=-10*ABS(X(1)-X(2))-15*ABS(X(1)-X(3))-20*ABS(X(1)-X(4))-0*ABS(X(1)-X(5))-17*ABS(X(1)-X(6))-30*ABS(X(2)-X(3))-35*ABS(X(2)-X(4))-10*ABS(X(2)-X(5))-32*ABS(X(2)-X(6))
1625 PR2=-10*ABS(X(3)-X(4))-20*ABS(X(3)-X(5))-26*ABS(X(3)-X(6))-15*ABS(X(4)-X(5))-13*ABS(X(4)-X(6))-19*ABS(X(5)-X(6))-10*ABS(X(7)-X(8))-15*ABS(X(7)-X(9))-20*ABS(X(7)-X(10))-0*ABS(X(7)-X(11))
1626 PR3=-17*ABS(X(7)-X(12))-30*ABS(X(8)-X(9))-35*ABS(X(8)-X(10))-10*ABS(X(8)-X(11))-32*ABS(X(8)-X(12))-10*ABS(X(9)-X(10))
1627 PR4=-20*ABS(X(9)-X(11))-26*ABS(X(9)-X(12))-15*ABS(X(10)-X(11))-13*ABS(X(10)-X(12))-19*ABS(X(11)-X(12))
1650 P=PR1+PR2+PR3+PR4-999*SUMTL
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 12
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1662 MM=PR1+PR2+PR3+PR4
1666 GOTO 128
1670 NEXT I
1890 IF M>-11639 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),A(9),A(10)
1915 PRINT A(11),A(12),MM,M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, and the output produced in thirteen hours of running is presented below. What immediately follows is a manual copy from the computer screen.

136.2185 165.1701 166.2257 137.6041 195.1733
165.2049 53.04271 33.03552 58.10423 33.0356
33.01572 2.968483 -11631.06 -11631.06 -31438

155.788 126.4413 125.7753 153.9702 96.41533
126.3579 62.67572 82.73879 57.66229 82.73458
82.69295 112.7742 -11631.88 -11631.88 -30257

98.17766 128.1517 128.1806 100.6427 158.2056
128.1536 87.69828 107.7177 82.69673 107.7191
107.7014 137.7372 -11621.93 -11621.93 -27712

Interpreted in accordance with line 1912 through line 1915, the output through JJJJ=-27712 was produced during the first thirteen hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter, which is not a compiler.

References

G. C. Armour and E. S. Buffa, "A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities," Management Science 9, 294-309 (1963).

S. S. Heragu. Facilities Design, Third Edition. CRC Press, 2008.

An Integer-Programming Computer Program Applied to a Space Allocation Problem

Jsun Yui Wong

The complete computer program listed below seeks to solve a five-department space allocation problem (Armour and Buffa, 1963). The departmment sizes for department 1 through department 5 are 25x20, 25x20, 35x30, 30x20, and 35x20, respectively; the interdepartmental flows are shown in line 1624, line 1625, and line 1626 of the following program. These sizes and flows are from Heragu (2008).

0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466),HS(99)
6 DIM T(11,11,5),TZ(11,11),TL(11)
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 10
88 A(I)=FIX(RND*240)
89 NEXT I
126 IMAR=10+FIX(RND*20000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 10
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*10)
234 X(IJL)=FIX(RND*240)
401 HS(1)=ABS(X(1)-X(2))-25
402 HS(2)=ABS(X(1)-X(3))-30
403 HS(3)=ABS(X(1)-X(4))-27.5
404 HS(4)=ABS(X(1)-X(5))-30
405 HS(5)=ABS(X(2)-X(3))-30
406 HS(6)=ABS(X(2)-X(4))-27.5
407 HS(7)=ABS(X(2)-X(5))-30
409 HS(9)=ABS(X(3)-X(4))-32.5
410 HS(10)=ABS(X(3)-X(5))-35
411 HS(11)=ABS(X(4)-X(5))-32.5
413 HS(13)=ABS(X(6)-X(7))-20
414 HS(14)=ABS(X(6)-X(8))-25
415 HS(15)=ABS(X(6)-X(9))-20
416 HS(16)=ABS(X(6)-X(10))-20
417 HS(17)=ABS(X(7)-X(8))-25
418 HS(18)=ABS(X(7)-X(9))-20
419 HS(19)=ABS(X(7)-X(10))-20
420 HS(20)=ABS(X(8)-X(9))-25
421 HS(21)=ABS(X(8)-X(10))-25
422 HS(22)=ABS(X(9)-X(10))-20
551 IF HS(1)<-.0001 AND HS(13)<-.0001 THEN TL(1)=999999! ELSE TL(1)=0
553 IF HS(2)<-.0001 AND HS(14)<-.0001 THEN TL(2)=999999! ELSE TL(2)=0
554 IF HS(3)<-.0001 AND HS(15)<-.0001 THEN TL(3)=999999! ELSE TL(3)=0
555 IF HS(4)<-.0001 AND HS(16)<-.0001 THEN TL(4)=999999! ELSE TL(4)=0
557 IF HS(5)<-.0001 AND HS(17)<-.0001 THEN TL(5)=999999! ELSE TL(5)=0
559 IF HS(6)<-.0001 AND HS(18)<-.0001 THEN TL(6)=999999! ELSE TL(6)=0
560 IF HS(7)<-.0001 AND HS(19)<-.0001 THEN TL(7)=999999! ELSE TL(7)=0
565 IF HS(9)<-.0001 AND HS(20)<-.0001 THEN TL(8)=999999! ELSE TL(8)=0
568 IF HS(10)<-.0001 AND HS(21)<-.0001 THEN TL(9)=999999! ELSE TL(9)=0
569 IF HS(11)<-.0001 AND HS(22)<-.0001 THEN TL(10)=999999! ELSE TL(10)=0
1611 SUMTL=0
1613 FOR IR=1 TO 10
1615 SUMTL=SUMTL+TL(IR)
1618 NEXT IR
1624 PR1=-10*ABS(X(1)-X(2))-15*ABS(X(1)-X(3))-20*ABS(X(1)-X(4))-0*ABS(X(1)-X(5))-30*ABS(X(2)-X(3))-35*ABS(X(2)-X(4))-10*ABS(X(2)-X(5))
1625 PR2=-10*ABS(X(3)-X(4))-20*ABS(X(3)-X(5))-15*ABS(X(4)-X(5))-10*ABS(X(6)-X(7))-15*ABS(X(6)-X(8))-20*ABS(X(6)-X(9))-0*ABS(X(6)-X(10))
1626 PR3=-30*ABS(X(7)-X(8))-35*ABS(X(7)-X(9))-10*ABS(X(7)-X(10))-10*ABS(X(8)-X(9))-20*ABS(X(8)-X(10))-15*ABS(X(9)-X(10))
1650 P=PR1+PR2+PR3-999*SUMTL
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 10
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1662 MM=PR1+PR2+PR3
1666 GOTO 128
1670 NEXT I
1890 IF M>-5700 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),A(9),A(10)
1915 PRINT MM,M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, and the best candidate solutions produced during the first 65 minutes of running are presented below. What immediately follows is a manual copy from the computer screen.

98 127 128 99 127
93 113 88 113 133
-5575 -5575 -31252

106 136 136 108 136
140 120 145 120 100
-5545 -5545 -30898

84 54 54 82 54
143 163 138 163 183
-5545 -5545 -30539

Interpreted in accordance with line 1912 through line 1915, the output through JJJJ=-30539 was produced during the first 65 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter, which is not a compiler.

References

G. C. Armour and E. S. Buffa, "A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities," Management Science 9, 294-309 (1963).

S. S. Heragu. Facilities Design, Third Edition. CRC Press, 2008.

A Complete Computer Program and Its Output for a Space Allocation Problem

Jsun Yui Wong

The complete computer program listed below seeks to solve a five-department space allocation problem (Armour and Buffa, 1963). The departmment sizes for department 1 through department 5 are 20x50, 30x40, 10x20, 60x70, and 40x50, respectively; the interdepartmental flows are shown in line 1624, line 1625, and line 1626 of the following program.

0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466),HS(99)
6 DIM T(11,11,5),TZ(11,11),TL(11)
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 10
88 A(I)=FIX(RND*240)
89 NEXT I
126 IMAR=10+FIX(RND*20000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 10
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*10)
234 X(IJL)=FIX(RND*240)
401 HS(1)=ABS(X(1)-X(2))-25
402 HS(2)=ABS(X(1)-X(3))-15
403 HS(3)=ABS(X(1)-X(4))-40
404 HS(4)=ABS(X(1)-X(5))-30
405 HS(5)=ABS(X(2)-X(3))-20
406 HS(6)=ABS(X(2)-X(4))-45
407 HS(7)=ABS(X(2)-X(5))-35
409 HS(9)=ABS(X(3)-X(4))-35
410 HS(10)=ABS(X(3)-X(5))-25
411 HS(11)=ABS(X(4)-X(5))-50
413 HS(13)=ABS(X(6)-X(7))-45
414 HS(14)=ABS(X(6)-X(8))-35
415 HS(15)=ABS(X(6)-X(9))-60
416 HS(16)=ABS(X(6)-X(10))-50
417 HS(17)=ABS(X(7)-X(8))-30
418 HS(18)=ABS(X(7)-X(9))-55
419 HS(19)=ABS(X(7)-X(10))-45
420 HS(20)=ABS(X(8)-X(9))-45
421 HS(21)=ABS(X(8)-X(10))-35
422 HS(22)=ABS(X(9)-X(10))-60
551 IF HS(1)<-.0001 AND HS(13)<-.0001 THEN TL(1)=999999! ELSE TL(1)=0
553 IF HS(2)<-.0001 AND HS(14)<-.0001 THEN TL(2)=999999! ELSE TL(2)=0
554 IF HS(3)<-.0001 AND HS(15)<-.0001 THEN TL(3)=999999! ELSE TL(3)=0
555 IF HS(4)<-.0001 AND HS(16)<-.0001 THEN TL(4)=999999! ELSE TL(4)=0
557 IF HS(5)<-.0001 AND HS(17)<-.0001 THEN TL(5)=999999! ELSE TL(5)=0
559 IF HS(6)<-.0001 AND HS(18)<-.0001 THEN TL(6)=999999! ELSE TL(6)=0
560 IF HS(7)<-.0001 AND HS(19)<-.0001 THEN TL(7)=999999! ELSE TL(7)=0
565 IF HS(9)<-.0001 AND HS(20)<-.0001 THEN TL(8)=999999! ELSE TL(8)=0
568 IF HS(10)<-.0001 AND HS(21)<-.0001 THEN TL(9)=999999! ELSE TL(9)=0
569 IF HS(11)<-.0001 AND HS(22)<-.0001 THEN TL(10)=999999! ELSE TL(10)=0
1611 SUMTL=0
1613 FOR IR=1 TO 10
1615 SUMTL=SUMTL+TL(IR)
1618 NEXT IR
1624 PR1=-111*ABS(X(1)-X(2))-222*ABS(X(1)-X(3))-110*ABS(X(1)-X(4))-340*ABS(X(1)-X(5))-88*ABS(X(2)-X(3))-260*ABS(X(2)-X(4))-70*ABS(X(2)-X(5))
1625 PR2=-250*ABS(X(3)-X(4))-90*ABS(X(3)-X(5))-280*ABS(X(4)-X(5))-111*ABS(X(6)-X(7))-222*ABS(X(6)-X(8))-110*ABS(X(6)-X(9))-340*ABS(X(6)-X(10))
1626 PR3=-88*ABS(X(7)-X(8))-260*ABS(X(7)-X(9))-70*ABS(X(7)-X(10))-250*ABS(X(8)-X(9))-90*ABS(X(8)-X(10))-280*ABS(X(9)-X(10))
1650 P=PR1+PR2+PR3-999*SUMTL
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 10
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1662 MM=PR1+PR2+PR3
1666 GOTO 128
1670 NEXT I
1890 IF M>-95555! THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),A(9),A(10)
1915 PRINT MM,M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, and the output produced during the first 25 minutes of running is presented below. What immediately follows is a manual copy from the computer screen.

113 78 98 33 143
54 54 54 54 54
-95325 -95325 -31788

73 108 88 153 43
85 85 85 85 85
-95325 -95325 -31737

105 140 120 185 75
186 186 186 186 186
-95325 -95325 -31597

158 63 143 108 188
137 137 137 137 137
-92265 -92265 -31584

146 141 131 96 176
90 45 90 90 90
-93620 -93620 -31427

143 238 158 193 113
167 167 167 167 167
-92265 -92265 -31402

Interpreted in accordance with line 1912 through line 1915, the output through JJJJ=-31402 was produced during the first 25 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter, which is not a compiler.

Reference

G. C. Armour and E. S. Buffa, "A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities," Management Science 9, 294-309 (1963).

A Computer Program and Its Output for a Small Space Allocation Problem

Jsun Yui Wong

The complete computer program listed below seeks to solve a small space allocation problem (Armour and Buffa, 1963). The departmment sizes for department 1 through department 4 are 20x50, 30x40, 10x20, and 60x70, respectively; the interdepartmental flows are shown in line 1624 of the following program.

0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466),HS(99)
6 DIM T(11,11,5),TZ(11,11),TL(11)
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 8
88 A(I)=FIX(RND*240)
89 NEXT I
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 8
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*8)
234 X(IJL)=FIX(RND*240)
401 HS(1)=ABS(X(1)-X(2))-25
402 HS(2)=ABS(X(1)-X(3))-15
403 HS(3)=ABS(X(1)-X(4))-40
405 HS(5)=ABS(X(2)-X(3))-20
406 HS(6)=ABS(X(2)-X(4))-45
409 HS(9)=ABS(X(3)-X(4))-35
413 HS(13)=ABS(X(5)-X(6))-45
414 HS(14)=ABS(X(5)-X(7))-35
415 HS(15)=ABS(X(5)-X(8))-60
417 HS(17)=ABS(X(6)-X(7))-30
418 HS(18)=ABS(X(6)-X(8))-55
421 HS(21)=ABS(X(7)-X(8))-45
551 IF HS(1)<-.0001 AND HS(13)<-.0001 THEN TL(1)=999999! ELSE TL(1)=0
553 IF HS(2)<-.0001 AND HS(14)<-.0001 THEN TL(2)=999999! ELSE TL(2)=0
554 IF HS(3)<-.0001 AND HS(15)<-.0001 THEN TL(3)=999999! ELSE TL(3)=0
557 IF HS(5)<-.0001 AND HS(17)<-.0001 THEN TL(4)=999999! ELSE TL(4)=0
559 IF HS(6)<-.0001 AND HS(18)<-.0001 THEN TL(5)=999999! ELSE TL(5)=0
561 IF HS(9)<-.0001 AND HS(21)<-.0001 THEN TL(6)=999999! ELSE TL(6)=0
1611 SUMTL=0
1613 FOR IR=1 TO 6
1615 SUMTL=SUMTL+TL(IR)
1618 NEXT IR
1624 PR1=-111*ABS(X(1)-X(2))-222*ABS(X(1)-X(3))-110*ABS(X(1)-X(4))-88*ABS(X(2)-X(3))-260*ABS(X(2)-X(4))-250*ABS(X(3)-X(4))-111*ABS(X(5)-X(6))-222*ABS(X(5)-X(7))-110*ABS(X(5)-X(8))-88*ABS(X(6)-X(7))-260*ABS(X(6)-X(8))-250*ABS(X(7)-X(8))
1650 P=PR1-999*SUMTL
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 8
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1662 MM=PR1
1666 GOTO 128
1670 NEXT I
1890 IF M>-45000! THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),MM,M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced during the first 2 minutes of running is presented below. What immediately follows is a manual copy from the computer screen.

199 224 184 149 98
98 98 98 -43375 -43375
-31973

97 124 81 46 185
185 185 185 -44973 -44973
-31962

180 155 195 231 103
102 103 103 -44454 -44454
-31933

166 191 151 116 14
14 14 14 -43375 -43375
-31919

Interpreted in accordance with line 1912 and line 1914, the output through JJJJ=-31919 was produced during the first 2 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

Reference

G. C. Armour and E. S. Buffa, "A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities," Management Science 9, 294-309 (1963).

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

Jsun Yui Wong

The complete computer program listed below seeks to solve Problem P17 of Amaral (2008), which is an instance of the allocation problem of Simmons (1969). In order to have integer locations, the department lengths used in the following computer program are twice as long as the original lengths.

0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466)
6 DIM T(33,33),TZ(33,33)
11 T(1,2)=23:T(1,3)=29:T(1,4)=23:T(1,5)=27:T(1,6)=23:T(1,7)=27:T(1,8)=25:T(1,9)=29:T(1,10)=26:T(1,11)=25:T(1,12)=23:T(1,13)=29:T(1,14)=23:T(1,15)=27
12 T(2,3)=12:T(2,4)=6:T(2,5)=10:T(2,6)=6:T(2,7)=10:T(2,8)=8:T(2,9)=12:T(2,10)=9:T(2,11)=8:T(2,12)=6:T(2,13)=12:T(2,14)=6:T(2,15)=10
13 T(3,4)=12:T(3,5)=16:T(3,6)=12:T(3,7)=16:T(3,8)=14:T(3,9)=18:T(3,10)=15:T(3,11)=14:T(3,12)=12:T(3,13)=18:T(3,14)=12:T(3,15)=16
14 T(4,5)=10:T(4,6)=6:T(4,7)=10:T(4,8)=8:T(4,9)=12:T(4,10)=9:T(4,11)=8:T(4,12)=6:T(4,13)=12:T(4,14)=6:T(4,15)=10
15 T(5,6)=10:T(5,7)=14:T(5,8)=12:T(5,9)=16:T(5,10)=13:T(5,11)=12:T(5,12)=10:T(5,13)=16:T(5,14)=10:T(5,15)=14
16 T(6,7)=10:T(6,8)=8:T(6,9)=12:T(6,10)=9:T(6,11)=8:T(6,12)=6:T(6,13)=12:T(6,14)=6:T(6,15)=10
17 T(7,8)=12:T(7,9)=16:T(7,10)=13:T(7,11)=12:T(7,12)=10:T(7,13)=16:T(7,14)=10:T(7,15)=14
18 T(8,9)=14:T(8,10)=11:T(8,11)=10:T(8,12)=8:T(8,13)=14:T(8,14)=8:T(8,15)=12
19 T(9,10)=15:T(9,11)=14:T(9,12)=12:T(9,13)=18:T(9,14)=12:T(9,15)=16
20 T(10,11)=11:T(10,12)=9:T(10,13)=15:T(10,14)=9:T(10,15)=13
21 T(11,12)=8:T(11,13)=14:T(11,14)=8:T(11,15)=12:T(12,13)=12:T(12,14)=6:T(12,15)=10:T(13,14)=12:T(13,15)=16:T(14,15)=10
31 T(1,16)=23:T(1,17)=27:T(2,16)=6:T(2,17)=10:T(3,16)=12:T(3,17)=16::T(4,16)=6:T(4,17)=10:T(5,16)=10:T(5,17)=14
32 T(6,16)=6:T(6,17)=10:T(7,16)=10:T(7,17)=14:T(8,16)=8:T(8,17)=12:T(9,16)=12:T(9,17)=16:T(10,16)=9
33 T(10,17)=13:T(11,16)=8:T(11,17)=12:T(12,16)=6:T(12,17)=10:T(13,16)=12:T(13,17)=16:T(14,16)=6:T(14,17)=10
34 T(15,16)=10:T(15,17)=14:T(16,17)=10
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 17
88 A(I)=FIX(RND*699)
89 NEXT I
126 REM IMAR=10+FIX(RND*32000)
128 FOR I=1 TO 32000
129 FOR KK=1 TO 17
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*17):IJM=1+FIX(RND*17):IJN=1+FIX(RND*17)
233 IF RND<.7 THEN X(IJL)=FIX(RND*699) ELSE IF RND<.05 THEN X(IJL)=A(IJL)-1-FIX(RND*2) ELSE GOTO 244
235 GOTO 351
244 X(IJM)=A(IJN):X(IJN)=A(IJM)
351 FOR K=1 TO 16
361 FOR J=K+1 TO 17
364 IF T(K,J)>ABS(X(K)-X(J)) THEN TZ(K,J)=99999! ELSE TZ(K,J)=0
366 NEXT J
399 NEXT K
1590 SUMTZ=0
1591 FOR K=1 TO 16
1594 FOR J=K+1 TO 17
1596 SUMTZ=SUMTZ+TZ(K,J)
1597 NEXT J
1598 NEXT K
1623 PR1=-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))-5*ABS(X(1)-X(12))-0*ABS(X(1)-X(13))-0*ABS(X(1)-X(14))-5*ABS(X(1)-X(15))
1624 PR2=-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))-5*ABS(X(2)-X(12))-0*ABS(X(2)-X(13))-10*ABS(X(2)-X(14))-10*ABS(X(2)-X(15))
1625 PR3=-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))-0*ABS(X(3)-X(12))-0*ABS(X(3)-X(13))-5*ABS(X(3)-X(14))-1*ABS(X(3)-X(15))
1626 PR4=-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))-2*ABS(X(4)-X(12))-2*ABS(X(4)-X(13))-0*ABS(X(4)-X(14))-2*ABS(X(4)-X(15))
1627 PR5=-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))
1628 PR6=-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))
1629 PR7=-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))
1630 PR8=-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))
1631 PR9=-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))
1632 PR10=-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))
1633 PR11=-5*ABS(X(11)-X(12))-2*ABS(X(11)-X(13))-5*ABS(X(11)-X(14))-1*ABS(X(11)-X(15))
1636 PR12=-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))
1638 PR21=-4*ABS(X(1)-X(16))-4*ABS(X(1)-X(17))-3*ABS(X(2)-X(16))-0*ABS(X(2)-X(17))-0*ABS(X(3)-X(16))-0*ABS(X(3)-X(17))-1*ABS(X(4)-X(16))-5*ABS(X(4)-X(17))
1639 PR22=-1*ABS(X(5)-X(16))-5*ABS(X(5)-X(17))-0*ABS(X(6)-X(16))-1*ABS(X(6)-X(17))-1*ABS(X(7)-X(16))-2*ABS(X(7)-X(17))-2*ABS(X(8)-X(16))-5*ABS(X(8)-X(17))
1640 PR23= -5*ABS(X(9)-X(16))-0*ABS(X(9)-X(17))-0*ABS(X(10)-X(16))-0*ABS(X(10)-X(17))-10*ABS(X(11)-X(16))-0*ABS(X(11)-X(17))-0*ABS(X(12)-X(16))-1*ABS(X(12)-X(17))
1642 PR24=-1*ABS(X(13)-X(16))-0*ABS(X(13)-X(17))
1643 PR25=-5*ABS(X(14)-X(16))-1*ABS(X(14)-X(17))-3*ABS(X(15)-X(16))-0*ABS(X(15)-X(17))-0*ABS(X(16)-X(17))
1650 P=PR1+PR2+PR3+PR4+PR5+PR6+PR7+PR8+PR9+PR10+PR11+PR12+PR21+PR22+PR23+PR24+PR25-SUMTZ
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 17
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-18577 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9),A(10)
1914 PRINT A(11),A(12),A(13),A(14),A(15)
1915 PRINT A(16),A(17),M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW-BASIC 3.11 interpreter, and the output produced within the first twelve hours of running is presented below. What immediately follows is a manual copy from the computer screen.

419 316 266 328 300
278 378 352 230 287
336 344 248 310 364
322 392 -18508 -31829

187 298 340 292 228
328 242 268 376 319
284 276 358 310 256
304 214 -18552 -31753

18508 is optimal, Amaral (2008, p. 1030). Interpreted in accordance with line 1912 through line 1915, the output above was produced within the first twelve hours of running on a personal computer with an Intel 2.66 GHz. chip and the Microsoft interpreter, which is not a compiler.

References

Amaral, A. R. S., 2006. On the exact solution of a facility layout problem. European Journal of Operational Research 173, 508-518.

Amaral, A. R. S., 2008. An exact approach to the one-dimensional facility layout problem. Operations Research 56, 1026-1033.

Heragu, S. S., A. Kusiak, 1991. Efficient models for the facility layout problem. European Journal of Operational Research 53, 1-13.

Simmons, D. M., 1969. One-dimensioanl space allocation: An ordering algorithm. Operations Research 17, 812-826.

Postscript: Line 233 of the present post and line 233 of the preceding post are noteworthy.

A Computer Program Illustrating an Ordering Algorithm for Eighteen Departments, Third Edition

Jsun Yui Wong

The complete computer program listed below seeks to solve Problem P18 of Amaral (2008), which is an instance of the allocation problem of Simmons (1969). In order to have integer locations, the department lengths used in the following computer program are twice as long as the original lengths.

0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466)
6 DIM T(33,33),TZ(33,33)
11 T(1,2)=23:T(1,3)=29:T(1,4)=23:T(1,5)=27:T(1,6)=23:T(1,7)=27:T(1,8)=25:T(1,9)=29:T(1,10)=26:T(1,11)=25:T(1,12)=23:T(1,13)=29:T(1,14)=23:T(1,15)=27
12 T(2,3)=12:T(2,4)=6:T(2,5)=10:T(2,6)=6:T(2,7)=10:T(2,8)=8:T(2,9)=12:T(2,10)=9:T(2,11)=8:T(2,12)=6:T(2,13)=12:T(2,14)=6:T(2,15)=10
13 T(3,4)=12:T(3,5)=16:T(3,6)=12:T(3,7)=16:T(3,8)=14:T(3,9)=18:T(3,10)=15:T(3,11)=14:T(3,12)=12:T(3,13)=18:T(3,14)=12:T(3,15)=16
14 T(4,5)=10:T(4,6)=6:T(4,7)=10:T(4,8)=8:T(4,9)=12:T(4,10)=9:T(4,11)=8:T(4,12)=6:T(4,13)=12:T(4,14)=6:T(4,15)=10
15 T(5,6)=10:T(5,7)=14:T(5,8)=12:T(5,9)=16:T(5,10)=13:T(5,11)=12:T(5,12)=10:T(5,13)=16:T(5,14)=10:T(5,15)=14
16 T(6,7)=10:T(6,8)=8:T(6,9)=12:T(6,10)=9:T(6,11)=8:T(6,12)=6:T(6,13)=12:T(6,14)=6:T(6,15)=10
17 T(7,8)=12:T(7,9)=16:T(7,10)=13:T(7,11)=12:T(7,12)=10:T(7,13)=16:T(7,14)=10:T(7,15)=14
18 T(8,9)=14:T(8,10)=11:T(8,11)=10:T(8,12)=8:T(8,13)=14:T(8,14)=8:T(8,15)=12
19 T(9,10)=15:T(9,11)=14:T(9,12)=12:T(9,13)=18:T(9,14)=12:T(9,15)=16
20 T(10,11)=11:T(10,12)=9:T(10,13)=15:T(10,14)=9:T(10,15)=13
21 T(11,12)=8:T(11,13)=14:T(11,14)=8:T(11,15)=12:T(12,13)=12:T(12,14)=6:T(12,15)=10:T(13,14)=12:T(13,15)=16:T(14,15)=10
31 T(1,16)=23:T(1,17)=27:T(1,18)=25:T(2,16)=6:T(2,17)=10:T(2,18)=8:T(3,16)=12:T(3,17)=16:T(3,18)=14:T(4,16)=6:T(4,17)=10:T(4,18)=8:T(5,16)=10:T(5,17)=14
32 T(5,18)=12:T(6,16)=6:T(6,17)=10:T(6,18)=8:T(7,16)=10:T(7,17)=14:T(7,18)=12:T(8,16)=8:T(8,17)=12:T(8,18)=10:T(9,16)=12:T(9,17)=16:T(9,18)=14:T(10,16)=9
33 T(10,17)=13:T(10,18)=11:T(11,16)=8:T(11,17)=12:T(11,18)=10:T(12,16)=6:T(12,17)=10:T(12,18)=8:T(13,16)=12:T(13,17)=16:T(13,18)=14:T(14,16)=6:T(14,17)=10
34 T(14,18)=8:T(15,16)=10:T(15,17)=14:T(15,18)=12:T(16,17)=10:T(16,18)=8:T(17,18)=12
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 18
88 A(I)=FIX(RND*699)
89 NEXT I
126 REM IMAR=10+FIX(RND*32000)
128 FOR I=1 TO 32000
129 FOR KK=1 TO 18
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*18):IJM=1+FIX(RND*18):IJN=1+FIX(RND*18)
233 IF RND<.7 THEN X(IJL)=FIX(RND*699) ELSE IF RND<.05 THEN X(IJL)=A(IJL)-1-FIX(RND*2) ELSE GOTO 244
235 GOTO 351
244 X(IJM)=A(IJN):X(IJN)=A(IJM)
351 FOR K=1 TO 17
361 FOR J=K+1 TO 18
364 IF T(K,J)>ABS(X(K)-X(J)) THEN TZ(K,J)=99999! ELSE TZ(K,J)=0
366 NEXT J
399 NEXT K
1590 SUMTZ=0
1591 FOR K=1 TO 17
1594 FOR J=K+1 TO 18
1596 SUMTZ=SUMTZ+TZ(K,J)
1597 NEXT J
1598 NEXT K
1623 PR1=-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))-5*ABS(X(1)-X(12))-0*ABS(X(1)-X(13))-0*ABS(X(1)-X(14))-5*ABS(X(1)-X(15))
1624 PR2=-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))-5*ABS(X(2)-X(12))-0*ABS(X(2)-X(13))-10*ABS(X(2)-X(14))-10*ABS(X(2)-X(15))
1625 PR3=-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))-0*ABS(X(3)-X(12))-0*ABS(X(3)-X(13))-5*ABS(X(3)-X(14))-1*ABS(X(3)-X(15))
1626 PR4=-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))-2*ABS(X(4)-X(12))-2*ABS(X(4)-X(13))-0*ABS(X(4)-X(14))-2*ABS(X(4)-X(15))
1627 PR5=-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))
1628 PR6=-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))
1629 PR7=-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))
1630 PR8=-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))
1631 PR9=-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))
1632 PR10=-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))
1633 PR11=-5*ABS(X(11)-X(12))-2*ABS(X(11)-X(13))-5*ABS(X(11)-X(14))-1*ABS(X(11)-X(15))
1636 PR12=-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))
1638 PR21=-4*ABS(X(1)-X(16))-4*ABS(X(1)-X(17))-0*ABS(X(1)-X(18))-3*ABS(X(2)-X(16))-0*ABS(X(2)-X(17))-5*ABS(X(2)-X(18))-0*ABS(X(3)-X(16))-0*ABS(X(3)-X(17))-5*ABS(X(3)-X(18))-1*ABS(X(4)-X(16))-5*ABS(X(4)-X(17))-2*ABS(X(4)-X(18))
1639 PR22=-1*ABS(X(5)-X(16))-5*ABS(X(5)-X(17))-2*ABS(X(5)-X(18))-0*ABS(X(6)-X(16))-1*ABS(X(6)-X(17))-0*ABS(X(6)-X(18))-1*ABS(X(7)-X(16))-2*ABS(X(7)-X(17))-1*ABS(X(7)-X(18))-2*ABS(X(8)-X(16))-5*ABS(X(8)-X(17))-2*ABS(X(8)-X(18))
1640 PR23=-5*ABS(X(9)-X(16))-0*ABS(X(9)-X(17))-0*ABS(X(9)-X(18))-0*ABS(X(10)-X(16))-0*ABS(X(10)-X(17))-5*ABS(X(10)-X(18))-10*ABS(X(11)-X(16))-0*ABS(X(11)-X(17))-2*ABS(X(11)-X(18))-0*ABS(X(12)-X(16))-1*ABS(X(12)-X(17))-1*ABS(X(12)-X(18))
1642 PR24=-1*ABS(X(13)-X(16))-0*ABS(X(13)-X(17))-0*ABS(X(13)-X(18))
1643 PR25=-5*ABS(X(14)-X(16))-1*ABS(X(14)-X(17))-5*ABS(X(14)-X(18))-3*ABS(X(15)-X(16))-0*ABS(X(15)-X(17))-5*ABS(X(15)-X(18))-0*ABS(X(16)-X(17))-0*ABS(X(16)-X(18))-5*ABS(X(17)-X(18))
1650 P=PR1+PR2+PR3+PR4+PR5+PR6+PR7+PR8+PR9+PR10+PR11+PR12+PR21+PR22+PR23+PR24+PR25-SUMTZ
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 18
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-21500 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9),A(10)
1914 PRINT A(11),A(12),A(13),A(14),A(15)
1915 PRINT A(16),A(17),A(18),M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW-BASIC 3.11 interpreter, and the output produced within the first ten hours of running is presented below. What immediately follows is a manual copy from the computer screen.

443 332 280 358 402
292 388 376 244 301
366 352 262 320 342
326 416 312 -21441 -31958

331 448 494 396 372
482 386 420 530 473
404 428 512 454 438
412 358 462 -21301 -31922

443 354 280 392 314
292 402 368 244 301
384 360 262 334 344
376 416 326 -21499 -31881

470 367 307 379 341
319 429 397 271 328
387 405 289 361 415
373 443 353 -21391 -31820

21301 is optimal, Amaral (2008, p. 1030). Interpreted in accordance with line 1912 through line 1915, the output through JJJJ=-31820 was produced within the first ten hours of running on a personal computer with an Intel 2.66 GHz. chip and the Microsoft interpreter, which is not a compiler.

References

Amaral, A. R. S., 2006. On the exact solution of a facility layout problem. European Journal of Operational Research 173, 508-518.

Amaral, A. R. S., 2008. An exact approach to the one-dimensional facility layout problem. Operations Research 56, 1026-1033.

Heragu, S. S., A. Kusiak, 1991. Efficient models for the facility layout problem. European Journal of Operational Research 53, 1-13.

Simmons, D. M., 1969. One-dimensioanl space allocation: An ordering algorithm. Operations Research 17, 812-826.