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.
Thursday, October 29, 2009
Saturday, October 24, 2009
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).
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).
Monday, October 19, 2009
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).
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).
Sunday, October 18, 2009
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).
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).
Saturday, October 17, 2009
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).
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).
Friday, October 16, 2009
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.
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.
Thursday, October 15, 2009
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.
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.
Subscribe to:
Posts (Atom)