Jsun Yui Wong
The complete computer program listed below illustrates an algorithm for solving the Carlson and Nemhauser (1966) scheduling problem. The interaction costs in line 11 through line 15 below are from Land (1963, p. 188); this illustration has five activities and three facilities.
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 TBM(33,33),TZ(33,33)
11 TBM(1,1)=0:TBM(1,2)=28:TBM(1,3)=33:TBM(1,4)=22:TBM(1,5)=20
12 TBM(2,1)=28:TBM(2,2)=0:TBM(2,3)=27:TBM(2,4)=40:TBM(2,5)=25
13 TBM(3,1)=33:TBM(3,2)=27:TBM(3,3)=0:TBM(3,4)=30:TBM(3,5)=15
14 TBM(4,1)=22:TBM(4,2)=40:TBM(4,3)=30:TBM(4,4)=0:TBM(4,5)=18
15 TBM(5,1)=20:TBM(5,2)=25:TBM(5,3)=15:TBM(5,4)=18:TBM(5,5)=0
51 REM
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 5
87 A(I)=1+FIX(RND*3)
89 NEXT I
126 IMAR=10+FIX(RND*0)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 5
131 X(KK)=A(KK)
132 NEXT KK
151 JK=1+FIX(RND*5)
153 X(JK)=1+FIX(RND*3)
330 IJM=1+FIX(RND*5)
331 IJN=1+FIX(RND*5)
333 X(IJM)=A(IJN):X(IJN)=A(IJM)
351 FOR K=1 TO 5
361 FOR J=1 TO 5
363 IF X(K)=X(J) THEN TZ(K,J)=TBM(K,J) ELSE TZ(K,J)=0
366 NEXT J
399 NEXT K
1590 SUMTZ=0
1591 FOR K=1 TO 13
1594 FOR J=1 TO 13
1596 SUMTZ=SUMTZ+TZ(K,J)
1597 NEXT J
1598 NEXT K
1609 P=-SUMTZ
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 5
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-150 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1927 PRINT M,JJJJ
1999 NEXT JJJJ
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 3 2 1 2
-74 -32000
3 2 2 1 1
-90 -31999
1 3 2 1 2
-74 -31998
1 2 2 3 3
-90 -31997
1 2 2 3 3
-90 -31996
2 1 3 2 3
-74 -31995
1 2 3 1 3
-74 -31994
Interpreted in accordance with line 1912 and line 1927, the output through
JJJJ=-31994 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
Carlson, R. C., and G. L. Nemhauser. "Scheduling to Minimize Interaction Cost," Operations Research 14, 52-58 (Jan.-Feb., 1966).
Land, A. H. "A Problem of Assignment with Inter-Related Costs," Operational Research Quarterly 14, 185-199 (June 1963).
