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).
