Jsun Yui Wong
The complete computer program listed below seeks to solve a six-department space allocation problem (Armour and Buffa, 1963). The departmment sizes for department 1 through department 6 are 25x20, 25x20, 35x30, 30x20, 35x20, and 60x40, respectively; the interdepartmental flows are shown in line 1624 through line 1627 of the following program. The sizes and flows of the first five departments are from Heragu (2008). The 1-6, 2-6, 3-6, 4-6, and 5-6 flows are 17, 32, 26, 13, and 19, respectively.
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466),HS(99)
6 DIM T(11,11,5),TZ(11,11),TL(22)
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 12
88 A(I)=(RND*240)
89 NEXT I
126 IMAR=10+FIX(RND*20000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 12
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*12)
234 X(IJL)=(RND*240)
391 HS(1)=ABS(X(1)-X(2))-25
392 HS(2)=ABS(X(1)-X(3))-30
393 HS(3)=ABS(X(1)-X(4))-27.5
394 HS(4)=ABS(X(1)-X(5))-30
395 HS(5)=ABS(X(1)-X(6))-42.5
405 HS(6)=ABS(X(2)-X(3))-30
406 HS(7)=ABS(X(2)-X(4))-27.5
407 HS(8)=ABS(X(2)-X(5))-30
408 HS(9)=ABS(X(2)-X(6))-42.5
409 HS(10)=ABS(X(3)-X(4))-32.5
410 HS(11)=ABS(X(3)-X(5))-35
411 HS(12)=ABS(X(3)-X(6))-47.5
412 HS(13)=ABS(X(4)-X(5))-32.5
413 HS(14)=ABS(X(4)-X(6))-45
414 HS(15)=ABS(X(5)-X(6))-47.5
415 HS(16)=ABS(X(7)-X(8))-20
416 HS(17)=ABS(X(7)-X(9))-25
417 HS(18)=ABS(X(7)-X(10))-20
418 HS(19)=ABS(X(7)-X(11))-20
419 HS(20)=ABS(X(7)-X(12))-30
420 HS(21)=ABS(X(8)-X(9))-25
421 HS(22)=ABS(X(8)-X(10))-20
422 HS(23)=ABS(X(8)-X(11))-20
423 HS(24)=ABS(X(8)-X(12))-30
424 HS(25)=ABS(X(9)-X(10))-25
425 HS(26)=ABS(X(9)-X(11))-25
426 HS(27)=ABS(X(9)-X(12))-35
427 HS(28)=ABS(X(10)-X(11))-20
431 HS(29)=ABS(X(10)-X(12))-30
432 HS(30)=ABS(X(11)-X(12))-30
551 IF HS(1)<-.0001 AND HS(16)<-.0001 THEN TL(1)=999999! ELSE TL(1)=0
553 IF HS(2)<-.0001 AND HS(17)<-.0001 THEN TL(2)=999999! ELSE TL(2)=0
554 IF HS(3)<-.0001 AND HS(18)<-.0001 THEN TL(3)=999999! ELSE TL(3)=0
555 IF HS(4)<-.0001 AND HS(19)<-.0001 THEN TL(4)=999999! ELSE TL(4)=0
557 IF HS(5)<-.0001 AND HS(20)<-.0001 THEN TL(5)=999999! ELSE TL(5)=0
559 IF HS(6)<-.0001 AND HS(21)<-.0001 THEN TL(6)=999999! ELSE TL(6)=0
560 IF HS(7)<-.0001 AND HS(22)<-.0001 THEN TL(7)=999999! ELSE TL(7)=0
565 IF HS(8)<-.0001 AND HS(23)<-.0001 THEN TL(8)=999999! ELSE TL(8)=0
568 IF HS(9)<-.0001 AND HS(24)<-.0001 THEN TL(9)=999999! ELSE TL(9)=0
569 IF HS(10)<-.0001 AND HS(25)<-.0001 THEN TL(10)=999999! ELSE TL(10)=0
581 IF HS(11)<-.0001 AND HS(26)<-.0001 THEN TL(10)=999999! ELSE TL(11)=0
582 IF HS(12)<-.0001 AND HS(27)<-.0001 THEN TL(10)=999999! ELSE TL(12)=0
583 IF HS(13)<-.0001 AND HS(28)<-.0001 THEN TL(10)=999999! ELSE TL(13)=0
584 IF HS(14)<-.0001 AND HS(29)<-.0001 THEN TL(10)=999999! ELSE TL(14)=0
585 IF HS(15)<-.0001 AND HS(30)<-.0001 THEN TL(10)=999999! ELSE TL(15)=0
1611 SUMTL=0
1613 FOR IR=1 TO 15
1615 SUMTL=SUMTL+TL(IR)
1618 NEXT IR
1624 PR1=-10*ABS(X(1)-X(2))-15*ABS(X(1)-X(3))-20*ABS(X(1)-X(4))-0*ABS(X(1)-X(5))-17*ABS(X(1)-X(6))-30*ABS(X(2)-X(3))-35*ABS(X(2)-X(4))-10*ABS(X(2)-X(5))-32*ABS(X(2)-X(6))
1625 PR2=-10*ABS(X(3)-X(4))-20*ABS(X(3)-X(5))-26*ABS(X(3)-X(6))-15*ABS(X(4)-X(5))-13*ABS(X(4)-X(6))-19*ABS(X(5)-X(6))-10*ABS(X(7)-X(8))-15*ABS(X(7)-X(9))-20*ABS(X(7)-X(10))-0*ABS(X(7)-X(11))
1626 PR3=-17*ABS(X(7)-X(12))-30*ABS(X(8)-X(9))-35*ABS(X(8)-X(10))-10*ABS(X(8)-X(11))-32*ABS(X(8)-X(12))-10*ABS(X(9)-X(10))
1627 PR4=-20*ABS(X(9)-X(11))-26*ABS(X(9)-X(12))-15*ABS(X(10)-X(11))-13*ABS(X(10)-X(12))-19*ABS(X(11)-X(12))
1650 P=PR1+PR2+PR3+PR4-999*SUMTL
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 12
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1662 MM=PR1+PR2+PR3+PR4
1666 GOTO 128
1670 NEXT I
1890 IF M>-11639 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),A(9),A(10)
1915 PRINT A(11),A(12),MM,M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, and the output produced in thirteen hours of running is presented below. What immediately follows is a manual copy from the computer screen.
136.2185 165.1701 166.2257 137.6041 195.1733
165.2049 53.04271 33.03552 58.10423 33.0356
33.01572 2.968483 -11631.06 -11631.06 -31438
155.788 126.4413 125.7753 153.9702 96.41533
126.3579 62.67572 82.73879 57.66229 82.73458
82.69295 112.7742 -11631.88 -11631.88 -30257
98.17766 128.1517 128.1806 100.6427 158.2056
128.1536 87.69828 107.7177 82.69673 107.7191
107.7014 137.7372 -11621.93 -11621.93 -27712
Interpreted in accordance with line 1912 through line 1915, the output through JJJJ=-27712 was produced during the first thirteen hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter, which is not a compiler.
References
G. C. Armour and E. S. Buffa, "A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities," Management Science 9, 294-309 (1963).
S. S. Heragu. Facilities Design, Third Edition. CRC Press, 2008.
Wednesday, October 14, 2009
Monday, October 12, 2009
An Integer-Programming Computer Program Applied to a Space Allocation Problem
Jsun Yui Wong
The complete computer program listed below seeks to solve a five-department space allocation problem (Armour and Buffa, 1963). The departmment sizes for department 1 through department 5 are 25x20, 25x20, 35x30, 30x20, and 35x20, respectively; the interdepartmental flows are shown in line 1624, line 1625, and line 1626 of the following program. These sizes and flows are from Heragu (2008).
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466),HS(99)
6 DIM T(11,11,5),TZ(11,11),TL(11)
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 10
88 A(I)=FIX(RND*240)
89 NEXT I
126 IMAR=10+FIX(RND*20000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 10
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*10)
234 X(IJL)=FIX(RND*240)
401 HS(1)=ABS(X(1)-X(2))-25
402 HS(2)=ABS(X(1)-X(3))-30
403 HS(3)=ABS(X(1)-X(4))-27.5
404 HS(4)=ABS(X(1)-X(5))-30
405 HS(5)=ABS(X(2)-X(3))-30
406 HS(6)=ABS(X(2)-X(4))-27.5
407 HS(7)=ABS(X(2)-X(5))-30
409 HS(9)=ABS(X(3)-X(4))-32.5
410 HS(10)=ABS(X(3)-X(5))-35
411 HS(11)=ABS(X(4)-X(5))-32.5
413 HS(13)=ABS(X(6)-X(7))-20
414 HS(14)=ABS(X(6)-X(8))-25
415 HS(15)=ABS(X(6)-X(9))-20
416 HS(16)=ABS(X(6)-X(10))-20
417 HS(17)=ABS(X(7)-X(8))-25
418 HS(18)=ABS(X(7)-X(9))-20
419 HS(19)=ABS(X(7)-X(10))-20
420 HS(20)=ABS(X(8)-X(9))-25
421 HS(21)=ABS(X(8)-X(10))-25
422 HS(22)=ABS(X(9)-X(10))-20
551 IF HS(1)<-.0001 AND HS(13)<-.0001 THEN TL(1)=999999! ELSE TL(1)=0
553 IF HS(2)<-.0001 AND HS(14)<-.0001 THEN TL(2)=999999! ELSE TL(2)=0
554 IF HS(3)<-.0001 AND HS(15)<-.0001 THEN TL(3)=999999! ELSE TL(3)=0
555 IF HS(4)<-.0001 AND HS(16)<-.0001 THEN TL(4)=999999! ELSE TL(4)=0
557 IF HS(5)<-.0001 AND HS(17)<-.0001 THEN TL(5)=999999! ELSE TL(5)=0
559 IF HS(6)<-.0001 AND HS(18)<-.0001 THEN TL(6)=999999! ELSE TL(6)=0
560 IF HS(7)<-.0001 AND HS(19)<-.0001 THEN TL(7)=999999! ELSE TL(7)=0
565 IF HS(9)<-.0001 AND HS(20)<-.0001 THEN TL(8)=999999! ELSE TL(8)=0
568 IF HS(10)<-.0001 AND HS(21)<-.0001 THEN TL(9)=999999! ELSE TL(9)=0
569 IF HS(11)<-.0001 AND HS(22)<-.0001 THEN TL(10)=999999! ELSE TL(10)=0
1611 SUMTL=0
1613 FOR IR=1 TO 10
1615 SUMTL=SUMTL+TL(IR)
1618 NEXT IR
1624 PR1=-10*ABS(X(1)-X(2))-15*ABS(X(1)-X(3))-20*ABS(X(1)-X(4))-0*ABS(X(1)-X(5))-30*ABS(X(2)-X(3))-35*ABS(X(2)-X(4))-10*ABS(X(2)-X(5))
1625 PR2=-10*ABS(X(3)-X(4))-20*ABS(X(3)-X(5))-15*ABS(X(4)-X(5))-10*ABS(X(6)-X(7))-15*ABS(X(6)-X(8))-20*ABS(X(6)-X(9))-0*ABS(X(6)-X(10))
1626 PR3=-30*ABS(X(7)-X(8))-35*ABS(X(7)-X(9))-10*ABS(X(7)-X(10))-10*ABS(X(8)-X(9))-20*ABS(X(8)-X(10))-15*ABS(X(9)-X(10))
1650 P=PR1+PR2+PR3-999*SUMTL
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 10
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1662 MM=PR1+PR2+PR3
1666 GOTO 128
1670 NEXT I
1890 IF M>-5700 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),A(9),A(10)
1915 PRINT MM,M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, and the best candidate solutions produced during the first 65 minutes of running are presented below. What immediately follows is a manual copy from the computer screen.
98 127 128 99 127
93 113 88 113 133
-5575 -5575 -31252
106 136 136 108 136
140 120 145 120 100
-5545 -5545 -30898
84 54 54 82 54
143 163 138 163 183
-5545 -5545 -30539
Interpreted in accordance with line 1912 through line 1915, the output through JJJJ=-30539 was produced during the first 65 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter, which is not a compiler.
References
G. C. Armour and E. S. Buffa, "A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities," Management Science 9, 294-309 (1963).
S. S. Heragu. Facilities Design, Third Edition. CRC Press, 2008.
The complete computer program listed below seeks to solve a five-department space allocation problem (Armour and Buffa, 1963). The departmment sizes for department 1 through department 5 are 25x20, 25x20, 35x30, 30x20, and 35x20, respectively; the interdepartmental flows are shown in line 1624, line 1625, and line 1626 of the following program. These sizes and flows are from Heragu (2008).
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466),HS(99)
6 DIM T(11,11,5),TZ(11,11),TL(11)
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 10
88 A(I)=FIX(RND*240)
89 NEXT I
126 IMAR=10+FIX(RND*20000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 10
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*10)
234 X(IJL)=FIX(RND*240)
401 HS(1)=ABS(X(1)-X(2))-25
402 HS(2)=ABS(X(1)-X(3))-30
403 HS(3)=ABS(X(1)-X(4))-27.5
404 HS(4)=ABS(X(1)-X(5))-30
405 HS(5)=ABS(X(2)-X(3))-30
406 HS(6)=ABS(X(2)-X(4))-27.5
407 HS(7)=ABS(X(2)-X(5))-30
409 HS(9)=ABS(X(3)-X(4))-32.5
410 HS(10)=ABS(X(3)-X(5))-35
411 HS(11)=ABS(X(4)-X(5))-32.5
413 HS(13)=ABS(X(6)-X(7))-20
414 HS(14)=ABS(X(6)-X(8))-25
415 HS(15)=ABS(X(6)-X(9))-20
416 HS(16)=ABS(X(6)-X(10))-20
417 HS(17)=ABS(X(7)-X(8))-25
418 HS(18)=ABS(X(7)-X(9))-20
419 HS(19)=ABS(X(7)-X(10))-20
420 HS(20)=ABS(X(8)-X(9))-25
421 HS(21)=ABS(X(8)-X(10))-25
422 HS(22)=ABS(X(9)-X(10))-20
551 IF HS(1)<-.0001 AND HS(13)<-.0001 THEN TL(1)=999999! ELSE TL(1)=0
553 IF HS(2)<-.0001 AND HS(14)<-.0001 THEN TL(2)=999999! ELSE TL(2)=0
554 IF HS(3)<-.0001 AND HS(15)<-.0001 THEN TL(3)=999999! ELSE TL(3)=0
555 IF HS(4)<-.0001 AND HS(16)<-.0001 THEN TL(4)=999999! ELSE TL(4)=0
557 IF HS(5)<-.0001 AND HS(17)<-.0001 THEN TL(5)=999999! ELSE TL(5)=0
559 IF HS(6)<-.0001 AND HS(18)<-.0001 THEN TL(6)=999999! ELSE TL(6)=0
560 IF HS(7)<-.0001 AND HS(19)<-.0001 THEN TL(7)=999999! ELSE TL(7)=0
565 IF HS(9)<-.0001 AND HS(20)<-.0001 THEN TL(8)=999999! ELSE TL(8)=0
568 IF HS(10)<-.0001 AND HS(21)<-.0001 THEN TL(9)=999999! ELSE TL(9)=0
569 IF HS(11)<-.0001 AND HS(22)<-.0001 THEN TL(10)=999999! ELSE TL(10)=0
1611 SUMTL=0
1613 FOR IR=1 TO 10
1615 SUMTL=SUMTL+TL(IR)
1618 NEXT IR
1624 PR1=-10*ABS(X(1)-X(2))-15*ABS(X(1)-X(3))-20*ABS(X(1)-X(4))-0*ABS(X(1)-X(5))-30*ABS(X(2)-X(3))-35*ABS(X(2)-X(4))-10*ABS(X(2)-X(5))
1625 PR2=-10*ABS(X(3)-X(4))-20*ABS(X(3)-X(5))-15*ABS(X(4)-X(5))-10*ABS(X(6)-X(7))-15*ABS(X(6)-X(8))-20*ABS(X(6)-X(9))-0*ABS(X(6)-X(10))
1626 PR3=-30*ABS(X(7)-X(8))-35*ABS(X(7)-X(9))-10*ABS(X(7)-X(10))-10*ABS(X(8)-X(9))-20*ABS(X(8)-X(10))-15*ABS(X(9)-X(10))
1650 P=PR1+PR2+PR3-999*SUMTL
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 10
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1662 MM=PR1+PR2+PR3
1666 GOTO 128
1670 NEXT I
1890 IF M>-5700 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),A(9),A(10)
1915 PRINT MM,M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, and the best candidate solutions produced during the first 65 minutes of running are presented below. What immediately follows is a manual copy from the computer screen.
98 127 128 99 127
93 113 88 113 133
-5575 -5575 -31252
106 136 136 108 136
140 120 145 120 100
-5545 -5545 -30898
84 54 54 82 54
143 163 138 163 183
-5545 -5545 -30539
Interpreted in accordance with line 1912 through line 1915, the output through JJJJ=-30539 was produced during the first 65 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter, which is not a compiler.
References
G. C. Armour and E. S. Buffa, "A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities," Management Science 9, 294-309 (1963).
S. S. Heragu. Facilities Design, Third Edition. CRC Press, 2008.
A Complete Computer Program and Its Output for a Space Allocation Problem
Jsun Yui Wong
The complete computer program listed below seeks to solve a five-department space allocation problem (Armour and Buffa, 1963). The departmment sizes for department 1 through department 5 are 20x50, 30x40, 10x20, 60x70, and 40x50, respectively; the interdepartmental flows are shown in line 1624, line 1625, and line 1626 of the following program.
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466),HS(99)
6 DIM T(11,11,5),TZ(11,11),TL(11)
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 10
88 A(I)=FIX(RND*240)
89 NEXT I
126 IMAR=10+FIX(RND*20000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 10
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*10)
234 X(IJL)=FIX(RND*240)
401 HS(1)=ABS(X(1)-X(2))-25
402 HS(2)=ABS(X(1)-X(3))-15
403 HS(3)=ABS(X(1)-X(4))-40
404 HS(4)=ABS(X(1)-X(5))-30
405 HS(5)=ABS(X(2)-X(3))-20
406 HS(6)=ABS(X(2)-X(4))-45
407 HS(7)=ABS(X(2)-X(5))-35
409 HS(9)=ABS(X(3)-X(4))-35
410 HS(10)=ABS(X(3)-X(5))-25
411 HS(11)=ABS(X(4)-X(5))-50
413 HS(13)=ABS(X(6)-X(7))-45
414 HS(14)=ABS(X(6)-X(8))-35
415 HS(15)=ABS(X(6)-X(9))-60
416 HS(16)=ABS(X(6)-X(10))-50
417 HS(17)=ABS(X(7)-X(8))-30
418 HS(18)=ABS(X(7)-X(9))-55
419 HS(19)=ABS(X(7)-X(10))-45
420 HS(20)=ABS(X(8)-X(9))-45
421 HS(21)=ABS(X(8)-X(10))-35
422 HS(22)=ABS(X(9)-X(10))-60
551 IF HS(1)<-.0001 AND HS(13)<-.0001 THEN TL(1)=999999! ELSE TL(1)=0
553 IF HS(2)<-.0001 AND HS(14)<-.0001 THEN TL(2)=999999! ELSE TL(2)=0
554 IF HS(3)<-.0001 AND HS(15)<-.0001 THEN TL(3)=999999! ELSE TL(3)=0
555 IF HS(4)<-.0001 AND HS(16)<-.0001 THEN TL(4)=999999! ELSE TL(4)=0
557 IF HS(5)<-.0001 AND HS(17)<-.0001 THEN TL(5)=999999! ELSE TL(5)=0
559 IF HS(6)<-.0001 AND HS(18)<-.0001 THEN TL(6)=999999! ELSE TL(6)=0
560 IF HS(7)<-.0001 AND HS(19)<-.0001 THEN TL(7)=999999! ELSE TL(7)=0
565 IF HS(9)<-.0001 AND HS(20)<-.0001 THEN TL(8)=999999! ELSE TL(8)=0
568 IF HS(10)<-.0001 AND HS(21)<-.0001 THEN TL(9)=999999! ELSE TL(9)=0
569 IF HS(11)<-.0001 AND HS(22)<-.0001 THEN TL(10)=999999! ELSE TL(10)=0
1611 SUMTL=0
1613 FOR IR=1 TO 10
1615 SUMTL=SUMTL+TL(IR)
1618 NEXT IR
1624 PR1=-111*ABS(X(1)-X(2))-222*ABS(X(1)-X(3))-110*ABS(X(1)-X(4))-340*ABS(X(1)-X(5))-88*ABS(X(2)-X(3))-260*ABS(X(2)-X(4))-70*ABS(X(2)-X(5))
1625 PR2=-250*ABS(X(3)-X(4))-90*ABS(X(3)-X(5))-280*ABS(X(4)-X(5))-111*ABS(X(6)-X(7))-222*ABS(X(6)-X(8))-110*ABS(X(6)-X(9))-340*ABS(X(6)-X(10))
1626 PR3=-88*ABS(X(7)-X(8))-260*ABS(X(7)-X(9))-70*ABS(X(7)-X(10))-250*ABS(X(8)-X(9))-90*ABS(X(8)-X(10))-280*ABS(X(9)-X(10))
1650 P=PR1+PR2+PR3-999*SUMTL
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 10
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1662 MM=PR1+PR2+PR3
1666 GOTO 128
1670 NEXT I
1890 IF M>-95555! THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),A(9),A(10)
1915 PRINT MM,M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, and the output produced during the first 25 minutes of running is presented below. What immediately follows is a manual copy from the computer screen.
113 78 98 33 143
54 54 54 54 54
-95325 -95325 -31788
73 108 88 153 43
85 85 85 85 85
-95325 -95325 -31737
105 140 120 185 75
186 186 186 186 186
-95325 -95325 -31597
158 63 143 108 188
137 137 137 137 137
-92265 -92265 -31584
146 141 131 96 176
90 45 90 90 90
-93620 -93620 -31427
143 238 158 193 113
167 167 167 167 167
-92265 -92265 -31402
Interpreted in accordance with line 1912 through line 1915, the output through JJJJ=-31402 was produced during the first 25 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter, which is not a compiler.
Reference
G. C. Armour and E. S. Buffa, "A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities," Management Science 9, 294-309 (1963).
The complete computer program listed below seeks to solve a five-department space allocation problem (Armour and Buffa, 1963). The departmment sizes for department 1 through department 5 are 20x50, 30x40, 10x20, 60x70, and 40x50, respectively; the interdepartmental flows are shown in line 1624, line 1625, and line 1626 of the following program.
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466),HS(99)
6 DIM T(11,11,5),TZ(11,11),TL(11)
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 10
88 A(I)=FIX(RND*240)
89 NEXT I
126 IMAR=10+FIX(RND*20000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 10
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*10)
234 X(IJL)=FIX(RND*240)
401 HS(1)=ABS(X(1)-X(2))-25
402 HS(2)=ABS(X(1)-X(3))-15
403 HS(3)=ABS(X(1)-X(4))-40
404 HS(4)=ABS(X(1)-X(5))-30
405 HS(5)=ABS(X(2)-X(3))-20
406 HS(6)=ABS(X(2)-X(4))-45
407 HS(7)=ABS(X(2)-X(5))-35
409 HS(9)=ABS(X(3)-X(4))-35
410 HS(10)=ABS(X(3)-X(5))-25
411 HS(11)=ABS(X(4)-X(5))-50
413 HS(13)=ABS(X(6)-X(7))-45
414 HS(14)=ABS(X(6)-X(8))-35
415 HS(15)=ABS(X(6)-X(9))-60
416 HS(16)=ABS(X(6)-X(10))-50
417 HS(17)=ABS(X(7)-X(8))-30
418 HS(18)=ABS(X(7)-X(9))-55
419 HS(19)=ABS(X(7)-X(10))-45
420 HS(20)=ABS(X(8)-X(9))-45
421 HS(21)=ABS(X(8)-X(10))-35
422 HS(22)=ABS(X(9)-X(10))-60
551 IF HS(1)<-.0001 AND HS(13)<-.0001 THEN TL(1)=999999! ELSE TL(1)=0
553 IF HS(2)<-.0001 AND HS(14)<-.0001 THEN TL(2)=999999! ELSE TL(2)=0
554 IF HS(3)<-.0001 AND HS(15)<-.0001 THEN TL(3)=999999! ELSE TL(3)=0
555 IF HS(4)<-.0001 AND HS(16)<-.0001 THEN TL(4)=999999! ELSE TL(4)=0
557 IF HS(5)<-.0001 AND HS(17)<-.0001 THEN TL(5)=999999! ELSE TL(5)=0
559 IF HS(6)<-.0001 AND HS(18)<-.0001 THEN TL(6)=999999! ELSE TL(6)=0
560 IF HS(7)<-.0001 AND HS(19)<-.0001 THEN TL(7)=999999! ELSE TL(7)=0
565 IF HS(9)<-.0001 AND HS(20)<-.0001 THEN TL(8)=999999! ELSE TL(8)=0
568 IF HS(10)<-.0001 AND HS(21)<-.0001 THEN TL(9)=999999! ELSE TL(9)=0
569 IF HS(11)<-.0001 AND HS(22)<-.0001 THEN TL(10)=999999! ELSE TL(10)=0
1611 SUMTL=0
1613 FOR IR=1 TO 10
1615 SUMTL=SUMTL+TL(IR)
1618 NEXT IR
1624 PR1=-111*ABS(X(1)-X(2))-222*ABS(X(1)-X(3))-110*ABS(X(1)-X(4))-340*ABS(X(1)-X(5))-88*ABS(X(2)-X(3))-260*ABS(X(2)-X(4))-70*ABS(X(2)-X(5))
1625 PR2=-250*ABS(X(3)-X(4))-90*ABS(X(3)-X(5))-280*ABS(X(4)-X(5))-111*ABS(X(6)-X(7))-222*ABS(X(6)-X(8))-110*ABS(X(6)-X(9))-340*ABS(X(6)-X(10))
1626 PR3=-88*ABS(X(7)-X(8))-260*ABS(X(7)-X(9))-70*ABS(X(7)-X(10))-250*ABS(X(8)-X(9))-90*ABS(X(8)-X(10))-280*ABS(X(9)-X(10))
1650 P=PR1+PR2+PR3-999*SUMTL
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 10
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1662 MM=PR1+PR2+PR3
1666 GOTO 128
1670 NEXT I
1890 IF M>-95555! THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),A(9),A(10)
1915 PRINT MM,M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, and the output produced during the first 25 minutes of running is presented below. What immediately follows is a manual copy from the computer screen.
113 78 98 33 143
54 54 54 54 54
-95325 -95325 -31788
73 108 88 153 43
85 85 85 85 85
-95325 -95325 -31737
105 140 120 185 75
186 186 186 186 186
-95325 -95325 -31597
158 63 143 108 188
137 137 137 137 137
-92265 -92265 -31584
146 141 131 96 176
90 45 90 90 90
-93620 -93620 -31427
143 238 158 193 113
167 167 167 167 167
-92265 -92265 -31402
Interpreted in accordance with line 1912 through line 1915, the output through JJJJ=-31402 was produced during the first 25 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter, which is not a compiler.
Reference
G. C. Armour and E. S. Buffa, "A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities," Management Science 9, 294-309 (1963).
A Computer Program and Its Output for a Small Space Allocation Problem
Jsun Yui Wong
The complete computer program listed below seeks to solve a small space allocation problem (Armour and Buffa, 1963). The departmment sizes for department 1 through department 4 are 20x50, 30x40, 10x20, and 60x70, respectively; the interdepartmental flows are shown in line 1624 of the following program.
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466),HS(99)
6 DIM T(11,11,5),TZ(11,11),TL(11)
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 8
88 A(I)=FIX(RND*240)
89 NEXT I
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 8
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*8)
234 X(IJL)=FIX(RND*240)
401 HS(1)=ABS(X(1)-X(2))-25
402 HS(2)=ABS(X(1)-X(3))-15
403 HS(3)=ABS(X(1)-X(4))-40
405 HS(5)=ABS(X(2)-X(3))-20
406 HS(6)=ABS(X(2)-X(4))-45
409 HS(9)=ABS(X(3)-X(4))-35
413 HS(13)=ABS(X(5)-X(6))-45
414 HS(14)=ABS(X(5)-X(7))-35
415 HS(15)=ABS(X(5)-X(8))-60
417 HS(17)=ABS(X(6)-X(7))-30
418 HS(18)=ABS(X(6)-X(8))-55
421 HS(21)=ABS(X(7)-X(8))-45
551 IF HS(1)<-.0001 AND HS(13)<-.0001 THEN TL(1)=999999! ELSE TL(1)=0
553 IF HS(2)<-.0001 AND HS(14)<-.0001 THEN TL(2)=999999! ELSE TL(2)=0
554 IF HS(3)<-.0001 AND HS(15)<-.0001 THEN TL(3)=999999! ELSE TL(3)=0
557 IF HS(5)<-.0001 AND HS(17)<-.0001 THEN TL(4)=999999! ELSE TL(4)=0
559 IF HS(6)<-.0001 AND HS(18)<-.0001 THEN TL(5)=999999! ELSE TL(5)=0
561 IF HS(9)<-.0001 AND HS(21)<-.0001 THEN TL(6)=999999! ELSE TL(6)=0
1611 SUMTL=0
1613 FOR IR=1 TO 6
1615 SUMTL=SUMTL+TL(IR)
1618 NEXT IR
1624 PR1=-111*ABS(X(1)-X(2))-222*ABS(X(1)-X(3))-110*ABS(X(1)-X(4))-88*ABS(X(2)-X(3))-260*ABS(X(2)-X(4))-250*ABS(X(3)-X(4))-111*ABS(X(5)-X(6))-222*ABS(X(5)-X(7))-110*ABS(X(5)-X(8))-88*ABS(X(6)-X(7))-260*ABS(X(6)-X(8))-250*ABS(X(7)-X(8))
1650 P=PR1-999*SUMTL
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 8
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1662 MM=PR1
1666 GOTO 128
1670 NEXT I
1890 IF M>-45000! THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),MM,M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced during the first 2 minutes of running is presented below. What immediately follows is a manual copy from the computer screen.
199 224 184 149 98
98 98 98 -43375 -43375
-31973
97 124 81 46 185
185 185 185 -44973 -44973
-31962
180 155 195 231 103
102 103 103 -44454 -44454
-31933
166 191 151 116 14
14 14 14 -43375 -43375
-31919
Interpreted in accordance with line 1912 and line 1914, the output through JJJJ=-31919 was produced during the first 2 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
Reference
G. C. Armour and E. S. Buffa, "A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities," Management Science 9, 294-309 (1963).
The complete computer program listed below seeks to solve a small space allocation problem (Armour and Buffa, 1963). The departmment sizes for department 1 through department 4 are 20x50, 30x40, 10x20, and 60x70, respectively; the interdepartmental flows are shown in line 1624 of the following program.
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466),HS(99)
6 DIM T(11,11,5),TZ(11,11),TL(11)
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 8
88 A(I)=FIX(RND*240)
89 NEXT I
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 8
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*8)
234 X(IJL)=FIX(RND*240)
401 HS(1)=ABS(X(1)-X(2))-25
402 HS(2)=ABS(X(1)-X(3))-15
403 HS(3)=ABS(X(1)-X(4))-40
405 HS(5)=ABS(X(2)-X(3))-20
406 HS(6)=ABS(X(2)-X(4))-45
409 HS(9)=ABS(X(3)-X(4))-35
413 HS(13)=ABS(X(5)-X(6))-45
414 HS(14)=ABS(X(5)-X(7))-35
415 HS(15)=ABS(X(5)-X(8))-60
417 HS(17)=ABS(X(6)-X(7))-30
418 HS(18)=ABS(X(6)-X(8))-55
421 HS(21)=ABS(X(7)-X(8))-45
551 IF HS(1)<-.0001 AND HS(13)<-.0001 THEN TL(1)=999999! ELSE TL(1)=0
553 IF HS(2)<-.0001 AND HS(14)<-.0001 THEN TL(2)=999999! ELSE TL(2)=0
554 IF HS(3)<-.0001 AND HS(15)<-.0001 THEN TL(3)=999999! ELSE TL(3)=0
557 IF HS(5)<-.0001 AND HS(17)<-.0001 THEN TL(4)=999999! ELSE TL(4)=0
559 IF HS(6)<-.0001 AND HS(18)<-.0001 THEN TL(5)=999999! ELSE TL(5)=0
561 IF HS(9)<-.0001 AND HS(21)<-.0001 THEN TL(6)=999999! ELSE TL(6)=0
1611 SUMTL=0
1613 FOR IR=1 TO 6
1615 SUMTL=SUMTL+TL(IR)
1618 NEXT IR
1624 PR1=-111*ABS(X(1)-X(2))-222*ABS(X(1)-X(3))-110*ABS(X(1)-X(4))-88*ABS(X(2)-X(3))-260*ABS(X(2)-X(4))-250*ABS(X(3)-X(4))-111*ABS(X(5)-X(6))-222*ABS(X(5)-X(7))-110*ABS(X(5)-X(8))-88*ABS(X(6)-X(7))-260*ABS(X(6)-X(8))-250*ABS(X(7)-X(8))
1650 P=PR1-999*SUMTL
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 8
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1662 MM=PR1
1666 GOTO 128
1670 NEXT I
1890 IF M>-45000! THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),MM,M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced during the first 2 minutes of running is presented below. What immediately follows is a manual copy from the computer screen.
199 224 184 149 98
98 98 98 -43375 -43375
-31973
97 124 81 46 185
185 185 185 -44973 -44973
-31962
180 155 195 231 103
102 103 103 -44454 -44454
-31933
166 191 151 116 14
14 14 14 -43375 -43375
-31919
Interpreted in accordance with line 1912 and line 1914, the output through JJJJ=-31919 was produced during the first 2 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
Reference
G. C. Armour and E. S. Buffa, "A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities," Management Science 9, 294-309 (1963).
Thursday, October 1, 2009
A General Integer-Programming Computer Program Applied to a Space Allocation Problem
Jsun Yui Wong
The complete computer program listed below seeks to solve Problem P17 of Amaral (2008), which is an instance of the allocation problem of Simmons (1969). In order to have integer locations, the department lengths used in the following computer program are twice as long as the original lengths.
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466)
6 DIM T(33,33),TZ(33,33)
11 T(1,2)=23:T(1,3)=29:T(1,4)=23:T(1,5)=27:T(1,6)=23:T(1,7)=27:T(1,8)=25:T(1,9)=29:T(1,10)=26:T(1,11)=25:T(1,12)=23:T(1,13)=29:T(1,14)=23:T(1,15)=27
12 T(2,3)=12:T(2,4)=6:T(2,5)=10:T(2,6)=6:T(2,7)=10:T(2,8)=8:T(2,9)=12:T(2,10)=9:T(2,11)=8:T(2,12)=6:T(2,13)=12:T(2,14)=6:T(2,15)=10
13 T(3,4)=12:T(3,5)=16:T(3,6)=12:T(3,7)=16:T(3,8)=14:T(3,9)=18:T(3,10)=15:T(3,11)=14:T(3,12)=12:T(3,13)=18:T(3,14)=12:T(3,15)=16
14 T(4,5)=10:T(4,6)=6:T(4,7)=10:T(4,8)=8:T(4,9)=12:T(4,10)=9:T(4,11)=8:T(4,12)=6:T(4,13)=12:T(4,14)=6:T(4,15)=10
15 T(5,6)=10:T(5,7)=14:T(5,8)=12:T(5,9)=16:T(5,10)=13:T(5,11)=12:T(5,12)=10:T(5,13)=16:T(5,14)=10:T(5,15)=14
16 T(6,7)=10:T(6,8)=8:T(6,9)=12:T(6,10)=9:T(6,11)=8:T(6,12)=6:T(6,13)=12:T(6,14)=6:T(6,15)=10
17 T(7,8)=12:T(7,9)=16:T(7,10)=13:T(7,11)=12:T(7,12)=10:T(7,13)=16:T(7,14)=10:T(7,15)=14
18 T(8,9)=14:T(8,10)=11:T(8,11)=10:T(8,12)=8:T(8,13)=14:T(8,14)=8:T(8,15)=12
19 T(9,10)=15:T(9,11)=14:T(9,12)=12:T(9,13)=18:T(9,14)=12:T(9,15)=16
20 T(10,11)=11:T(10,12)=9:T(10,13)=15:T(10,14)=9:T(10,15)=13
21 T(11,12)=8:T(11,13)=14:T(11,14)=8:T(11,15)=12:T(12,13)=12:T(12,14)=6:T(12,15)=10:T(13,14)=12:T(13,15)=16:T(14,15)=10
31 T(1,16)=23:T(1,17)=27:T(2,16)=6:T(2,17)=10:T(3,16)=12:T(3,17)=16::T(4,16)=6:T(4,17)=10:T(5,16)=10:T(5,17)=14
32 T(6,16)=6:T(6,17)=10:T(7,16)=10:T(7,17)=14:T(8,16)=8:T(8,17)=12:T(9,16)=12:T(9,17)=16:T(10,16)=9
33 T(10,17)=13:T(11,16)=8:T(11,17)=12:T(12,16)=6:T(12,17)=10:T(13,16)=12:T(13,17)=16:T(14,16)=6:T(14,17)=10
34 T(15,16)=10:T(15,17)=14:T(16,17)=10
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 17
88 A(I)=FIX(RND*699)
89 NEXT I
126 REM IMAR=10+FIX(RND*32000)
128 FOR I=1 TO 32000
129 FOR KK=1 TO 17
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*17):IJM=1+FIX(RND*17):IJN=1+FIX(RND*17)
233 IF RND<.7 THEN X(IJL)=FIX(RND*699) ELSE IF RND<.05 THEN X(IJL)=A(IJL)-1-FIX(RND*2) ELSE GOTO 244
235 GOTO 351
244 X(IJM)=A(IJN):X(IJN)=A(IJM)
351 FOR K=1 TO 16
361 FOR J=K+1 TO 17
364 IF T(K,J)>ABS(X(K)-X(J)) THEN TZ(K,J)=99999! ELSE TZ(K,J)=0
366 NEXT J
399 NEXT K
1590 SUMTZ=0
1591 FOR K=1 TO 16
1594 FOR J=K+1 TO 17
1596 SUMTZ=SUMTZ+TZ(K,J)
1597 NEXT J
1598 NEXT K
1623 PR1=-0*ABS(X(1)-X(2))-5*ABS(X(1)-X(3))-0*ABS(X(1)-X(4))-5*ABS(X(1)-X(5))-2*ABS(X(1)-X(6))-10*ABS(X(1)-X(7))-3*ABS(X(1)-X(8))-1*ABS(X(1)-X(9))-5*ABS(X(1)-X(10))-5*ABS(X(1)-X(11))-5*ABS(X(1)-X(12))-0*ABS(X(1)-X(13))-0*ABS(X(1)-X(14))-5*ABS(X(1)-X(15))
1624 PR2=-3*ABS(X(2)-X(3))-10*ABS(X(2)-X(4))-5*ABS(X(2)-X(5))-1*ABS(X(2)-X(6))-5*ABS(X(2)-X(7))-1*ABS(X(2)-X(8))-2*ABS(X(2)-X(9))-4*ABS(X(2)-X(10))-2*ABS(X(2)-X(11))-5*ABS(X(2)-X(12))-0*ABS(X(2)-X(13))-10*ABS(X(2)-X(14))-10*ABS(X(2)-X(15))
1625 PR3=-2*ABS(X(3)-X(4))-0*ABS(X(3)-X(5))-5*ABS(X(3)-X(6))-2*ABS(X(3)-X(7))-4*ABS(X(3)-X(8))-4*ABS(X(3)-X(9))-5*ABS(X(3)-X(10))-0*ABS(X(3)-X(11))-0*ABS(X(3)-X(12))-0*ABS(X(3)-X(13))-5*ABS(X(3)-X(14))-1*ABS(X(3)-X(15))
1626 PR4=-1*ABS(X(4)-X(5))-0*ABS(X(4)-X(6))-5*ABS(X(4)-X(7))-2*ABS(X(4)-X(8))-1*ABS(X(4)-X(9))-0*ABS(X(4)-X(10))-10*ABS(X(4)-X(11))-2*ABS(X(4)-X(12))-2*ABS(X(4)-X(13))-0*ABS(X(4)-X(14))-2*ABS(X(4)-X(15))
1627 PR5=-5*ABS(X(5)-X(6))-6*ABS(X(5)-X(7))-5*ABS(X(5)-X(8))-2*ABS(X(5)-X(9))-5*ABS(X(5)-X(10))-2*ABS(X(5)-X(11))-0*ABS(X(5)-X(12))-5*ABS(X(5)-X(13))-1*ABS(X(5)-X(14))-1*ABS(X(5)-X(15))
1628 PR6=-5*ABS(X(6)-X(7))-2*ABS(X(6)-X(8))-1*ABS(X(6)-X(9))-6*ABS(X(6)-X(10))-0*ABS(X(6)-X(11))-0*ABS(X(6)-X(12))-10*ABS(X(6)-X(13))-0*ABS(X(6)-X(14))-2*ABS(X(6)-X(15))
1629 PR7=-0*ABS(X(7)-X(8))-0*ABS(X(7)-X(9))-0*ABS(X(7)-X(10))-5*ABS(X(7)-X(11))-10*ABS(X(7)-X(12))-2*ABS(X(7)-X(13))-2*ABS(X(7)-X(14))-5*ABS(X(7)-X(15))
1630 PR8=-1*ABS(X(8)-X(9))-1*ABS(X(8)-X(10))-10*ABS(X(8)-X(11))-10*ABS(X(8)-X(12))-2*ABS(X(8)-X(13))-0*ABS(X(8)-X(14))-10*ABS(X(8)-X(15))
1631 PR9=-2*ABS(X(9)-X(10))-0*ABS(X(9)-X(11))-3*ABS(X(9)-X(12))-5*ABS(X(9)-X(13))-5*ABS(X(9)-X(14))-0*ABS(X(9)-X(15))
1632 PR10=-5*ABS(X(10)-X(11))-5*ABS(X(10)-X(12))-0*ABS(X(10)-X(13))-5*ABS(X(10)-X(14))-1*ABS(X(10)-X(15))
1633 PR11=-5*ABS(X(11)-X(12))-2*ABS(X(11)-X(13))-5*ABS(X(11)-X(14))-1*ABS(X(11)-X(15))
1636 PR12=-2*ABS(X(12)-X(13))-10*ABS(X(12)-X(14))-5*ABS(X(12)-X(15))-2*ABS(X(13)-X(14))-2*ABS(X(13)-X(15))-5*ABS(X(14)-X(15))
1638 PR21=-4*ABS(X(1)-X(16))-4*ABS(X(1)-X(17))-3*ABS(X(2)-X(16))-0*ABS(X(2)-X(17))-0*ABS(X(3)-X(16))-0*ABS(X(3)-X(17))-1*ABS(X(4)-X(16))-5*ABS(X(4)-X(17))
1639 PR22=-1*ABS(X(5)-X(16))-5*ABS(X(5)-X(17))-0*ABS(X(6)-X(16))-1*ABS(X(6)-X(17))-1*ABS(X(7)-X(16))-2*ABS(X(7)-X(17))-2*ABS(X(8)-X(16))-5*ABS(X(8)-X(17))
1640 PR23= -5*ABS(X(9)-X(16))-0*ABS(X(9)-X(17))-0*ABS(X(10)-X(16))-0*ABS(X(10)-X(17))-10*ABS(X(11)-X(16))-0*ABS(X(11)-X(17))-0*ABS(X(12)-X(16))-1*ABS(X(12)-X(17))
1642 PR24=-1*ABS(X(13)-X(16))-0*ABS(X(13)-X(17))
1643 PR25=-5*ABS(X(14)-X(16))-1*ABS(X(14)-X(17))-3*ABS(X(15)-X(16))-0*ABS(X(15)-X(17))-0*ABS(X(16)-X(17))
1650 P=PR1+PR2+PR3+PR4+PR5+PR6+PR7+PR8+PR9+PR10+PR11+PR12+PR21+PR22+PR23+PR24+PR25-SUMTZ
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 17
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-18577 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9),A(10)
1914 PRINT A(11),A(12),A(13),A(14),A(15)
1915 PRINT A(16),A(17),M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW-BASIC 3.11 interpreter, and the output produced within the first twelve hours of running is presented below. What immediately follows is a manual copy from the computer screen.
419 316 266 328 300
278 378 352 230 287
336 344 248 310 364
322 392 -18508 -31829
187 298 340 292 228
328 242 268 376 319
284 276 358 310 256
304 214 -18552 -31753
18508 is optimal, Amaral (2008, p. 1030). Interpreted in accordance with line 1912 through line 1915, the output above was produced within the first twelve hours of running on a personal computer with an Intel 2.66 GHz. chip and the Microsoft interpreter, which is not a compiler.
References
Amaral, A. R. S., 2006. On the exact solution of a facility layout problem. European Journal of Operational Research 173, 508-518.
Amaral, A. R. S., 2008. An exact approach to the one-dimensional facility layout problem. Operations Research 56, 1026-1033.
Heragu, S. S., A. Kusiak, 1991. Efficient models for the facility layout problem. European Journal of Operational Research 53, 1-13.
Simmons, D. M., 1969. One-dimensioanl space allocation: An ordering algorithm. Operations Research 17, 812-826.
Postscript: Line 233 of the present post and line 233 of the preceding post are noteworthy.
The complete computer program listed below seeks to solve Problem P17 of Amaral (2008), which is an instance of the allocation problem of Simmons (1969). In order to have integer locations, the department lengths used in the following computer program are twice as long as the original lengths.
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466)
6 DIM T(33,33),TZ(33,33)
11 T(1,2)=23:T(1,3)=29:T(1,4)=23:T(1,5)=27:T(1,6)=23:T(1,7)=27:T(1,8)=25:T(1,9)=29:T(1,10)=26:T(1,11)=25:T(1,12)=23:T(1,13)=29:T(1,14)=23:T(1,15)=27
12 T(2,3)=12:T(2,4)=6:T(2,5)=10:T(2,6)=6:T(2,7)=10:T(2,8)=8:T(2,9)=12:T(2,10)=9:T(2,11)=8:T(2,12)=6:T(2,13)=12:T(2,14)=6:T(2,15)=10
13 T(3,4)=12:T(3,5)=16:T(3,6)=12:T(3,7)=16:T(3,8)=14:T(3,9)=18:T(3,10)=15:T(3,11)=14:T(3,12)=12:T(3,13)=18:T(3,14)=12:T(3,15)=16
14 T(4,5)=10:T(4,6)=6:T(4,7)=10:T(4,8)=8:T(4,9)=12:T(4,10)=9:T(4,11)=8:T(4,12)=6:T(4,13)=12:T(4,14)=6:T(4,15)=10
15 T(5,6)=10:T(5,7)=14:T(5,8)=12:T(5,9)=16:T(5,10)=13:T(5,11)=12:T(5,12)=10:T(5,13)=16:T(5,14)=10:T(5,15)=14
16 T(6,7)=10:T(6,8)=8:T(6,9)=12:T(6,10)=9:T(6,11)=8:T(6,12)=6:T(6,13)=12:T(6,14)=6:T(6,15)=10
17 T(7,8)=12:T(7,9)=16:T(7,10)=13:T(7,11)=12:T(7,12)=10:T(7,13)=16:T(7,14)=10:T(7,15)=14
18 T(8,9)=14:T(8,10)=11:T(8,11)=10:T(8,12)=8:T(8,13)=14:T(8,14)=8:T(8,15)=12
19 T(9,10)=15:T(9,11)=14:T(9,12)=12:T(9,13)=18:T(9,14)=12:T(9,15)=16
20 T(10,11)=11:T(10,12)=9:T(10,13)=15:T(10,14)=9:T(10,15)=13
21 T(11,12)=8:T(11,13)=14:T(11,14)=8:T(11,15)=12:T(12,13)=12:T(12,14)=6:T(12,15)=10:T(13,14)=12:T(13,15)=16:T(14,15)=10
31 T(1,16)=23:T(1,17)=27:T(2,16)=6:T(2,17)=10:T(3,16)=12:T(3,17)=16::T(4,16)=6:T(4,17)=10:T(5,16)=10:T(5,17)=14
32 T(6,16)=6:T(6,17)=10:T(7,16)=10:T(7,17)=14:T(8,16)=8:T(8,17)=12:T(9,16)=12:T(9,17)=16:T(10,16)=9
33 T(10,17)=13:T(11,16)=8:T(11,17)=12:T(12,16)=6:T(12,17)=10:T(13,16)=12:T(13,17)=16:T(14,16)=6:T(14,17)=10
34 T(15,16)=10:T(15,17)=14:T(16,17)=10
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 17
88 A(I)=FIX(RND*699)
89 NEXT I
126 REM IMAR=10+FIX(RND*32000)
128 FOR I=1 TO 32000
129 FOR KK=1 TO 17
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*17):IJM=1+FIX(RND*17):IJN=1+FIX(RND*17)
233 IF RND<.7 THEN X(IJL)=FIX(RND*699) ELSE IF RND<.05 THEN X(IJL)=A(IJL)-1-FIX(RND*2) ELSE GOTO 244
235 GOTO 351
244 X(IJM)=A(IJN):X(IJN)=A(IJM)
351 FOR K=1 TO 16
361 FOR J=K+1 TO 17
364 IF T(K,J)>ABS(X(K)-X(J)) THEN TZ(K,J)=99999! ELSE TZ(K,J)=0
366 NEXT J
399 NEXT K
1590 SUMTZ=0
1591 FOR K=1 TO 16
1594 FOR J=K+1 TO 17
1596 SUMTZ=SUMTZ+TZ(K,J)
1597 NEXT J
1598 NEXT K
1623 PR1=-0*ABS(X(1)-X(2))-5*ABS(X(1)-X(3))-0*ABS(X(1)-X(4))-5*ABS(X(1)-X(5))-2*ABS(X(1)-X(6))-10*ABS(X(1)-X(7))-3*ABS(X(1)-X(8))-1*ABS(X(1)-X(9))-5*ABS(X(1)-X(10))-5*ABS(X(1)-X(11))-5*ABS(X(1)-X(12))-0*ABS(X(1)-X(13))-0*ABS(X(1)-X(14))-5*ABS(X(1)-X(15))
1624 PR2=-3*ABS(X(2)-X(3))-10*ABS(X(2)-X(4))-5*ABS(X(2)-X(5))-1*ABS(X(2)-X(6))-5*ABS(X(2)-X(7))-1*ABS(X(2)-X(8))-2*ABS(X(2)-X(9))-4*ABS(X(2)-X(10))-2*ABS(X(2)-X(11))-5*ABS(X(2)-X(12))-0*ABS(X(2)-X(13))-10*ABS(X(2)-X(14))-10*ABS(X(2)-X(15))
1625 PR3=-2*ABS(X(3)-X(4))-0*ABS(X(3)-X(5))-5*ABS(X(3)-X(6))-2*ABS(X(3)-X(7))-4*ABS(X(3)-X(8))-4*ABS(X(3)-X(9))-5*ABS(X(3)-X(10))-0*ABS(X(3)-X(11))-0*ABS(X(3)-X(12))-0*ABS(X(3)-X(13))-5*ABS(X(3)-X(14))-1*ABS(X(3)-X(15))
1626 PR4=-1*ABS(X(4)-X(5))-0*ABS(X(4)-X(6))-5*ABS(X(4)-X(7))-2*ABS(X(4)-X(8))-1*ABS(X(4)-X(9))-0*ABS(X(4)-X(10))-10*ABS(X(4)-X(11))-2*ABS(X(4)-X(12))-2*ABS(X(4)-X(13))-0*ABS(X(4)-X(14))-2*ABS(X(4)-X(15))
1627 PR5=-5*ABS(X(5)-X(6))-6*ABS(X(5)-X(7))-5*ABS(X(5)-X(8))-2*ABS(X(5)-X(9))-5*ABS(X(5)-X(10))-2*ABS(X(5)-X(11))-0*ABS(X(5)-X(12))-5*ABS(X(5)-X(13))-1*ABS(X(5)-X(14))-1*ABS(X(5)-X(15))
1628 PR6=-5*ABS(X(6)-X(7))-2*ABS(X(6)-X(8))-1*ABS(X(6)-X(9))-6*ABS(X(6)-X(10))-0*ABS(X(6)-X(11))-0*ABS(X(6)-X(12))-10*ABS(X(6)-X(13))-0*ABS(X(6)-X(14))-2*ABS(X(6)-X(15))
1629 PR7=-0*ABS(X(7)-X(8))-0*ABS(X(7)-X(9))-0*ABS(X(7)-X(10))-5*ABS(X(7)-X(11))-10*ABS(X(7)-X(12))-2*ABS(X(7)-X(13))-2*ABS(X(7)-X(14))-5*ABS(X(7)-X(15))
1630 PR8=-1*ABS(X(8)-X(9))-1*ABS(X(8)-X(10))-10*ABS(X(8)-X(11))-10*ABS(X(8)-X(12))-2*ABS(X(8)-X(13))-0*ABS(X(8)-X(14))-10*ABS(X(8)-X(15))
1631 PR9=-2*ABS(X(9)-X(10))-0*ABS(X(9)-X(11))-3*ABS(X(9)-X(12))-5*ABS(X(9)-X(13))-5*ABS(X(9)-X(14))-0*ABS(X(9)-X(15))
1632 PR10=-5*ABS(X(10)-X(11))-5*ABS(X(10)-X(12))-0*ABS(X(10)-X(13))-5*ABS(X(10)-X(14))-1*ABS(X(10)-X(15))
1633 PR11=-5*ABS(X(11)-X(12))-2*ABS(X(11)-X(13))-5*ABS(X(11)-X(14))-1*ABS(X(11)-X(15))
1636 PR12=-2*ABS(X(12)-X(13))-10*ABS(X(12)-X(14))-5*ABS(X(12)-X(15))-2*ABS(X(13)-X(14))-2*ABS(X(13)-X(15))-5*ABS(X(14)-X(15))
1638 PR21=-4*ABS(X(1)-X(16))-4*ABS(X(1)-X(17))-3*ABS(X(2)-X(16))-0*ABS(X(2)-X(17))-0*ABS(X(3)-X(16))-0*ABS(X(3)-X(17))-1*ABS(X(4)-X(16))-5*ABS(X(4)-X(17))
1639 PR22=-1*ABS(X(5)-X(16))-5*ABS(X(5)-X(17))-0*ABS(X(6)-X(16))-1*ABS(X(6)-X(17))-1*ABS(X(7)-X(16))-2*ABS(X(7)-X(17))-2*ABS(X(8)-X(16))-5*ABS(X(8)-X(17))
1640 PR23= -5*ABS(X(9)-X(16))-0*ABS(X(9)-X(17))-0*ABS(X(10)-X(16))-0*ABS(X(10)-X(17))-10*ABS(X(11)-X(16))-0*ABS(X(11)-X(17))-0*ABS(X(12)-X(16))-1*ABS(X(12)-X(17))
1642 PR24=-1*ABS(X(13)-X(16))-0*ABS(X(13)-X(17))
1643 PR25=-5*ABS(X(14)-X(16))-1*ABS(X(14)-X(17))-3*ABS(X(15)-X(16))-0*ABS(X(15)-X(17))-0*ABS(X(16)-X(17))
1650 P=PR1+PR2+PR3+PR4+PR5+PR6+PR7+PR8+PR9+PR10+PR11+PR12+PR21+PR22+PR23+PR24+PR25-SUMTZ
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 17
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-18577 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9),A(10)
1914 PRINT A(11),A(12),A(13),A(14),A(15)
1915 PRINT A(16),A(17),M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW-BASIC 3.11 interpreter, and the output produced within the first twelve hours of running is presented below. What immediately follows is a manual copy from the computer screen.
419 316 266 328 300
278 378 352 230 287
336 344 248 310 364
322 392 -18508 -31829
187 298 340 292 228
328 242 268 376 319
284 276 358 310 256
304 214 -18552 -31753
18508 is optimal, Amaral (2008, p. 1030). Interpreted in accordance with line 1912 through line 1915, the output above was produced within the first twelve hours of running on a personal computer with an Intel 2.66 GHz. chip and the Microsoft interpreter, which is not a compiler.
References
Amaral, A. R. S., 2006. On the exact solution of a facility layout problem. European Journal of Operational Research 173, 508-518.
Amaral, A. R. S., 2008. An exact approach to the one-dimensional facility layout problem. Operations Research 56, 1026-1033.
Heragu, S. S., A. Kusiak, 1991. Efficient models for the facility layout problem. European Journal of Operational Research 53, 1-13.
Simmons, D. M., 1969. One-dimensioanl space allocation: An ordering algorithm. Operations Research 17, 812-826.
Postscript: Line 233 of the present post and line 233 of the preceding post are noteworthy.
A Computer Program Illustrating an Ordering Algorithm for Eighteen Departments, Third Edition
Jsun Yui Wong
The complete computer program listed below seeks to solve Problem P18 of Amaral (2008), which is an instance of the allocation problem of Simmons (1969). In order to have integer locations, the department lengths used in the following computer program are twice as long as the original lengths.
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466)
6 DIM T(33,33),TZ(33,33)
11 T(1,2)=23:T(1,3)=29:T(1,4)=23:T(1,5)=27:T(1,6)=23:T(1,7)=27:T(1,8)=25:T(1,9)=29:T(1,10)=26:T(1,11)=25:T(1,12)=23:T(1,13)=29:T(1,14)=23:T(1,15)=27
12 T(2,3)=12:T(2,4)=6:T(2,5)=10:T(2,6)=6:T(2,7)=10:T(2,8)=8:T(2,9)=12:T(2,10)=9:T(2,11)=8:T(2,12)=6:T(2,13)=12:T(2,14)=6:T(2,15)=10
13 T(3,4)=12:T(3,5)=16:T(3,6)=12:T(3,7)=16:T(3,8)=14:T(3,9)=18:T(3,10)=15:T(3,11)=14:T(3,12)=12:T(3,13)=18:T(3,14)=12:T(3,15)=16
14 T(4,5)=10:T(4,6)=6:T(4,7)=10:T(4,8)=8:T(4,9)=12:T(4,10)=9:T(4,11)=8:T(4,12)=6:T(4,13)=12:T(4,14)=6:T(4,15)=10
15 T(5,6)=10:T(5,7)=14:T(5,8)=12:T(5,9)=16:T(5,10)=13:T(5,11)=12:T(5,12)=10:T(5,13)=16:T(5,14)=10:T(5,15)=14
16 T(6,7)=10:T(6,8)=8:T(6,9)=12:T(6,10)=9:T(6,11)=8:T(6,12)=6:T(6,13)=12:T(6,14)=6:T(6,15)=10
17 T(7,8)=12:T(7,9)=16:T(7,10)=13:T(7,11)=12:T(7,12)=10:T(7,13)=16:T(7,14)=10:T(7,15)=14
18 T(8,9)=14:T(8,10)=11:T(8,11)=10:T(8,12)=8:T(8,13)=14:T(8,14)=8:T(8,15)=12
19 T(9,10)=15:T(9,11)=14:T(9,12)=12:T(9,13)=18:T(9,14)=12:T(9,15)=16
20 T(10,11)=11:T(10,12)=9:T(10,13)=15:T(10,14)=9:T(10,15)=13
21 T(11,12)=8:T(11,13)=14:T(11,14)=8:T(11,15)=12:T(12,13)=12:T(12,14)=6:T(12,15)=10:T(13,14)=12:T(13,15)=16:T(14,15)=10
31 T(1,16)=23:T(1,17)=27:T(1,18)=25:T(2,16)=6:T(2,17)=10:T(2,18)=8:T(3,16)=12:T(3,17)=16:T(3,18)=14:T(4,16)=6:T(4,17)=10:T(4,18)=8:T(5,16)=10:T(5,17)=14
32 T(5,18)=12:T(6,16)=6:T(6,17)=10:T(6,18)=8:T(7,16)=10:T(7,17)=14:T(7,18)=12:T(8,16)=8:T(8,17)=12:T(8,18)=10:T(9,16)=12:T(9,17)=16:T(9,18)=14:T(10,16)=9
33 T(10,17)=13:T(10,18)=11:T(11,16)=8:T(11,17)=12:T(11,18)=10:T(12,16)=6:T(12,17)=10:T(12,18)=8:T(13,16)=12:T(13,17)=16:T(13,18)=14:T(14,16)=6:T(14,17)=10
34 T(14,18)=8:T(15,16)=10:T(15,17)=14:T(15,18)=12:T(16,17)=10:T(16,18)=8:T(17,18)=12
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 18
88 A(I)=FIX(RND*699)
89 NEXT I
126 REM IMAR=10+FIX(RND*32000)
128 FOR I=1 TO 32000
129 FOR KK=1 TO 18
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*18):IJM=1+FIX(RND*18):IJN=1+FIX(RND*18)
233 IF RND<.7 THEN X(IJL)=FIX(RND*699) ELSE IF RND<.05 THEN X(IJL)=A(IJL)-1-FIX(RND*2) ELSE GOTO 244
235 GOTO 351
244 X(IJM)=A(IJN):X(IJN)=A(IJM)
351 FOR K=1 TO 17
361 FOR J=K+1 TO 18
364 IF T(K,J)>ABS(X(K)-X(J)) THEN TZ(K,J)=99999! ELSE TZ(K,J)=0
366 NEXT J
399 NEXT K
1590 SUMTZ=0
1591 FOR K=1 TO 17
1594 FOR J=K+1 TO 18
1596 SUMTZ=SUMTZ+TZ(K,J)
1597 NEXT J
1598 NEXT K
1623 PR1=-0*ABS(X(1)-X(2))-5*ABS(X(1)-X(3))-0*ABS(X(1)-X(4))-5*ABS(X(1)-X(5))-2*ABS(X(1)-X(6))-10*ABS(X(1)-X(7))-3*ABS(X(1)-X(8))-1*ABS(X(1)-X(9))-5*ABS(X(1)-X(10))-5*ABS(X(1)-X(11))-5*ABS(X(1)-X(12))-0*ABS(X(1)-X(13))-0*ABS(X(1)-X(14))-5*ABS(X(1)-X(15))
1624 PR2=-3*ABS(X(2)-X(3))-10*ABS(X(2)-X(4))-5*ABS(X(2)-X(5))-1*ABS(X(2)-X(6))-5*ABS(X(2)-X(7))-1*ABS(X(2)-X(8))-2*ABS(X(2)-X(9))-4*ABS(X(2)-X(10))-2*ABS(X(2)-X(11))-5*ABS(X(2)-X(12))-0*ABS(X(2)-X(13))-10*ABS(X(2)-X(14))-10*ABS(X(2)-X(15))
1625 PR3=-2*ABS(X(3)-X(4))-0*ABS(X(3)-X(5))-5*ABS(X(3)-X(6))-2*ABS(X(3)-X(7))-4*ABS(X(3)-X(8))-4*ABS(X(3)-X(9))-5*ABS(X(3)-X(10))-0*ABS(X(3)-X(11))-0*ABS(X(3)-X(12))-0*ABS(X(3)-X(13))-5*ABS(X(3)-X(14))-1*ABS(X(3)-X(15))
1626 PR4=-1*ABS(X(4)-X(5))-0*ABS(X(4)-X(6))-5*ABS(X(4)-X(7))-2*ABS(X(4)-X(8))-1*ABS(X(4)-X(9))-0*ABS(X(4)-X(10))-10*ABS(X(4)-X(11))-2*ABS(X(4)-X(12))-2*ABS(X(4)-X(13))-0*ABS(X(4)-X(14))-2*ABS(X(4)-X(15))
1627 PR5=-5*ABS(X(5)-X(6))-6*ABS(X(5)-X(7))-5*ABS(X(5)-X(8))-2*ABS(X(5)-X(9))-5*ABS(X(5)-X(10))-2*ABS(X(5)-X(11))-0*ABS(X(5)-X(12))-5*ABS(X(5)-X(13))-1*ABS(X(5)-X(14))-1*ABS(X(5)-X(15))
1628 PR6=-5*ABS(X(6)-X(7))-2*ABS(X(6)-X(8))-1*ABS(X(6)-X(9))-6*ABS(X(6)-X(10))-0*ABS(X(6)-X(11))-0*ABS(X(6)-X(12))-10*ABS(X(6)-X(13))-0*ABS(X(6)-X(14))-2*ABS(X(6)-X(15))
1629 PR7=-0*ABS(X(7)-X(8))-0*ABS(X(7)-X(9))-0*ABS(X(7)-X(10))-5*ABS(X(7)-X(11))-10*ABS(X(7)-X(12))-2*ABS(X(7)-X(13))-2*ABS(X(7)-X(14))-5*ABS(X(7)-X(15))
1630 PR8=-1*ABS(X(8)-X(9))-1*ABS(X(8)-X(10))-10*ABS(X(8)-X(11))-10*ABS(X(8)-X(12))-2*ABS(X(8)-X(13))-0*ABS(X(8)-X(14))-10*ABS(X(8)-X(15))
1631 PR9=-2*ABS(X(9)-X(10))-0*ABS(X(9)-X(11))-3*ABS(X(9)-X(12))-5*ABS(X(9)-X(13))-5*ABS(X(9)-X(14))-0*ABS(X(9)-X(15))
1632 PR10=-5*ABS(X(10)-X(11))-5*ABS(X(10)-X(12))-0*ABS(X(10)-X(13))-5*ABS(X(10)-X(14))-1*ABS(X(10)-X(15))
1633 PR11=-5*ABS(X(11)-X(12))-2*ABS(X(11)-X(13))-5*ABS(X(11)-X(14))-1*ABS(X(11)-X(15))
1636 PR12=-2*ABS(X(12)-X(13))-10*ABS(X(12)-X(14))-5*ABS(X(12)-X(15))-2*ABS(X(13)-X(14))-2*ABS(X(13)-X(15))-5*ABS(X(14)-X(15))
1638 PR21=-4*ABS(X(1)-X(16))-4*ABS(X(1)-X(17))-0*ABS(X(1)-X(18))-3*ABS(X(2)-X(16))-0*ABS(X(2)-X(17))-5*ABS(X(2)-X(18))-0*ABS(X(3)-X(16))-0*ABS(X(3)-X(17))-5*ABS(X(3)-X(18))-1*ABS(X(4)-X(16))-5*ABS(X(4)-X(17))-2*ABS(X(4)-X(18))
1639 PR22=-1*ABS(X(5)-X(16))-5*ABS(X(5)-X(17))-2*ABS(X(5)-X(18))-0*ABS(X(6)-X(16))-1*ABS(X(6)-X(17))-0*ABS(X(6)-X(18))-1*ABS(X(7)-X(16))-2*ABS(X(7)-X(17))-1*ABS(X(7)-X(18))-2*ABS(X(8)-X(16))-5*ABS(X(8)-X(17))-2*ABS(X(8)-X(18))
1640 PR23=-5*ABS(X(9)-X(16))-0*ABS(X(9)-X(17))-0*ABS(X(9)-X(18))-0*ABS(X(10)-X(16))-0*ABS(X(10)-X(17))-5*ABS(X(10)-X(18))-10*ABS(X(11)-X(16))-0*ABS(X(11)-X(17))-2*ABS(X(11)-X(18))-0*ABS(X(12)-X(16))-1*ABS(X(12)-X(17))-1*ABS(X(12)-X(18))
1642 PR24=-1*ABS(X(13)-X(16))-0*ABS(X(13)-X(17))-0*ABS(X(13)-X(18))
1643 PR25=-5*ABS(X(14)-X(16))-1*ABS(X(14)-X(17))-5*ABS(X(14)-X(18))-3*ABS(X(15)-X(16))-0*ABS(X(15)-X(17))-5*ABS(X(15)-X(18))-0*ABS(X(16)-X(17))-0*ABS(X(16)-X(18))-5*ABS(X(17)-X(18))
1650 P=PR1+PR2+PR3+PR4+PR5+PR6+PR7+PR8+PR9+PR10+PR11+PR12+PR21+PR22+PR23+PR24+PR25-SUMTZ
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 18
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-21500 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9),A(10)
1914 PRINT A(11),A(12),A(13),A(14),A(15)
1915 PRINT A(16),A(17),A(18),M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW-BASIC 3.11 interpreter, and the output produced within the first ten hours of running is presented below. What immediately follows is a manual copy from the computer screen.
443 332 280 358 402
292 388 376 244 301
366 352 262 320 342
326 416 312 -21441 -31958
331 448 494 396 372
482 386 420 530 473
404 428 512 454 438
412 358 462 -21301 -31922
443 354 280 392 314
292 402 368 244 301
384 360 262 334 344
376 416 326 -21499 -31881
470 367 307 379 341
319 429 397 271 328
387 405 289 361 415
373 443 353 -21391 -31820
21301 is optimal, Amaral (2008, p. 1030). Interpreted in accordance with line 1912 through line 1915, the output through JJJJ=-31820 was produced within the first ten hours of running on a personal computer with an Intel 2.66 GHz. chip and the Microsoft interpreter, which is not a compiler.
References
Amaral, A. R. S., 2006. On the exact solution of a facility layout problem. European Journal of Operational Research 173, 508-518.
Amaral, A. R. S., 2008. An exact approach to the one-dimensional facility layout problem. Operations Research 56, 1026-1033.
Heragu, S. S., A. Kusiak, 1991. Efficient models for the facility layout problem. European Journal of Operational Research 53, 1-13.
Simmons, D. M., 1969. One-dimensioanl space allocation: An ordering algorithm. Operations Research 17, 812-826.
The complete computer program listed below seeks to solve Problem P18 of Amaral (2008), which is an instance of the allocation problem of Simmons (1969). In order to have integer locations, the department lengths used in the following computer program are twice as long as the original lengths.
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466)
6 DIM T(33,33),TZ(33,33)
11 T(1,2)=23:T(1,3)=29:T(1,4)=23:T(1,5)=27:T(1,6)=23:T(1,7)=27:T(1,8)=25:T(1,9)=29:T(1,10)=26:T(1,11)=25:T(1,12)=23:T(1,13)=29:T(1,14)=23:T(1,15)=27
12 T(2,3)=12:T(2,4)=6:T(2,5)=10:T(2,6)=6:T(2,7)=10:T(2,8)=8:T(2,9)=12:T(2,10)=9:T(2,11)=8:T(2,12)=6:T(2,13)=12:T(2,14)=6:T(2,15)=10
13 T(3,4)=12:T(3,5)=16:T(3,6)=12:T(3,7)=16:T(3,8)=14:T(3,9)=18:T(3,10)=15:T(3,11)=14:T(3,12)=12:T(3,13)=18:T(3,14)=12:T(3,15)=16
14 T(4,5)=10:T(4,6)=6:T(4,7)=10:T(4,8)=8:T(4,9)=12:T(4,10)=9:T(4,11)=8:T(4,12)=6:T(4,13)=12:T(4,14)=6:T(4,15)=10
15 T(5,6)=10:T(5,7)=14:T(5,8)=12:T(5,9)=16:T(5,10)=13:T(5,11)=12:T(5,12)=10:T(5,13)=16:T(5,14)=10:T(5,15)=14
16 T(6,7)=10:T(6,8)=8:T(6,9)=12:T(6,10)=9:T(6,11)=8:T(6,12)=6:T(6,13)=12:T(6,14)=6:T(6,15)=10
17 T(7,8)=12:T(7,9)=16:T(7,10)=13:T(7,11)=12:T(7,12)=10:T(7,13)=16:T(7,14)=10:T(7,15)=14
18 T(8,9)=14:T(8,10)=11:T(8,11)=10:T(8,12)=8:T(8,13)=14:T(8,14)=8:T(8,15)=12
19 T(9,10)=15:T(9,11)=14:T(9,12)=12:T(9,13)=18:T(9,14)=12:T(9,15)=16
20 T(10,11)=11:T(10,12)=9:T(10,13)=15:T(10,14)=9:T(10,15)=13
21 T(11,12)=8:T(11,13)=14:T(11,14)=8:T(11,15)=12:T(12,13)=12:T(12,14)=6:T(12,15)=10:T(13,14)=12:T(13,15)=16:T(14,15)=10
31 T(1,16)=23:T(1,17)=27:T(1,18)=25:T(2,16)=6:T(2,17)=10:T(2,18)=8:T(3,16)=12:T(3,17)=16:T(3,18)=14:T(4,16)=6:T(4,17)=10:T(4,18)=8:T(5,16)=10:T(5,17)=14
32 T(5,18)=12:T(6,16)=6:T(6,17)=10:T(6,18)=8:T(7,16)=10:T(7,17)=14:T(7,18)=12:T(8,16)=8:T(8,17)=12:T(8,18)=10:T(9,16)=12:T(9,17)=16:T(9,18)=14:T(10,16)=9
33 T(10,17)=13:T(10,18)=11:T(11,16)=8:T(11,17)=12:T(11,18)=10:T(12,16)=6:T(12,17)=10:T(12,18)=8:T(13,16)=12:T(13,17)=16:T(13,18)=14:T(14,16)=6:T(14,17)=10
34 T(14,18)=8:T(15,16)=10:T(15,17)=14:T(15,18)=12:T(16,17)=10:T(16,18)=8:T(17,18)=12
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 18
88 A(I)=FIX(RND*699)
89 NEXT I
126 REM IMAR=10+FIX(RND*32000)
128 FOR I=1 TO 32000
129 FOR KK=1 TO 18
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*18):IJM=1+FIX(RND*18):IJN=1+FIX(RND*18)
233 IF RND<.7 THEN X(IJL)=FIX(RND*699) ELSE IF RND<.05 THEN X(IJL)=A(IJL)-1-FIX(RND*2) ELSE GOTO 244
235 GOTO 351
244 X(IJM)=A(IJN):X(IJN)=A(IJM)
351 FOR K=1 TO 17
361 FOR J=K+1 TO 18
364 IF T(K,J)>ABS(X(K)-X(J)) THEN TZ(K,J)=99999! ELSE TZ(K,J)=0
366 NEXT J
399 NEXT K
1590 SUMTZ=0
1591 FOR K=1 TO 17
1594 FOR J=K+1 TO 18
1596 SUMTZ=SUMTZ+TZ(K,J)
1597 NEXT J
1598 NEXT K
1623 PR1=-0*ABS(X(1)-X(2))-5*ABS(X(1)-X(3))-0*ABS(X(1)-X(4))-5*ABS(X(1)-X(5))-2*ABS(X(1)-X(6))-10*ABS(X(1)-X(7))-3*ABS(X(1)-X(8))-1*ABS(X(1)-X(9))-5*ABS(X(1)-X(10))-5*ABS(X(1)-X(11))-5*ABS(X(1)-X(12))-0*ABS(X(1)-X(13))-0*ABS(X(1)-X(14))-5*ABS(X(1)-X(15))
1624 PR2=-3*ABS(X(2)-X(3))-10*ABS(X(2)-X(4))-5*ABS(X(2)-X(5))-1*ABS(X(2)-X(6))-5*ABS(X(2)-X(7))-1*ABS(X(2)-X(8))-2*ABS(X(2)-X(9))-4*ABS(X(2)-X(10))-2*ABS(X(2)-X(11))-5*ABS(X(2)-X(12))-0*ABS(X(2)-X(13))-10*ABS(X(2)-X(14))-10*ABS(X(2)-X(15))
1625 PR3=-2*ABS(X(3)-X(4))-0*ABS(X(3)-X(5))-5*ABS(X(3)-X(6))-2*ABS(X(3)-X(7))-4*ABS(X(3)-X(8))-4*ABS(X(3)-X(9))-5*ABS(X(3)-X(10))-0*ABS(X(3)-X(11))-0*ABS(X(3)-X(12))-0*ABS(X(3)-X(13))-5*ABS(X(3)-X(14))-1*ABS(X(3)-X(15))
1626 PR4=-1*ABS(X(4)-X(5))-0*ABS(X(4)-X(6))-5*ABS(X(4)-X(7))-2*ABS(X(4)-X(8))-1*ABS(X(4)-X(9))-0*ABS(X(4)-X(10))-10*ABS(X(4)-X(11))-2*ABS(X(4)-X(12))-2*ABS(X(4)-X(13))-0*ABS(X(4)-X(14))-2*ABS(X(4)-X(15))
1627 PR5=-5*ABS(X(5)-X(6))-6*ABS(X(5)-X(7))-5*ABS(X(5)-X(8))-2*ABS(X(5)-X(9))-5*ABS(X(5)-X(10))-2*ABS(X(5)-X(11))-0*ABS(X(5)-X(12))-5*ABS(X(5)-X(13))-1*ABS(X(5)-X(14))-1*ABS(X(5)-X(15))
1628 PR6=-5*ABS(X(6)-X(7))-2*ABS(X(6)-X(8))-1*ABS(X(6)-X(9))-6*ABS(X(6)-X(10))-0*ABS(X(6)-X(11))-0*ABS(X(6)-X(12))-10*ABS(X(6)-X(13))-0*ABS(X(6)-X(14))-2*ABS(X(6)-X(15))
1629 PR7=-0*ABS(X(7)-X(8))-0*ABS(X(7)-X(9))-0*ABS(X(7)-X(10))-5*ABS(X(7)-X(11))-10*ABS(X(7)-X(12))-2*ABS(X(7)-X(13))-2*ABS(X(7)-X(14))-5*ABS(X(7)-X(15))
1630 PR8=-1*ABS(X(8)-X(9))-1*ABS(X(8)-X(10))-10*ABS(X(8)-X(11))-10*ABS(X(8)-X(12))-2*ABS(X(8)-X(13))-0*ABS(X(8)-X(14))-10*ABS(X(8)-X(15))
1631 PR9=-2*ABS(X(9)-X(10))-0*ABS(X(9)-X(11))-3*ABS(X(9)-X(12))-5*ABS(X(9)-X(13))-5*ABS(X(9)-X(14))-0*ABS(X(9)-X(15))
1632 PR10=-5*ABS(X(10)-X(11))-5*ABS(X(10)-X(12))-0*ABS(X(10)-X(13))-5*ABS(X(10)-X(14))-1*ABS(X(10)-X(15))
1633 PR11=-5*ABS(X(11)-X(12))-2*ABS(X(11)-X(13))-5*ABS(X(11)-X(14))-1*ABS(X(11)-X(15))
1636 PR12=-2*ABS(X(12)-X(13))-10*ABS(X(12)-X(14))-5*ABS(X(12)-X(15))-2*ABS(X(13)-X(14))-2*ABS(X(13)-X(15))-5*ABS(X(14)-X(15))
1638 PR21=-4*ABS(X(1)-X(16))-4*ABS(X(1)-X(17))-0*ABS(X(1)-X(18))-3*ABS(X(2)-X(16))-0*ABS(X(2)-X(17))-5*ABS(X(2)-X(18))-0*ABS(X(3)-X(16))-0*ABS(X(3)-X(17))-5*ABS(X(3)-X(18))-1*ABS(X(4)-X(16))-5*ABS(X(4)-X(17))-2*ABS(X(4)-X(18))
1639 PR22=-1*ABS(X(5)-X(16))-5*ABS(X(5)-X(17))-2*ABS(X(5)-X(18))-0*ABS(X(6)-X(16))-1*ABS(X(6)-X(17))-0*ABS(X(6)-X(18))-1*ABS(X(7)-X(16))-2*ABS(X(7)-X(17))-1*ABS(X(7)-X(18))-2*ABS(X(8)-X(16))-5*ABS(X(8)-X(17))-2*ABS(X(8)-X(18))
1640 PR23=-5*ABS(X(9)-X(16))-0*ABS(X(9)-X(17))-0*ABS(X(9)-X(18))-0*ABS(X(10)-X(16))-0*ABS(X(10)-X(17))-5*ABS(X(10)-X(18))-10*ABS(X(11)-X(16))-0*ABS(X(11)-X(17))-2*ABS(X(11)-X(18))-0*ABS(X(12)-X(16))-1*ABS(X(12)-X(17))-1*ABS(X(12)-X(18))
1642 PR24=-1*ABS(X(13)-X(16))-0*ABS(X(13)-X(17))-0*ABS(X(13)-X(18))
1643 PR25=-5*ABS(X(14)-X(16))-1*ABS(X(14)-X(17))-5*ABS(X(14)-X(18))-3*ABS(X(15)-X(16))-0*ABS(X(15)-X(17))-5*ABS(X(15)-X(18))-0*ABS(X(16)-X(17))-0*ABS(X(16)-X(18))-5*ABS(X(17)-X(18))
1650 P=PR1+PR2+PR3+PR4+PR5+PR6+PR7+PR8+PR9+PR10+PR11+PR12+PR21+PR22+PR23+PR24+PR25-SUMTZ
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 18
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-21500 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9),A(10)
1914 PRINT A(11),A(12),A(13),A(14),A(15)
1915 PRINT A(16),A(17),A(18),M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW-BASIC 3.11 interpreter, and the output produced within the first ten hours of running is presented below. What immediately follows is a manual copy from the computer screen.
443 332 280 358 402
292 388 376 244 301
366 352 262 320 342
326 416 312 -21441 -31958
331 448 494 396 372
482 386 420 530 473
404 428 512 454 438
412 358 462 -21301 -31922
443 354 280 392 314
292 402 368 244 301
384 360 262 334 344
376 416 326 -21499 -31881
470 367 307 379 341
319 429 397 271 328
387 405 289 361 415
373 443 353 -21391 -31820
21301 is optimal, Amaral (2008, p. 1030). Interpreted in accordance with line 1912 through line 1915, the output through JJJJ=-31820 was produced within the first ten hours of running on a personal computer with an Intel 2.66 GHz. chip and the Microsoft interpreter, which is not a compiler.
References
Amaral, A. R. S., 2006. On the exact solution of a facility layout problem. European Journal of Operational Research 173, 508-518.
Amaral, A. R. S., 2008. An exact approach to the one-dimensional facility layout problem. Operations Research 56, 1026-1033.
Heragu, S. S., A. Kusiak, 1991. Efficient models for the facility layout problem. European Journal of Operational Research 53, 1-13.
Simmons, D. M., 1969. One-dimensioanl space allocation: An ordering algorithm. Operations Research 17, 812-826.
Sunday, September 27, 2009
A Computer Program Illustrating an Ordering Algorithm for Eighteen Departments, Second Edition
Jsun Yui Wong
The complete computer program listed below seeks to solve Problem P18 of Amaral (2008), which is an instance of the allocation problem of Simmons (1969). In order to have integer locations, the department lengths used in the following computer program are twice as long as the original lengths.
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466)
6 DIM T(33,33),TZ(33,33)
11 T(1,2)=23:T(1,3)=29:T(1,4)=23:T(1,5)=27:T(1,6)=23:T(1,7)=27:T(1,8)=25:T(1,9)=29:T(1,10)=26:T(1,11)=25:T(1,12)=23:T(1,13)=29:T(1,14)=23:T(1,15)=27
12 T(2,3)=12:T(2,4)=6:T(2,5)=10:T(2,6)=6:T(2,7)=10:T(2,8)=8:T(2,9)=12:T(2,10)=9:T(2,11)=8:T(2,12)=6:T(2,13)=12:T(2,14)=6:T(2,15)=10
13 T(3,4)=12:T(3,5)=16:T(3,6)=12:T(3,7)=16:T(3,8)=14:T(3,9)=18:T(3,10)=15:T(3,11)=14:T(3,12)=12:T(3,13)=18:T(3,14)=12:T(3,15)=16
14 T(4,5)=10:T(4,6)=6:T(4,7)=10:T(4,8)=8:T(4,9)=12:T(4,10)=9:T(4,11)=8:T(4,12)=6:T(4,13)=12:T(4,14)=6:T(4,15)=10
15 T(5,6)=10:T(5,7)=14:T(5,8)=12:T(5,9)=16:T(5,10)=13:T(5,11)=12:T(5,12)=10:T(5,13)=16:T(5,14)=10:T(5,15)=14
16 T(6,7)=10:T(6,8)=8:T(6,9)=12:T(6,10)=9:T(6,11)=8:T(6,12)=6:T(6,13)=12:T(6,14)=6:T(6,15)=10
17 T(7,8)=12:T(7,9)=16:T(7,10)=13:T(7,11)=12:T(7,12)=10:T(7,13)=16:T(7,14)=10:T(7,15)=14
18 T(8,9)=14:T(8,10)=11:T(8,11)=10:T(8,12)=8:T(8,13)=14:T(8,14)=8:T(8,15)=12
19 T(9,10)=15:T(9,11)=14:T(9,12)=12:T(9,13)=18:T(9,14)=12:T(9,15)=16
20 T(10,11)=11:T(10,12)=9:T(10,13)=15:T(10,14)=9:T(10,15)=13
21 T(11,12)=8:T(11,13)=14:T(11,14)=8:T(11,15)=12:T(12,13)=12:T(12,14)=6:T(12,15)=10:T(13,14)=12:T(13,15)=16:T(14,15)=10
31 T(1,16)=23:T(1,17)=27:T(1,18)=25:T(2,16)=6:T(2,17)=10:T(2,18)=8:T(3,16)=12:T(3,17)=16:T(3,18)=14:T(4,16)=6:T(4,17)=10:T(4,18)=8:T(5,16)=10:T(5,17)=14
32 T(5,18)=12:T(6,16)=6:T(6,17)=10:T(6,18)=8:T(7,16)=10:T(7,17)=14:T(7,18)=12:T(8,16)=8:T(8,17)=12:T(8,18)=10:T(9,16)=12:T(9,17)=16:T(9,18)=14:T(10,16)=9
33 T(10,17)=13:T(10,18)=11:T(11,16)=8:T(11,17)=12:T(11,18)=10:T(12,16)=6:T(12,17)=10:T(12,18)=8:T(13,16)=12:T(13,17)=16:T(13,18)=14:T(14,16)=6:T(14,17)=10
34 T(14,18)=8:T(15,16)=10:T(15,17)=14:T(15,18)=12:T(16,17)=10:T(16,18)=8:T(17,18)=12
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 18
88 A(I)=FIX(RND*699)
89 NEXT I
126 REM IMAR=10+FIX(RND*32000)
128 FOR I=1 TO 32000
129 FOR KK=1 TO 18
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*18):IJM=1+FIX(RND*18):IJN=1+FIX(RND*18)
233 IF RND<.7 THEN X(IJL)=FIX(RND*699) ELSE IF RND<.05 THEN X(IJL)=A(IJL)-1 ELSE GOTO 244
235 GOTO 351
244 X(IJM)=A(IJN):X(IJN)=A(IJM)
351 FOR K=1 TO 17
361 FOR J=K+1 TO 18
364 IF T(K,J)>ABS(X(K)-X(J)) THEN TZ(K,J)=99999! ELSE TZ(K,J)=0
366 NEXT J
399 NEXT K
1590 SUMTZ=0
1591 FOR K=1 TO 17
1594 FOR J=K+1 TO 18
1596 SUMTZ=SUMTZ+TZ(K,J)
1597 NEXT J
1598 NEXT K
1623 PR1=-0*ABS(X(1)-X(2))-5*ABS(X(1)-X(3))-0*ABS(X(1)-X(4))-5*ABS(X(1)-X(5))-2*ABS(X(1)-X(6))-10*ABS(X(1)-X(7))-3*ABS(X(1)-X(8))-1*ABS(X(1)-X(9))-5*ABS(X(1)-X(10))-5*ABS(X(1)-X(11))-5*ABS(X(1)-X(12))-0*ABS(X(1)-X(13))-0*ABS(X(1)-X(14))-5*ABS(X(1)-X(15))
1624 PR2=-3*ABS(X(2)-X(3))-10*ABS(X(2)-X(4))-5*ABS(X(2)-X(5))-1*ABS(X(2)-X(6))-5*ABS(X(2)-X(7))-1*ABS(X(2)-X(8))-2*ABS(X(2)-X(9))-4*ABS(X(2)-X(10))-2*ABS(X(2)-X(11))-5*ABS(X(2)-X(12))-0*ABS(X(2)-X(13))-10*ABS(X(2)-X(14))-10*ABS(X(2)-X(15))
1625 PR3=-2*ABS(X(3)-X(4))-0*ABS(X(3)-X(5))-5*ABS(X(3)-X(6))-2*ABS(X(3)-X(7))-4*ABS(X(3)-X(8))-4*ABS(X(3)-X(9))-5*ABS(X(3)-X(10))-0*ABS(X(3)-X(11))-0*ABS(X(3)-X(12))-0*ABS(X(3)-X(13))-5*ABS(X(3)-X(14))-1*ABS(X(3)-X(15))
1626 PR4=-1*ABS(X(4)-X(5))-0*ABS(X(4)-X(6))-5*ABS(X(4)-X(7))-2*ABS(X(4)-X(8))-1*ABS(X(4)-X(9))-0*ABS(X(4)-X(10))-10*ABS(X(4)-X(11))-2*ABS(X(4)-X(12))-2*ABS(X(4)-X(13))-0*ABS(X(4)-X(14))-2*ABS(X(4)-X(15))
1627 PR5=-5*ABS(X(5)-X(6))-6*ABS(X(5)-X(7))-5*ABS(X(5)-X(8))-2*ABS(X(5)-X(9))-5*ABS(X(5)-X(10))-2*ABS(X(5)-X(11))-0*ABS(X(5)-X(12))-5*ABS(X(5)-X(13))-1*ABS(X(5)-X(14))-1*ABS(X(5)-X(15))
1628 PR6=-5*ABS(X(6)-X(7))-2*ABS(X(6)-X(8))-1*ABS(X(6)-X(9))-6*ABS(X(6)-X(10))-0*ABS(X(6)-X(11))-0*ABS(X(6)-X(12))-10*ABS(X(6)-X(13))-0*ABS(X(6)-X(14))-2*ABS(X(6)-X(15))
1629 PR7=-0*ABS(X(7)-X(8))-0*ABS(X(7)-X(9))-0*ABS(X(7)-X(10))-5*ABS(X(7)-X(11))-10*ABS(X(7)-X(12))-2*ABS(X(7)-X(13))-2*ABS(X(7)-X(14))-5*ABS(X(7)-X(15))
1630 PR8=-1*ABS(X(8)-X(9))-1*ABS(X(8)-X(10))-10*ABS(X(8)-X(11))-10*ABS(X(8)-X(12))-2*ABS(X(8)-X(13))-0*ABS(X(8)-X(14))-10*ABS(X(8)-X(15))
1631 PR9=-2*ABS(X(9)-X(10))-0*ABS(X(9)-X(11))-3*ABS(X(9)-X(12))-5*ABS(X(9)-X(13))-5*ABS(X(9)-X(14))-0*ABS(X(9)-X(15))
1632 PR10=-5*ABS(X(10)-X(11))-5*ABS(X(10)-X(12))-0*ABS(X(10)-X(13))-5*ABS(X(10)-X(14))-1*ABS(X(10)-X(15))
1633 PR11=-5*ABS(X(11)-X(12))-2*ABS(X(11)-X(13))-5*ABS(X(11)-X(14))-1*ABS(X(11)-X(15))
1636 PR12=-2*ABS(X(12)-X(13))-10*ABS(X(12)-X(14))-5*ABS(X(12)-X(15))-2*ABS(X(13)-X(14))-2*ABS(X(13)-X(15))-5*ABS(X(14)-X(15))
1638 PR21=-4*ABS(X(1)-X(16))-4*ABS(X(1)-X(17))-0*ABS(X(1)-X(18))-3*ABS(X(2)-X(16))-0*ABS(X(2)-X(17))-5*ABS(X(2)-X(18))-0*ABS(X(3)-X(16))-0*ABS(X(3)-X(17))-5*ABS(X(3)-X(18))-1*ABS(X(4)-X(16))-5*ABS(X(4)-X(17))-2*ABS(X(4)-X(18))
1639 PR22=-1*ABS(X(5)-X(16))-5*ABS(X(5)-X(17))-2*ABS(X(5)-X(18))-0*ABS(X(6)-X(16))-1*ABS(X(6)-X(17))-0*ABS(X(6)-X(18))-1*ABS(X(7)-X(16))-2*ABS(X(7)-X(17))-1*ABS(X(7)-X(18))-2*ABS(X(8)-X(16))-5*ABS(X(8)-X(17))-2*ABS(X(8)-X(18))
1640 PR23=-5*ABS(X(9)-X(16))-0*ABS(X(9)-X(17))-0*ABS(X(9)-X(18))-0*ABS(X(10)-X(16))-0*ABS(X(10)-X(17))-5*ABS(X(10)-X(18))-10*ABS(X(11)-X(16))-0*ABS(X(11)-X(17))-2*ABS(X(11)-X(18))-0*ABS(X(12)-X(16))-1*ABS(X(12)-X(17))-1*ABS(X(12)-X(18))
1642 PR24=-1*ABS(X(13)-X(16))-0*ABS(X(13)-X(17))-0*ABS(X(13)-X(18))
1643 PR25=-5*ABS(X(14)-X(16))-1*ABS(X(14)-X(17))-5*ABS(X(14)-X(18))-3*ABS(X(15)-X(16))-0*ABS(X(15)-X(17))-5*ABS(X(15)-X(18))-0*ABS(X(16)-X(17))-0*ABS(X(16)-X(18))-5*ABS(X(17)-X(18))
1650 P=PR1+PR2+PR3+PR4+PR5+PR6+PR7+PR8+PR9+PR10+PR11+PR12+PR21+PR22+PR23+PR24+PR25-SUMTZ
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 18
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-21400 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9),A(10)
1914 PRINT A(11),A(12),A(13),A(14),A(15)
1915 PRINT A(16),A(17),A(18),M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW-BASIC 3.11 interpreter, and the output produced in the first 27 hours of running is presented below. What immediately follows is a manual copy from the computer screen.
158 261 321 249 287
309 199 231 357 300
241 223 339 267 213
255 185 275 -21391 -31667
605 488 442 540 564
454 550 516 406 463
532 508 424 482 498
524 578 474 -21301 -31563
463 352 300 358 422
312 408 382 264 321
366 374 282 340 394
346 436 332 -21365 -31489
421 304 258 356 380
270 366 332 222 279
348 324 240 298 314
340 394 290 -21301 -31343
21301 is optimal, Amaral (2008, p. 1030). Interpreted in accordance with line 1912 through line 1915, the output through JJJJ=-31343 was produced in the first 27 hours of running on a personal computer with an Intel 2.66 GHz. chip and the Microsoft interpreter, which is not a compiler.
References
Amaral, A. R. S., 2006. On the exact solution of a facility layout problem. European Journal of Operational Research 173, 508-518.
Amaral, A. R. S., 2008. An exact approach to the one-dimensional facility layout problem. Operations Research 56, 1026-1033.
Simmons, D. M., 1969. One-dimensioanl space allocation: An ordering algorithm. Operations Research 17, 812-826.
The complete computer program listed below seeks to solve Problem P18 of Amaral (2008), which is an instance of the allocation problem of Simmons (1969). In order to have integer locations, the department lengths used in the following computer program are twice as long as the original lengths.
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466)
6 DIM T(33,33),TZ(33,33)
11 T(1,2)=23:T(1,3)=29:T(1,4)=23:T(1,5)=27:T(1,6)=23:T(1,7)=27:T(1,8)=25:T(1,9)=29:T(1,10)=26:T(1,11)=25:T(1,12)=23:T(1,13)=29:T(1,14)=23:T(1,15)=27
12 T(2,3)=12:T(2,4)=6:T(2,5)=10:T(2,6)=6:T(2,7)=10:T(2,8)=8:T(2,9)=12:T(2,10)=9:T(2,11)=8:T(2,12)=6:T(2,13)=12:T(2,14)=6:T(2,15)=10
13 T(3,4)=12:T(3,5)=16:T(3,6)=12:T(3,7)=16:T(3,8)=14:T(3,9)=18:T(3,10)=15:T(3,11)=14:T(3,12)=12:T(3,13)=18:T(3,14)=12:T(3,15)=16
14 T(4,5)=10:T(4,6)=6:T(4,7)=10:T(4,8)=8:T(4,9)=12:T(4,10)=9:T(4,11)=8:T(4,12)=6:T(4,13)=12:T(4,14)=6:T(4,15)=10
15 T(5,6)=10:T(5,7)=14:T(5,8)=12:T(5,9)=16:T(5,10)=13:T(5,11)=12:T(5,12)=10:T(5,13)=16:T(5,14)=10:T(5,15)=14
16 T(6,7)=10:T(6,8)=8:T(6,9)=12:T(6,10)=9:T(6,11)=8:T(6,12)=6:T(6,13)=12:T(6,14)=6:T(6,15)=10
17 T(7,8)=12:T(7,9)=16:T(7,10)=13:T(7,11)=12:T(7,12)=10:T(7,13)=16:T(7,14)=10:T(7,15)=14
18 T(8,9)=14:T(8,10)=11:T(8,11)=10:T(8,12)=8:T(8,13)=14:T(8,14)=8:T(8,15)=12
19 T(9,10)=15:T(9,11)=14:T(9,12)=12:T(9,13)=18:T(9,14)=12:T(9,15)=16
20 T(10,11)=11:T(10,12)=9:T(10,13)=15:T(10,14)=9:T(10,15)=13
21 T(11,12)=8:T(11,13)=14:T(11,14)=8:T(11,15)=12:T(12,13)=12:T(12,14)=6:T(12,15)=10:T(13,14)=12:T(13,15)=16:T(14,15)=10
31 T(1,16)=23:T(1,17)=27:T(1,18)=25:T(2,16)=6:T(2,17)=10:T(2,18)=8:T(3,16)=12:T(3,17)=16:T(3,18)=14:T(4,16)=6:T(4,17)=10:T(4,18)=8:T(5,16)=10:T(5,17)=14
32 T(5,18)=12:T(6,16)=6:T(6,17)=10:T(6,18)=8:T(7,16)=10:T(7,17)=14:T(7,18)=12:T(8,16)=8:T(8,17)=12:T(8,18)=10:T(9,16)=12:T(9,17)=16:T(9,18)=14:T(10,16)=9
33 T(10,17)=13:T(10,18)=11:T(11,16)=8:T(11,17)=12:T(11,18)=10:T(12,16)=6:T(12,17)=10:T(12,18)=8:T(13,16)=12:T(13,17)=16:T(13,18)=14:T(14,16)=6:T(14,17)=10
34 T(14,18)=8:T(15,16)=10:T(15,17)=14:T(15,18)=12:T(16,17)=10:T(16,18)=8:T(17,18)=12
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 18
88 A(I)=FIX(RND*699)
89 NEXT I
126 REM IMAR=10+FIX(RND*32000)
128 FOR I=1 TO 32000
129 FOR KK=1 TO 18
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*18):IJM=1+FIX(RND*18):IJN=1+FIX(RND*18)
233 IF RND<.7 THEN X(IJL)=FIX(RND*699) ELSE IF RND<.05 THEN X(IJL)=A(IJL)-1 ELSE GOTO 244
235 GOTO 351
244 X(IJM)=A(IJN):X(IJN)=A(IJM)
351 FOR K=1 TO 17
361 FOR J=K+1 TO 18
364 IF T(K,J)>ABS(X(K)-X(J)) THEN TZ(K,J)=99999! ELSE TZ(K,J)=0
366 NEXT J
399 NEXT K
1590 SUMTZ=0
1591 FOR K=1 TO 17
1594 FOR J=K+1 TO 18
1596 SUMTZ=SUMTZ+TZ(K,J)
1597 NEXT J
1598 NEXT K
1623 PR1=-0*ABS(X(1)-X(2))-5*ABS(X(1)-X(3))-0*ABS(X(1)-X(4))-5*ABS(X(1)-X(5))-2*ABS(X(1)-X(6))-10*ABS(X(1)-X(7))-3*ABS(X(1)-X(8))-1*ABS(X(1)-X(9))-5*ABS(X(1)-X(10))-5*ABS(X(1)-X(11))-5*ABS(X(1)-X(12))-0*ABS(X(1)-X(13))-0*ABS(X(1)-X(14))-5*ABS(X(1)-X(15))
1624 PR2=-3*ABS(X(2)-X(3))-10*ABS(X(2)-X(4))-5*ABS(X(2)-X(5))-1*ABS(X(2)-X(6))-5*ABS(X(2)-X(7))-1*ABS(X(2)-X(8))-2*ABS(X(2)-X(9))-4*ABS(X(2)-X(10))-2*ABS(X(2)-X(11))-5*ABS(X(2)-X(12))-0*ABS(X(2)-X(13))-10*ABS(X(2)-X(14))-10*ABS(X(2)-X(15))
1625 PR3=-2*ABS(X(3)-X(4))-0*ABS(X(3)-X(5))-5*ABS(X(3)-X(6))-2*ABS(X(3)-X(7))-4*ABS(X(3)-X(8))-4*ABS(X(3)-X(9))-5*ABS(X(3)-X(10))-0*ABS(X(3)-X(11))-0*ABS(X(3)-X(12))-0*ABS(X(3)-X(13))-5*ABS(X(3)-X(14))-1*ABS(X(3)-X(15))
1626 PR4=-1*ABS(X(4)-X(5))-0*ABS(X(4)-X(6))-5*ABS(X(4)-X(7))-2*ABS(X(4)-X(8))-1*ABS(X(4)-X(9))-0*ABS(X(4)-X(10))-10*ABS(X(4)-X(11))-2*ABS(X(4)-X(12))-2*ABS(X(4)-X(13))-0*ABS(X(4)-X(14))-2*ABS(X(4)-X(15))
1627 PR5=-5*ABS(X(5)-X(6))-6*ABS(X(5)-X(7))-5*ABS(X(5)-X(8))-2*ABS(X(5)-X(9))-5*ABS(X(5)-X(10))-2*ABS(X(5)-X(11))-0*ABS(X(5)-X(12))-5*ABS(X(5)-X(13))-1*ABS(X(5)-X(14))-1*ABS(X(5)-X(15))
1628 PR6=-5*ABS(X(6)-X(7))-2*ABS(X(6)-X(8))-1*ABS(X(6)-X(9))-6*ABS(X(6)-X(10))-0*ABS(X(6)-X(11))-0*ABS(X(6)-X(12))-10*ABS(X(6)-X(13))-0*ABS(X(6)-X(14))-2*ABS(X(6)-X(15))
1629 PR7=-0*ABS(X(7)-X(8))-0*ABS(X(7)-X(9))-0*ABS(X(7)-X(10))-5*ABS(X(7)-X(11))-10*ABS(X(7)-X(12))-2*ABS(X(7)-X(13))-2*ABS(X(7)-X(14))-5*ABS(X(7)-X(15))
1630 PR8=-1*ABS(X(8)-X(9))-1*ABS(X(8)-X(10))-10*ABS(X(8)-X(11))-10*ABS(X(8)-X(12))-2*ABS(X(8)-X(13))-0*ABS(X(8)-X(14))-10*ABS(X(8)-X(15))
1631 PR9=-2*ABS(X(9)-X(10))-0*ABS(X(9)-X(11))-3*ABS(X(9)-X(12))-5*ABS(X(9)-X(13))-5*ABS(X(9)-X(14))-0*ABS(X(9)-X(15))
1632 PR10=-5*ABS(X(10)-X(11))-5*ABS(X(10)-X(12))-0*ABS(X(10)-X(13))-5*ABS(X(10)-X(14))-1*ABS(X(10)-X(15))
1633 PR11=-5*ABS(X(11)-X(12))-2*ABS(X(11)-X(13))-5*ABS(X(11)-X(14))-1*ABS(X(11)-X(15))
1636 PR12=-2*ABS(X(12)-X(13))-10*ABS(X(12)-X(14))-5*ABS(X(12)-X(15))-2*ABS(X(13)-X(14))-2*ABS(X(13)-X(15))-5*ABS(X(14)-X(15))
1638 PR21=-4*ABS(X(1)-X(16))-4*ABS(X(1)-X(17))-0*ABS(X(1)-X(18))-3*ABS(X(2)-X(16))-0*ABS(X(2)-X(17))-5*ABS(X(2)-X(18))-0*ABS(X(3)-X(16))-0*ABS(X(3)-X(17))-5*ABS(X(3)-X(18))-1*ABS(X(4)-X(16))-5*ABS(X(4)-X(17))-2*ABS(X(4)-X(18))
1639 PR22=-1*ABS(X(5)-X(16))-5*ABS(X(5)-X(17))-2*ABS(X(5)-X(18))-0*ABS(X(6)-X(16))-1*ABS(X(6)-X(17))-0*ABS(X(6)-X(18))-1*ABS(X(7)-X(16))-2*ABS(X(7)-X(17))-1*ABS(X(7)-X(18))-2*ABS(X(8)-X(16))-5*ABS(X(8)-X(17))-2*ABS(X(8)-X(18))
1640 PR23=-5*ABS(X(9)-X(16))-0*ABS(X(9)-X(17))-0*ABS(X(9)-X(18))-0*ABS(X(10)-X(16))-0*ABS(X(10)-X(17))-5*ABS(X(10)-X(18))-10*ABS(X(11)-X(16))-0*ABS(X(11)-X(17))-2*ABS(X(11)-X(18))-0*ABS(X(12)-X(16))-1*ABS(X(12)-X(17))-1*ABS(X(12)-X(18))
1642 PR24=-1*ABS(X(13)-X(16))-0*ABS(X(13)-X(17))-0*ABS(X(13)-X(18))
1643 PR25=-5*ABS(X(14)-X(16))-1*ABS(X(14)-X(17))-5*ABS(X(14)-X(18))-3*ABS(X(15)-X(16))-0*ABS(X(15)-X(17))-5*ABS(X(15)-X(18))-0*ABS(X(16)-X(17))-0*ABS(X(16)-X(18))-5*ABS(X(17)-X(18))
1650 P=PR1+PR2+PR3+PR4+PR5+PR6+PR7+PR8+PR9+PR10+PR11+PR12+PR21+PR22+PR23+PR24+PR25-SUMTZ
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 18
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-21400 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9),A(10)
1914 PRINT A(11),A(12),A(13),A(14),A(15)
1915 PRINT A(16),A(17),A(18),M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW-BASIC 3.11 interpreter, and the output produced in the first 27 hours of running is presented below. What immediately follows is a manual copy from the computer screen.
158 261 321 249 287
309 199 231 357 300
241 223 339 267 213
255 185 275 -21391 -31667
605 488 442 540 564
454 550 516 406 463
532 508 424 482 498
524 578 474 -21301 -31563
463 352 300 358 422
312 408 382 264 321
366 374 282 340 394
346 436 332 -21365 -31489
421 304 258 356 380
270 366 332 222 279
348 324 240 298 314
340 394 290 -21301 -31343
21301 is optimal, Amaral (2008, p. 1030). Interpreted in accordance with line 1912 through line 1915, the output through JJJJ=-31343 was produced in the first 27 hours of running on a personal computer with an Intel 2.66 GHz. chip and the Microsoft interpreter, which is not a compiler.
References
Amaral, A. R. S., 2006. On the exact solution of a facility layout problem. European Journal of Operational Research 173, 508-518.
Amaral, A. R. S., 2008. An exact approach to the one-dimensional facility layout problem. Operations Research 56, 1026-1033.
Simmons, D. M., 1969. One-dimensioanl space allocation: An ordering algorithm. Operations Research 17, 812-826.
Subscribe to:
Posts (Atom)