Jsun Yui Wong
The computer program listed below seeks to solve Problem LW5 of Amaral (2006); it is a single-row five-facility layout problem. In order to have integer locations, the facility lengths used in the following computer program have been made twice as long as the given facility lengths.
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(166),A(166),L(166),K(166),P(166),B(166),S(166)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 5
113 A(K)=FIX(RND*699)
115 NEXT K
126 IMAR=10+FIX(RND*500)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 5
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*5):IJM=1+FIX(RND*5):IJN=1+FIX(RND*5)
234 IF RND<.7 THEN X(IJL)=FIX(RND*699) ELSE IF RND<.05 THEN X(IJL)=A(IJL)-1 ELSE GOTO 244
235 GOTO 501
244 X(IJM)=A(IJN):X(IJN)=A(IJM)
501 B(1)=ABS(X(1)-X(2))
502 B(2)=ABS(X(1)-X(3))
503 B(3)=ABS(X(1)-X(4))
504 B(4)=ABS(X(1)-X(5))
505 B(5)=ABS(X(2)-X(3))
506 B(6)=ABS(X(2)-X(4))
507 B(7)=ABS(X(2)-X(5))
508 B(8)=ABS(X(3)-X(4))
509 B(9)=ABS(X(3)-X(5))
510 B(10)=ABS(X(4)-X(5))
701 S(1)=B(1)-4
702 S(2)=B(2)-5
703 S(3)=B(3)-7
704 S(4)=B(4)-8
705 S(5)=B(5)-7
706 S(6)=B(6)-9
707 S(7)=B(7)-10
708 S(8)=B(8)-10
709 S(9)=B(9)-11
710 S(10)=B(10)-13
1107 FOR IJUL=1 TO 10
1112 IF S(IJUL)<0 THEN B(IJUL)=333333!
1115 NEXT IJUL
1380 PH=-2*B(1)-1*B(2)-.001*B(3)-1*B(4)
1381 PI=-.001*B(5)-2*B(6)-2*B(7)
1384 PJ=-6*B(8)-3*B(9)-4*B(10)
1589 P=PH+PI+PJ
1599 PR=PH+PI+PJ
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 5
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-305 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1917 PRINT M,JJJJ
1999 NEXT JJJJ
One notes that the artificial .001 flows of line 1380 and line 1381 replace the original 0 flows.
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced during the first minute of running is presented below. (What immediately follows is a manual copy from the computer screen.)
492 496 461 471 484
-302.056 -31784
438 442 407 417 430
-302.056 -31737
516 520 497 487 508
-302.052 -31711
215 211 246 236 223
-302.056 -31707
228 224 259 249 236
-302.056 -31634
413 417 382 392 405
-302.056 -31439
616 620 597 587 608
-302.052 -31115
Interpreted in accordance with line 1912 and line 1917, the output through JJJJ=-31115 was produced during the first minute of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Amaral, A. R. S. (2006), "On the exact solution of a facility layout problem," European Journal of Operational Research 173, 508-518.
Heragu, S. S., and Kusiak, A. (1991), "Efficient models for the facility layout problem," European Journal of Operational Research 53, 1-13.
Simmons, D. M. (1969), "One-dimensional space allocation: An ordering algorithm," Operations Research 17, 812-826.
Saturday, August 15, 2009
Friday, August 14, 2009
An Application of an Integer Programming Computer Program
Jsun Yui Wong
The computer program listed below seeks to solve the single-row seven-facility layout problem in Kumar, Hadjinicola, and Lin (1995).
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(166),A(166),L(166),K(166),P(166),B(166),S(166)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 7
113 A(K)=FIX(RND*6)
115 NEXT K
126 IMAR=10+FIX(RND*500)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 7
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*7)
234 X(IJL)=FIX(RND*7)
501 B(1)=ABS(X(1)-X(2))
502 B(2)=ABS(X(1)-X(3))
503 B(3)=ABS(X(1)-X(4))
504 B(4)=ABS(X(1)-X(5))
505 B(5)=ABS(X(1)-X(6))
506 B(6)=ABS(X(1)-X(7))
507 B(7)=ABS(X(2)-X(3))
508 B(8)=ABS(X(2)-X(4))
509 B(9)=ABS(X(2)-X(5))
510 B(10)=ABS(X(2)-X(6))
511 B(11)=ABS(X(2)-X(7))
512 B(12)=ABS(X(3)-X(4))
513 B(13)=ABS(X(3)-X(5))
514 B(14)=ABS(X(3)-X(6))
515 B(15)=ABS(X(3)-X(7))
516 B(16)=ABS(X(4)-X(5))
517 B(17)=ABS(X(4)-X(6))
518 B(18)=ABS(X(4)-X(7))
519 B(19)=ABS(X(5)-X(6))
520 B(20)=ABS(X(5)-X(7))
521 B(21)=ABS(X(6)-X(7))
1107 FOR IJUL=1 TO 21
1111 IF B(IJUL)=0 THEN B(IJUL)=333333!
1115 NEXT IJUL
1380 PH=-69*B(1)-78*B(2)-5*B(3)-51*B(4)-76*B(5)-59*B(6)-42*B(7)
1381 PI=-58*B(8)-31*B(9)-88*B(10)-97*B(11)-6*B(12)-30*B(13)-22*B(14)
1382 PJ=-29*B(15)-99*B(16)-98*B(17)-26*B(18)-99*B(19)-2*B(20)-85*B(21)
1588 P=PH+PI+PJ
1599 PR=PK
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 7
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-2300 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 9 minutes of running is presented below. (What immediately follows is a manual copy from the computer screen.)
1 3 0 6 5
4 2 -2285 -27726
1 3 0 6 5
4 2 -2285 -27250
1 3 0 6 5
4 2 -2285 -26608
1 3 0 6 5
4 2 -2285 -22917
1 3 0 6 5
4 2 -2285 -20880
1 3 0 6 5
4 2 -2285 -17442
1 3 0 6 5
4 2 -2285 -16211
1 3 0 6 5
4 2 -2285 -14739
1 3 0 6 5
4 2 -2285 -14482
5 3 6 0 1
2 4 -2285 -13063
2285 is optimal, Kumar et al. (1995, p. 69). Interpreted in accordance with line 1912 and line 1913, the output through JJJJ=-13063 was produced in the first 9 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Heragu, S. S., and Kusiak, A. (1991), "Efficient models for the facility layout problem," European Journal of Operational Research 53, 1-13.
Kumar, K. R., Hadjinicola, G. C., and Lin, T. L. (1995), "A Heuristic procedure for the single-row facility layout problem," European Journal of Operational Research 87, 65-73.
The computer program listed below seeks to solve the single-row seven-facility layout problem in Kumar, Hadjinicola, and Lin (1995).
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(166),A(166),L(166),K(166),P(166),B(166),S(166)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 7
113 A(K)=FIX(RND*6)
115 NEXT K
126 IMAR=10+FIX(RND*500)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 7
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*7)
234 X(IJL)=FIX(RND*7)
501 B(1)=ABS(X(1)-X(2))
502 B(2)=ABS(X(1)-X(3))
503 B(3)=ABS(X(1)-X(4))
504 B(4)=ABS(X(1)-X(5))
505 B(5)=ABS(X(1)-X(6))
506 B(6)=ABS(X(1)-X(7))
507 B(7)=ABS(X(2)-X(3))
508 B(8)=ABS(X(2)-X(4))
509 B(9)=ABS(X(2)-X(5))
510 B(10)=ABS(X(2)-X(6))
511 B(11)=ABS(X(2)-X(7))
512 B(12)=ABS(X(3)-X(4))
513 B(13)=ABS(X(3)-X(5))
514 B(14)=ABS(X(3)-X(6))
515 B(15)=ABS(X(3)-X(7))
516 B(16)=ABS(X(4)-X(5))
517 B(17)=ABS(X(4)-X(6))
518 B(18)=ABS(X(4)-X(7))
519 B(19)=ABS(X(5)-X(6))
520 B(20)=ABS(X(5)-X(7))
521 B(21)=ABS(X(6)-X(7))
1107 FOR IJUL=1 TO 21
1111 IF B(IJUL)=0 THEN B(IJUL)=333333!
1115 NEXT IJUL
1380 PH=-69*B(1)-78*B(2)-5*B(3)-51*B(4)-76*B(5)-59*B(6)-42*B(7)
1381 PI=-58*B(8)-31*B(9)-88*B(10)-97*B(11)-6*B(12)-30*B(13)-22*B(14)
1382 PJ=-29*B(15)-99*B(16)-98*B(17)-26*B(18)-99*B(19)-2*B(20)-85*B(21)
1588 P=PH+PI+PJ
1599 PR=PK
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 7
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-2300 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 9 minutes of running is presented below. (What immediately follows is a manual copy from the computer screen.)
1 3 0 6 5
4 2 -2285 -27726
1 3 0 6 5
4 2 -2285 -27250
1 3 0 6 5
4 2 -2285 -26608
1 3 0 6 5
4 2 -2285 -22917
1 3 0 6 5
4 2 -2285 -20880
1 3 0 6 5
4 2 -2285 -17442
1 3 0 6 5
4 2 -2285 -16211
1 3 0 6 5
4 2 -2285 -14739
1 3 0 6 5
4 2 -2285 -14482
5 3 6 0 1
2 4 -2285 -13063
2285 is optimal, Kumar et al. (1995, p. 69). Interpreted in accordance with line 1912 and line 1913, the output through JJJJ=-13063 was produced in the first 9 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Heragu, S. S., and Kusiak, A. (1991), "Efficient models for the facility layout problem," European Journal of Operational Research 53, 1-13.
Kumar, K. R., Hadjinicola, G. C., and Lin, T. L. (1995), "A Heuristic procedure for the single-row facility layout problem," European Journal of Operational Research 87, 65-73.
An Integer Programming Computer Program Applied to a Small Quadratic Assignment Problem
Jsun Yui Wong
The computer program listed below seeks to solve the five-department problem in Nugent, Vollmann, and Ruml (1968).
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(166),A(166),L(166),K(166),P(166),B(166),S(166)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 5
113 A(K)=FIX(RND*3)
115 NEXT K
117 FOR KKK=6 TO 10
118 A(KKK)=FIX(RND*2)
119 NEXT KKK
126 IMAR=10+FIX(RND*500)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 10
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*5)
234 X(IJL)=FIX(RND*3)
242 IJM=6+FIX(RND*10)
244 X(IJM)=FIX(RND*2)
501 B(1)=ABS(X(1)-X(2))+ABS(X(6)-X(7))
502 B(2)=ABS(X(1)-X(3))+ABS(X(6)-X(8))
503 B(3)=ABS(X(1)-X(4))+ABS(X(6)-X(9))
504 B(4)=ABS(X(1)-X(5))+ABS(X(6)-X(10))
505 B(5)=ABS(X(2)-X(3))+ABS(X(7)-X(8))
506 B(6)=ABS(X(2)-X(4))+ABS(X(7)-X(9))
507 B(7)=ABS(X(2)-X(5))+ABS(X(7)-X(10))
508 B(8)=ABS(X(3)-X(4))+ABS(X(8)-X(9))
509 B(9)=ABS(X(3)-X(5))+ABS(X(8)-X(10))
510 B(10)=ABS(X(4)-X(5))+ABS(X(9)-X(10))
1107 FOR IJUL=1 TO 10
1111 IF B(IJUL)=0 THEN B(IJUL)=333333!
1115 NEXT IJUL
1380 PH=-5*B(1)-2*B(2)-4*B(3)-1*B(4)
1381 PI=-3*B(5)-.001*B(6)-2*B(7)
1384 PJ=-.001*B(8)-.001*B(9)-5*B(10)
1588 P=PH+PI+PJ
1599 PR=PK
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 10
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-27 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)
1917 PRINT M,JJJJ
1999 NEXT JJJJ
One notes that the artificial .001 flows of line 1381 and line 1384 replace the original 0 flows.
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced during the first second of running is presented below. (What immediately follows is a manual copy from the computer screen.)
1 1 2 0 0
1 0 0 1 0
-25.007 -32000
1 0 2 1 0
1 1 1 0 0
-26.007 -31998
0 1 2 0 1
0 0 0 1 1
-25.007 -31996
1 2 0 1 2
0 0 0 1 1
-26.007 -31994
1 1 2 0 0
1 0 0 1 0
-25.007 -31992
Interpreted in accordance with line 1912 through line 1917, the output through JJJJ=-31992 was produced during the first second of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Heragu, S. S., and Kusiak, A. (1991), "Efficient models for the facility layout problem," European Journal of Operational Research 53, 1-13.
Nugent, C. E., Vollmann, T. E., and Ruml, J. (1968), "An experimental comparisons of techniques for the assignment of facilities to locations," Operations Research 16, 150-173.
The computer program listed below seeks to solve the five-department problem in Nugent, Vollmann, and Ruml (1968).
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(166),A(166),L(166),K(166),P(166),B(166),S(166)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 5
113 A(K)=FIX(RND*3)
115 NEXT K
117 FOR KKK=6 TO 10
118 A(KKK)=FIX(RND*2)
119 NEXT KKK
126 IMAR=10+FIX(RND*500)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 10
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*5)
234 X(IJL)=FIX(RND*3)
242 IJM=6+FIX(RND*10)
244 X(IJM)=FIX(RND*2)
501 B(1)=ABS(X(1)-X(2))+ABS(X(6)-X(7))
502 B(2)=ABS(X(1)-X(3))+ABS(X(6)-X(8))
503 B(3)=ABS(X(1)-X(4))+ABS(X(6)-X(9))
504 B(4)=ABS(X(1)-X(5))+ABS(X(6)-X(10))
505 B(5)=ABS(X(2)-X(3))+ABS(X(7)-X(8))
506 B(6)=ABS(X(2)-X(4))+ABS(X(7)-X(9))
507 B(7)=ABS(X(2)-X(5))+ABS(X(7)-X(10))
508 B(8)=ABS(X(3)-X(4))+ABS(X(8)-X(9))
509 B(9)=ABS(X(3)-X(5))+ABS(X(8)-X(10))
510 B(10)=ABS(X(4)-X(5))+ABS(X(9)-X(10))
1107 FOR IJUL=1 TO 10
1111 IF B(IJUL)=0 THEN B(IJUL)=333333!
1115 NEXT IJUL
1380 PH=-5*B(1)-2*B(2)-4*B(3)-1*B(4)
1381 PI=-3*B(5)-.001*B(6)-2*B(7)
1384 PJ=-.001*B(8)-.001*B(9)-5*B(10)
1588 P=PH+PI+PJ
1599 PR=PK
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 10
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-27 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)
1917 PRINT M,JJJJ
1999 NEXT JJJJ
One notes that the artificial .001 flows of line 1381 and line 1384 replace the original 0 flows.
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced during the first second of running is presented below. (What immediately follows is a manual copy from the computer screen.)
1 1 2 0 0
1 0 0 1 0
-25.007 -32000
1 0 2 1 0
1 1 1 0 0
-26.007 -31998
0 1 2 0 1
0 0 0 1 1
-25.007 -31996
1 2 0 1 2
0 0 0 1 1
-26.007 -31994
1 1 2 0 0
1 0 0 1 0
-25.007 -31992
Interpreted in accordance with line 1912 through line 1917, the output through JJJJ=-31992 was produced during the first second of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Heragu, S. S., and Kusiak, A. (1991), "Efficient models for the facility layout problem," European Journal of Operational Research 53, 1-13.
Nugent, C. E., Vollmann, T. E., and Ruml, J. (1968), "An experimental comparisons of techniques for the assignment of facilities to locations," Operations Research 16, 150-173.
An Illustration of an Integer Programming Computer Program, Second Edition
Jsun Yui Wong
The computer program listed below seeks to solve Problem LW5 of Amaral (2006). In order to have integer locations, the department lengths used in the following computer program have been made twice as long as the given department lengths.
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(166),A(166),L(166),K(166),P(166),B(166),S(166)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 5
113 A(K)=FIX(RND*699)
115 NEXT K
126 IMAR=10+FIX(RND*500)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 5
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*5):IJM=1+FIX(RND*5):IJN=1+FIX(RND*5)
234 IF RND<.7 THEN X(IJL)=FIX(RND*699) ELSE IF RND<.05 THEN X(IJL)=A(IJL)-1 ELSE GOTO 244
235 GOTO 501
244 X(IJM)=A(IJN):X(IJN)=A(IJM)
501 B(1)=ABS(X(1)-X(2))
502 B(2)=ABS(X(1)-X(3))
503 B(3)=ABS(X(1)-X(4))
504 B(4)=ABS(X(1)-X(5))
505 B(5)=ABS(X(2)-X(3))
506 B(6)=ABS(X(2)-X(4))
507 B(7)=ABS(X(2)-X(5))
508 B(8)=ABS(X(3)-X(4))
509 B(9)=ABS(X(3)-X(5))
510 B(10)=ABS(X(4)-X(5))
701 S(1)=B(1)-4
702 S(2)=B(2)-5
703 S(3)=B(3)-7
704 S(4)=B(4)-8
705 S(5)=B(5)-7
706 S(6)=B(6)-9
707 S(7)=B(7)-10
708 S(8)=B(8)-10
709 S(9)=B(9)-11
710 S(10)=B(10)-13
1107 FOR IJUL=1 TO 10
1112 IF S(IJUL)<0 THEN S(IJUL)=-333333! ELSE S(IJUL)=0
1115 NEXT IJUL
1117 SSUM=0
1121 FOR IAU=1 TO 10
1123 SSUM=SSUM+S(IAU)
1125 NEXT IAU
1380 PH=-2*B(1)-1*B(2)-0*B(3)-1*B(4)
1381 PI=-0*B(5)-2*B(6)-2*B(7)
1384 PJ=-6*B(8)-3*B(9)-4*B(10)
1589 P=PH+PI+PJ+SSUM
1599 PR=PH+PI+PJ
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 5
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-305 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1917 PRINT M,MM,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 2 minutes of running is presented below. (What immediately follows is a manual copy from the computer screen.)
489 485 520 510 497
-302 -302 -31881
470 474 439 449 462
-302 -302 -31368
482 486 451 461 474
-302 -302 -31193
306 310 275 285 298
-302 -302 -31119
632 636 601 611 624
-302 -302 -31106
375 379 344 354 367
-302 -302 -30804
Interpreted in accordance with line 1912 and line 1917, the output through JJJJ=-30804 was produced in the first 2 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Amaral, A. R. S. (2006), "On the exact solution of a facility layout problem," European Journal of Operational Research 173, 508-518.
Heragu, S. S., and Kusiak, A. (1991), "Efficient models for the facility layout problem," European Journal of Operational Research 53, 1-13.
Simmons, D. M. (1969), "One-dimensional space allocation: An ordering algorithm," Operations Research 17, 812-826.
The computer program listed below seeks to solve Problem LW5 of Amaral (2006). In order to have integer locations, the department lengths used in the following computer program have been made twice as long as the given department lengths.
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(166),A(166),L(166),K(166),P(166),B(166),S(166)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 5
113 A(K)=FIX(RND*699)
115 NEXT K
126 IMAR=10+FIX(RND*500)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 5
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*5):IJM=1+FIX(RND*5):IJN=1+FIX(RND*5)
234 IF RND<.7 THEN X(IJL)=FIX(RND*699) ELSE IF RND<.05 THEN X(IJL)=A(IJL)-1 ELSE GOTO 244
235 GOTO 501
244 X(IJM)=A(IJN):X(IJN)=A(IJM)
501 B(1)=ABS(X(1)-X(2))
502 B(2)=ABS(X(1)-X(3))
503 B(3)=ABS(X(1)-X(4))
504 B(4)=ABS(X(1)-X(5))
505 B(5)=ABS(X(2)-X(3))
506 B(6)=ABS(X(2)-X(4))
507 B(7)=ABS(X(2)-X(5))
508 B(8)=ABS(X(3)-X(4))
509 B(9)=ABS(X(3)-X(5))
510 B(10)=ABS(X(4)-X(5))
701 S(1)=B(1)-4
702 S(2)=B(2)-5
703 S(3)=B(3)-7
704 S(4)=B(4)-8
705 S(5)=B(5)-7
706 S(6)=B(6)-9
707 S(7)=B(7)-10
708 S(8)=B(8)-10
709 S(9)=B(9)-11
710 S(10)=B(10)-13
1107 FOR IJUL=1 TO 10
1112 IF S(IJUL)<0 THEN S(IJUL)=-333333! ELSE S(IJUL)=0
1115 NEXT IJUL
1117 SSUM=0
1121 FOR IAU=1 TO 10
1123 SSUM=SSUM+S(IAU)
1125 NEXT IAU
1380 PH=-2*B(1)-1*B(2)-0*B(3)-1*B(4)
1381 PI=-0*B(5)-2*B(6)-2*B(7)
1384 PJ=-6*B(8)-3*B(9)-4*B(10)
1589 P=PH+PI+PJ+SSUM
1599 PR=PH+PI+PJ
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 5
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-305 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1917 PRINT M,MM,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 2 minutes of running is presented below. (What immediately follows is a manual copy from the computer screen.)
489 485 520 510 497
-302 -302 -31881
470 474 439 449 462
-302 -302 -31368
482 486 451 461 474
-302 -302 -31193
306 310 275 285 298
-302 -302 -31119
632 636 601 611 624
-302 -302 -31106
375 379 344 354 367
-302 -302 -30804
Interpreted in accordance with line 1912 and line 1917, the output through JJJJ=-30804 was produced in the first 2 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Amaral, A. R. S. (2006), "On the exact solution of a facility layout problem," European Journal of Operational Research 173, 508-518.
Heragu, S. S., and Kusiak, A. (1991), "Efficient models for the facility layout problem," European Journal of Operational Research 53, 1-13.
Simmons, D. M. (1969), "One-dimensional space allocation: An ordering algorithm," Operations Research 17, 812-826.
An Illustration of an Integer Programming Computer Program
Jsun Yui Wong
The computer program listed below seeks to solve Problem LW5 of Amaral (2006). In order to have integer locations, the department lengths used in the following computer program have been made twice as long as the given department lengths.
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(166),A(166),L(166),K(166),P(166),B(166),S(166)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 5
113 A(K)=FIX(RND*699)
115 NEXT K
126 IMAR=10+FIX(RND*500)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 5
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*5):IJM=1+FIX(RND*5):IJN=1+FIX(RND*5)
234 IF RND<.7 THEN X(IJL)=FIX(RND*699) ELSE IF RND<.05 THEN X(IJL)=A(IJL)-1 ELSE GOTO 244
235 GOTO 501
244 X(IJM)=A(IJN):X(IJN)=A(IJM)
501 B(1)=ABS(X(1)-X(2))
502 B(2)=ABS(X(1)-X(3))
503 B(3)=ABS(X(1)-X(4))
504 B(4)=ABS(X(1)-X(5))
505 B(5)=ABS(X(2)-X(3))
506 B(6)=ABS(X(2)-X(4))
507 B(7)=ABS(X(2)-X(5))
508 B(8)=ABS(X(3)-X(4))
509 B(9)=ABS(X(3)-X(5))
510 B(10)=ABS(X(4)-X(5))
701 S(1)=B(1)-4
702 S(2)=B(2)-5
703 S(3)=B(3)-7
704 S(4)=B(4)-8
705 S(5)=B(5)-7
706 S(6)=B(6)-9
707 S(7)=B(7)-10
708 S(8)=B(8)-10
709 S(9)=B(9)-11
710 S(10)=B(10)-13
1107 FOR IJUL=1 TO 10
1112 IF S(IJUL)<0 THEN S(IJUL)=-333333! ELSE S(IJUL)=0
1115 NEXT IJUL
1117 SSUM=0
1121 FOR IAU=1 TO 10
1123 SSUM=SSUM+S(IAU)
1125 NEXT IAU
1380 PH=-2*B(1)-1*B(2)-0*B(3)-1*B(4)
1381 PI=-0*B(5)-2*B(6)-2*B(7)
1384 PJ=-6*B(8)-3*B(9)-4*B(10)
1589 P=PH+PI+PJ+SSUM
1599 PR=PH+PI+PJ
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 5
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-305 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1917 PRINT M,MM,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 2 seconds of running is presented below. (What immediately follows is a manual copy from the computer screen.)
489 485 520 510 497
-302 -302 -31881
470 474 439 449 462
-302 -302 -31368
482 486 451 461 474
-302 -302 -31193
306 310 275 285 298
-302 -302 -31119
632 636 601 611 624
-302 -302 -31106
375 379 344 354 367
-302 -302 -30804
Interpreted in accordance with line 1912 and line 1917, the output through JJJJ=-30804 was produced in the first 2 seconds of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Amaral, A. R. S. (2006), "On the exact solution of a facility layout problem," European Journal of Operational Research 173, 508-518.
Heragu, S. S., and Kusiak, A. (1991), "Efficient models for the facility layout problem," European Journal of Operational Research 53, 1-13.
Simmons, D. M. (1969), "One-dimensional space allocation: An ordering algorithm," Operations Research 17, 812-826.
The computer program listed below seeks to solve Problem LW5 of Amaral (2006). In order to have integer locations, the department lengths used in the following computer program have been made twice as long as the given department lengths.
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(166),A(166),L(166),K(166),P(166),B(166),S(166)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 5
113 A(K)=FIX(RND*699)
115 NEXT K
126 IMAR=10+FIX(RND*500)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 5
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*5):IJM=1+FIX(RND*5):IJN=1+FIX(RND*5)
234 IF RND<.7 THEN X(IJL)=FIX(RND*699) ELSE IF RND<.05 THEN X(IJL)=A(IJL)-1 ELSE GOTO 244
235 GOTO 501
244 X(IJM)=A(IJN):X(IJN)=A(IJM)
501 B(1)=ABS(X(1)-X(2))
502 B(2)=ABS(X(1)-X(3))
503 B(3)=ABS(X(1)-X(4))
504 B(4)=ABS(X(1)-X(5))
505 B(5)=ABS(X(2)-X(3))
506 B(6)=ABS(X(2)-X(4))
507 B(7)=ABS(X(2)-X(5))
508 B(8)=ABS(X(3)-X(4))
509 B(9)=ABS(X(3)-X(5))
510 B(10)=ABS(X(4)-X(5))
701 S(1)=B(1)-4
702 S(2)=B(2)-5
703 S(3)=B(3)-7
704 S(4)=B(4)-8
705 S(5)=B(5)-7
706 S(6)=B(6)-9
707 S(7)=B(7)-10
708 S(8)=B(8)-10
709 S(9)=B(9)-11
710 S(10)=B(10)-13
1107 FOR IJUL=1 TO 10
1112 IF S(IJUL)<0 THEN S(IJUL)=-333333! ELSE S(IJUL)=0
1115 NEXT IJUL
1117 SSUM=0
1121 FOR IAU=1 TO 10
1123 SSUM=SSUM+S(IAU)
1125 NEXT IAU
1380 PH=-2*B(1)-1*B(2)-0*B(3)-1*B(4)
1381 PI=-0*B(5)-2*B(6)-2*B(7)
1384 PJ=-6*B(8)-3*B(9)-4*B(10)
1589 P=PH+PI+PJ+SSUM
1599 PR=PH+PI+PJ
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 5
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-305 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1917 PRINT M,MM,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 2 seconds of running is presented below. (What immediately follows is a manual copy from the computer screen.)
489 485 520 510 497
-302 -302 -31881
470 474 439 449 462
-302 -302 -31368
482 486 451 461 474
-302 -302 -31193
306 310 275 285 298
-302 -302 -31119
632 636 601 611 624
-302 -302 -31106
375 379 344 354 367
-302 -302 -30804
Interpreted in accordance with line 1912 and line 1917, the output through JJJJ=-30804 was produced in the first 2 seconds of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Amaral, A. R. S. (2006), "On the exact solution of a facility layout problem," European Journal of Operational Research 173, 508-518.
Heragu, S. S., and Kusiak, A. (1991), "Efficient models for the facility layout problem," European Journal of Operational Research 53, 1-13.
Simmons, D. M. (1969), "One-dimensional space allocation: An ordering algorithm," Operations Research 17, 812-826.
Thursday, August 13, 2009
An Integer Programming Computer Program Applied to a Quadratic Assignment Problem
Jsun Yui Wong
The computer program listed below seeks to solve the six-department problem in Nugent, Vollmann, and Ruml (1968).
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(166),A(166),L(166),K(166),P(166),B(166),S(166)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 12
113 A(K)=FIX(RND*3)
115 NEXT K
126 IMAR=10+FIX(RND*500)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 12
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*12)
234 X(IJL)=FIX(RND*3)
501 B(1)=ABS(X(1)-X(2))+ABS(X(7)-X(8))
502 B(2)=ABS(X(1)-X(3))+ABS(X(7)-X(9))
503 B(3)=ABS(X(1)-X(4))+ABS(X(7)-X(10))
504 B(4)=ABS(X(1)-X(5))+ABS(X(7)-X(11))
505 B(5)=ABS(X(1)-X(6))+ABS(X(7)-X(12))
506 B(6)=ABS(X(2)-X(3))+ABS(X(8)-X(9))
507 B(7)=ABS(X(2)-X(4))+ABS(X(8)-X(10))
508 B(8)=ABS(X(2)-X(5))+ABS(X(8)-X(11))
509 B(9)=ABS(X(2)-X(6))+ABS(X(8)-X(12))
510 B(10)=ABS(X(3)-X(4))+ABS(X(9)-X(10))
511 B(11)=ABS(X(3)-X(5))+ABS(X(9)-X(11))
512 B(12)=ABS(X(3)-X(6))+ABS(X(9)-X(12))
513 B(13)=ABS(X(4)-X(5))+ABS(X(10)-X(11))
514 B(14)=ABS(X(4)-X(6))+ABS(X(10)-X(12))
515 B(15)=ABS(X(5)-X(6))+ABS(X(11)-X(12))
1107 FOR IJUL=1 TO 15
1111 IF B(IJUL)=0 THEN B(IJUL)=333333!
1115 NEXT IJUL
1380 PH=-5*B(1)-2*B(2)-4*B(3)-1*B(4)
1381 PI=-.01*B(5)-3*B(6)-.01*B(7)
1384 PJ=-2*B(8)-2*B(9)-.01*B(10)
1385 PK=-.01*B(11)-.01*B(12)-5*B(13)-2*B(14)
1386 PL=-10*B(15)
1588 P=PH+PI+PJ+PK+PL
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 12
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-45 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),M,JJJJ
1999 NEXT JJJJ
One notes that the artificial .01 flows of lines 1381, 1384 and 1385 replace the original 0 flows.
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 10 seconds of running is presented below. (What immediately follows is a manual copy from the computer screen.)
0 1 2 0 1
1 0 0 0 1
1 2 -43.13 -31989
0 0 0 1 1
2 2 1 0 2
1 1 -43.13 -31910
0 0 0 1 1
2 0 1 2 0
1 1 -43.13 -31906
2 1 1 2 1
0 1 1 2 0
0 0 -43.13 -31884
1 1 2 0 0
0 2 1 1 2
1 0 -43.13 -31825
1 1 1 2 2
2 0 1 2 0
1 2 -43.11 -31793
2 1 0 2 1
1 2 2 2 1
1 0 -43.13 -31779
The candidate solution above at JJJJ=-31793 is usable. Interpreted in accordance with line 1912 through line 1914, the output through JJJJ=-31779 was produced in the first 10 seconds of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Heragu, S. S., and Kusiak, A. (1991), "Efficient models for the facility layout problem," European Journal of Operational Research 53, 1-13.
Nugent, C. E., Vollmann, T. E., and Ruml, J. (1968), "An experimental comparisons of techniques for the assignment of facilities to locations," Operations Research 16, 150-173.
The computer program listed below seeks to solve the six-department problem in Nugent, Vollmann, and Ruml (1968).
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(166),A(166),L(166),K(166),P(166),B(166),S(166)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 12
113 A(K)=FIX(RND*3)
115 NEXT K
126 IMAR=10+FIX(RND*500)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 12
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*12)
234 X(IJL)=FIX(RND*3)
501 B(1)=ABS(X(1)-X(2))+ABS(X(7)-X(8))
502 B(2)=ABS(X(1)-X(3))+ABS(X(7)-X(9))
503 B(3)=ABS(X(1)-X(4))+ABS(X(7)-X(10))
504 B(4)=ABS(X(1)-X(5))+ABS(X(7)-X(11))
505 B(5)=ABS(X(1)-X(6))+ABS(X(7)-X(12))
506 B(6)=ABS(X(2)-X(3))+ABS(X(8)-X(9))
507 B(7)=ABS(X(2)-X(4))+ABS(X(8)-X(10))
508 B(8)=ABS(X(2)-X(5))+ABS(X(8)-X(11))
509 B(9)=ABS(X(2)-X(6))+ABS(X(8)-X(12))
510 B(10)=ABS(X(3)-X(4))+ABS(X(9)-X(10))
511 B(11)=ABS(X(3)-X(5))+ABS(X(9)-X(11))
512 B(12)=ABS(X(3)-X(6))+ABS(X(9)-X(12))
513 B(13)=ABS(X(4)-X(5))+ABS(X(10)-X(11))
514 B(14)=ABS(X(4)-X(6))+ABS(X(10)-X(12))
515 B(15)=ABS(X(5)-X(6))+ABS(X(11)-X(12))
1107 FOR IJUL=1 TO 15
1111 IF B(IJUL)=0 THEN B(IJUL)=333333!
1115 NEXT IJUL
1380 PH=-5*B(1)-2*B(2)-4*B(3)-1*B(4)
1381 PI=-.01*B(5)-3*B(6)-.01*B(7)
1384 PJ=-2*B(8)-2*B(9)-.01*B(10)
1385 PK=-.01*B(11)-.01*B(12)-5*B(13)-2*B(14)
1386 PL=-10*B(15)
1588 P=PH+PI+PJ+PK+PL
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 12
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-45 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),M,JJJJ
1999 NEXT JJJJ
One notes that the artificial .01 flows of lines 1381, 1384 and 1385 replace the original 0 flows.
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 10 seconds of running is presented below. (What immediately follows is a manual copy from the computer screen.)
0 1 2 0 1
1 0 0 0 1
1 2 -43.13 -31989
0 0 0 1 1
2 2 1 0 2
1 1 -43.13 -31910
0 0 0 1 1
2 0 1 2 0
1 1 -43.13 -31906
2 1 1 2 1
0 1 1 2 0
0 0 -43.13 -31884
1 1 2 0 0
0 2 1 1 2
1 0 -43.13 -31825
1 1 1 2 2
2 0 1 2 0
1 2 -43.11 -31793
2 1 0 2 1
1 2 2 2 1
1 0 -43.13 -31779
The candidate solution above at JJJJ=-31793 is usable. Interpreted in accordance with line 1912 through line 1914, the output through JJJJ=-31779 was produced in the first 10 seconds of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Heragu, S. S., and Kusiak, A. (1991), "Efficient models for the facility layout problem," European Journal of Operational Research 53, 1-13.
Nugent, C. E., Vollmann, T. E., and Ruml, J. (1968), "An experimental comparisons of techniques for the assignment of facilities to locations," Operations Research 16, 150-173.
Wednesday, August 12, 2009
An Application of an Integer Programming Computer Program
Jsun Yui Wong
The computer program listed below seeks to solve Example 4 on pages 219-222 of Heragu (2008) with the modification that the five offices are cubes with the following dimensions: 24x24x24, 24x24x24, 34x34x34, 26x26x26, and 28x28x28.
0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(166),A(166),L(166),K(166),P(166),B(166),S(166)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 15
113 A(K)=FIX(RND*699)
115 NEXT K
121 FOR KF=16 TO 45
123 A(KF)=FIX(RND*2)
125 NEXT KF
126 IMAR=10+FIX(RND*3000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 45
131 X(KK)=A(KK)
132 NEXT KK
151 IF RND<.7 GOTO 222 ELSE IF RND<.5 GOTO 236 ELSE GOTO 241
222 IJL=1+FIX(RND*15)
233 IF RND<.95 THEN X(IJL)=FIX(RND*699) ELSE X(IJL)=A(IJL)-1
235 GOTO 501
236 IJR=16+FIX(RND*30)
238 X(IJR)=FIX(RND*2)
239 GOTO 501
241 IF RND<.5 THEN 243 ELSE 248
243 IJU=1+FIX(RND*15):IJV=1+FIX(RND*15)
244 X(IJU)=A(IJV):X(IJV)=A(IJU)
245 GOTO 501
248 IJW=16+FIX(RND*30):IJX=16+FIX(RND*30)
249 X(IJW)=A(IJX):X(IJX)=A(IJW)
501 B(1)=ABS(X(1)-X(2))
502 B(2)=ABS(X(1)-X(3))
503 B(3)=ABS(X(1)-X(4))
504 B(4)=ABS(X(1)-X(5))
505 B(5)=ABS(X(2)-X(3))
506 B(6)=ABS(X(2)-X(4))
507 B(7)=ABS(X(2)-X(5))
508 B(8)=ABS(X(3)-X(4))
509 B(9)=ABS(X(3)-X(5))
510 B(10)=ABS(X(4)-X(5))
511 B(11)=ABS(X(6)-X(7))
512 B(12)=ABS(X(6)-X(8))
513 B(13)=ABS(X(6)-X(9))
514 B(14)=ABS(X(6)-X(10))
515 B(15)=ABS(X(7)-X(8))
516 B(16)=ABS(X(7)-X(9))
517 B(17)=ABS(X(7)-X(10))
518 B(18)=ABS(X(8)-X(9))
519 B(19)=ABS(X(8)-X(10))
520 B(20)=ABS(X(9)-X(10))
521 B(21)=ABS(X(11)-X(12))
522 B(22)=ABS(X(11)-X(13))
523 B(23)=ABS(X(11)-X(14))
524 B(24)=ABS(X(11)-X(15))
525 B(25)=ABS(X(12)-X(13))
526 B(26)=ABS(X(12)-X(14))
527 B(27)=ABS(X(12)-X(15))
528 B(28)=ABS(X(13)-X(14))
529 B(29)=ABS(X(13)-X(15))
530 B(30)=ABS(X(14)-X(15))
901 S(1)=B(1)-24+999*X(16)
902 S(2)=B(11)-24+999*X(17)
903 S(3)=B(21)-24+999*X(18)
913 S(4)=B(2)-29+999*X(19)
914 S(5)=B(12)-29+999*X(20)
915 S(6)=B(22)-29+999*X(21)
925 S(7)=B(3)-25+999*X(22)
926 S(8)=B(13)-25+999*X(23)
927 S(9)=B(23)-25+999*X(24)
937 S(10)=B(4)-26+999*X(25)
938 S(11)=B(14)-26+999*X(26)
939 S(12)=B(24)-26+999*X(27)
949 S(13)=B(5)-29+999*X(28)
950 S(14)=B(15)-29+999*X(29)
951 S(15)=B(25)-29+999*X(30)
961 S(16)=B(6)-25+999*X(31)
962 S(17)=B(16)-25+999*X(32)
963 S(18)=B(26)-25+999*X(33)
973 S(19)=B(7)-26+999*X(34)
974 S(20)=B(17)-26+999*X(35)
975 S(21)=B(27)-26+999*X(36)
985 S(22)=B(8)-30+999*X(37)
986 S(23)=B(18)-30+999*X(38)
987 S(24)=B(28)-30+999*X(39)
997 S(25)=B(9)-31+999*X(40)
998 S(26)=B(19)-31+999*X(41)
999 S(27)=B(29)-31+999*X(42)
1009 S(28)=B(10)-27+999*X(43)
1010 S(29)=B(20)-27+999*X(44)
1011 S(30)=B(30)-27+999*X(45)
1021 SZ(1)=X(16)+X(17)+X(18)-2
1022 SZ(2)=X(19)+X(20)+X(21)-2
1023 SZ(3)=X(22)+X(23)+X(24)-2
1024 SZ(4)=X(25)+X(26)+X(27)-2
1025 SZ(5)=X(28)+X(29)+X(30)-2
1026 SZ(6)=X(31)+X(32)+X(33)-2
1027 SZ(7)=X(34)+X(35)+X(36)-2
1028 SZ(8)=X(37)+X(38)+X(39)-2
1029 SZ(9)=X(40)+X(41)+X(42)-2
1030 SZ(10)=X(43)+X(44)+X(45)-2
1047 FOR IJUG=1 TO 10
1048 IF SZ(IJUG)=0 THEN SZ(IJUG)=0 ELSE SZ(IJUG)=ABS(SZ(IJUG))
1049 NEXT IJUG
1107 FOR IJUL=1 TO 30
1111 IF S(IJUL)<0 THEN S(IJUL)=ABS(S(IJUL)) ELSE S(IJUL)=0
1115 NEXT IJUL
1285 PL11=-333333!*(S(1)+S(2)+S(3)+S(4)+S(5)+S(6)+S(7)+S(8)+S(9)+S(10)+S(11))
1286 PL12=-333333!*(S(12)+S(13)+S(14)+S(15)+S(16)+S(17)+S(18)+S(19)+S(20))
1287 PL13=-333333!*(S(21)+S(22)+S(23)+S(24)+S(25)+S(26)+S(27)+S(28)+S(29))
1288 PL14=-333333!*(S(30))
1299 PL21=-333333!*(SZ(1)+SZ(2)+SZ(3)+SZ(4)+SZ(5)+SZ(6)+SZ(7)+SZ(8)+SZ(9)+SZ(10))
1380 PH=-10*(B(1)+B(11)+B(21))-15*(B(2)+B(12)+B(22))-20*(B(3)+B(13)+B(23))
1381 PI=-30*(B(5)+B(15)+B(25))-35*(B(6)+B(16)+B(26))-10*(B(7)+B(17)+B(27))
1384 PJ=-10*(B(8)+B(18)+B(28))-20*(B(9)+B(19)+B(29))-15*(B(10)+B(20)+B(30))
1587 PK=PH+PI+PJ
1588 P=PK+PL11+PL12+PL13+PL14+PL21
1599 PR=PK
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 45
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-6100 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)
1917 PRINT M,MM,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 12 hours of running is presented below. (What immediately follows is a manual copy from the computer screen.)
345 345 374 345 372
569 569 569 569 569
476 452 457 427 426
-6035 -6035 -28729
267 267 267 267 267
205 205 176 205 178
423 447 442 472 473
-6035 -6035 -14654
Interpreted in accordance with line 1912 through line 1917, the output through JJJJ=-14654 was produced in the first 12 hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Heragu, S. S.: "Facilities Design," Third Edition, CRC Press, Taylor and Francis Group, Boca Raton, Florida, 2008.
Hillier, F. S., and G. J. Lieberman: "Introduction to Operations Research," Sixth Edition, pp. 498-499, McGraw-Hill, Inc., New York, 1995.
The computer program listed below seeks to solve Example 4 on pages 219-222 of Heragu (2008) with the modification that the five offices are cubes with the following dimensions: 24x24x24, 24x24x24, 34x34x34, 26x26x26, and 28x28x28.
0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(166),A(166),L(166),K(166),P(166),B(166),S(166)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 15
113 A(K)=FIX(RND*699)
115 NEXT K
121 FOR KF=16 TO 45
123 A(KF)=FIX(RND*2)
125 NEXT KF
126 IMAR=10+FIX(RND*3000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 45
131 X(KK)=A(KK)
132 NEXT KK
151 IF RND<.7 GOTO 222 ELSE IF RND<.5 GOTO 236 ELSE GOTO 241
222 IJL=1+FIX(RND*15)
233 IF RND<.95 THEN X(IJL)=FIX(RND*699) ELSE X(IJL)=A(IJL)-1
235 GOTO 501
236 IJR=16+FIX(RND*30)
238 X(IJR)=FIX(RND*2)
239 GOTO 501
241 IF RND<.5 THEN 243 ELSE 248
243 IJU=1+FIX(RND*15):IJV=1+FIX(RND*15)
244 X(IJU)=A(IJV):X(IJV)=A(IJU)
245 GOTO 501
248 IJW=16+FIX(RND*30):IJX=16+FIX(RND*30)
249 X(IJW)=A(IJX):X(IJX)=A(IJW)
501 B(1)=ABS(X(1)-X(2))
502 B(2)=ABS(X(1)-X(3))
503 B(3)=ABS(X(1)-X(4))
504 B(4)=ABS(X(1)-X(5))
505 B(5)=ABS(X(2)-X(3))
506 B(6)=ABS(X(2)-X(4))
507 B(7)=ABS(X(2)-X(5))
508 B(8)=ABS(X(3)-X(4))
509 B(9)=ABS(X(3)-X(5))
510 B(10)=ABS(X(4)-X(5))
511 B(11)=ABS(X(6)-X(7))
512 B(12)=ABS(X(6)-X(8))
513 B(13)=ABS(X(6)-X(9))
514 B(14)=ABS(X(6)-X(10))
515 B(15)=ABS(X(7)-X(8))
516 B(16)=ABS(X(7)-X(9))
517 B(17)=ABS(X(7)-X(10))
518 B(18)=ABS(X(8)-X(9))
519 B(19)=ABS(X(8)-X(10))
520 B(20)=ABS(X(9)-X(10))
521 B(21)=ABS(X(11)-X(12))
522 B(22)=ABS(X(11)-X(13))
523 B(23)=ABS(X(11)-X(14))
524 B(24)=ABS(X(11)-X(15))
525 B(25)=ABS(X(12)-X(13))
526 B(26)=ABS(X(12)-X(14))
527 B(27)=ABS(X(12)-X(15))
528 B(28)=ABS(X(13)-X(14))
529 B(29)=ABS(X(13)-X(15))
530 B(30)=ABS(X(14)-X(15))
901 S(1)=B(1)-24+999*X(16)
902 S(2)=B(11)-24+999*X(17)
903 S(3)=B(21)-24+999*X(18)
913 S(4)=B(2)-29+999*X(19)
914 S(5)=B(12)-29+999*X(20)
915 S(6)=B(22)-29+999*X(21)
925 S(7)=B(3)-25+999*X(22)
926 S(8)=B(13)-25+999*X(23)
927 S(9)=B(23)-25+999*X(24)
937 S(10)=B(4)-26+999*X(25)
938 S(11)=B(14)-26+999*X(26)
939 S(12)=B(24)-26+999*X(27)
949 S(13)=B(5)-29+999*X(28)
950 S(14)=B(15)-29+999*X(29)
951 S(15)=B(25)-29+999*X(30)
961 S(16)=B(6)-25+999*X(31)
962 S(17)=B(16)-25+999*X(32)
963 S(18)=B(26)-25+999*X(33)
973 S(19)=B(7)-26+999*X(34)
974 S(20)=B(17)-26+999*X(35)
975 S(21)=B(27)-26+999*X(36)
985 S(22)=B(8)-30+999*X(37)
986 S(23)=B(18)-30+999*X(38)
987 S(24)=B(28)-30+999*X(39)
997 S(25)=B(9)-31+999*X(40)
998 S(26)=B(19)-31+999*X(41)
999 S(27)=B(29)-31+999*X(42)
1009 S(28)=B(10)-27+999*X(43)
1010 S(29)=B(20)-27+999*X(44)
1011 S(30)=B(30)-27+999*X(45)
1021 SZ(1)=X(16)+X(17)+X(18)-2
1022 SZ(2)=X(19)+X(20)+X(21)-2
1023 SZ(3)=X(22)+X(23)+X(24)-2
1024 SZ(4)=X(25)+X(26)+X(27)-2
1025 SZ(5)=X(28)+X(29)+X(30)-2
1026 SZ(6)=X(31)+X(32)+X(33)-2
1027 SZ(7)=X(34)+X(35)+X(36)-2
1028 SZ(8)=X(37)+X(38)+X(39)-2
1029 SZ(9)=X(40)+X(41)+X(42)-2
1030 SZ(10)=X(43)+X(44)+X(45)-2
1047 FOR IJUG=1 TO 10
1048 IF SZ(IJUG)=0 THEN SZ(IJUG)=0 ELSE SZ(IJUG)=ABS(SZ(IJUG))
1049 NEXT IJUG
1107 FOR IJUL=1 TO 30
1111 IF S(IJUL)<0 THEN S(IJUL)=ABS(S(IJUL)) ELSE S(IJUL)=0
1115 NEXT IJUL
1285 PL11=-333333!*(S(1)+S(2)+S(3)+S(4)+S(5)+S(6)+S(7)+S(8)+S(9)+S(10)+S(11))
1286 PL12=-333333!*(S(12)+S(13)+S(14)+S(15)+S(16)+S(17)+S(18)+S(19)+S(20))
1287 PL13=-333333!*(S(21)+S(22)+S(23)+S(24)+S(25)+S(26)+S(27)+S(28)+S(29))
1288 PL14=-333333!*(S(30))
1299 PL21=-333333!*(SZ(1)+SZ(2)+SZ(3)+SZ(4)+SZ(5)+SZ(6)+SZ(7)+SZ(8)+SZ(9)+SZ(10))
1380 PH=-10*(B(1)+B(11)+B(21))-15*(B(2)+B(12)+B(22))-20*(B(3)+B(13)+B(23))
1381 PI=-30*(B(5)+B(15)+B(25))-35*(B(6)+B(16)+B(26))-10*(B(7)+B(17)+B(27))
1384 PJ=-10*(B(8)+B(18)+B(28))-20*(B(9)+B(19)+B(29))-15*(B(10)+B(20)+B(30))
1587 PK=PH+PI+PJ
1588 P=PK+PL11+PL12+PL13+PL14+PL21
1599 PR=PK
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 45
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-6100 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)
1917 PRINT M,MM,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 12 hours of running is presented below. (What immediately follows is a manual copy from the computer screen.)
345 345 374 345 372
569 569 569 569 569
476 452 457 427 426
-6035 -6035 -28729
267 267 267 267 267
205 205 176 205 178
423 447 442 472 473
-6035 -6035 -14654
Interpreted in accordance with line 1912 through line 1917, the output through JJJJ=-14654 was produced in the first 12 hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
Heragu, S. S.: "Facilities Design," Third Edition, CRC Press, Taylor and Francis Group, Boca Raton, Florida, 2008.
Hillier, F. S., and G. J. Lieberman: "Introduction to Operations Research," Sixth Edition, pp. 498-499, McGraw-Hill, Inc., New York, 1995.
Subscribe to:
Posts (Atom)