Jsun Yui Wong
The complete computer program listed below uses the example in Carlson and Nemhauser (1966) to illustrate an algorithm for its scheduling problem.
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)=0:TBM(1,3)=2:TBM(1,4)=4:TBM(1,5)=3
12 TBM(2,1)=0:TBM(2,2)=0:TBM(2,3)=6:TBM(2,4)=2:TBM(2,5)=3
13 TBM(3,1)=2:TBM(3,2)=6:TBM(3,3)=0:TBM(3,4)=5:TBM(3,5)=3
14 TBM(4,1)=4:TBM(4,2)=2:TBM(4,3)=5:TBM(4,4)=0:TBM(4,5)=3
15 TBM(5,1)=3:TBM(5,2)=3:TBM(5,3)=3:TBM(5,4)=3:TBM(5,5)=0
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>-10 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 1 3 2 2
-6 -32000
2 2 1 3 3
-6 -31999
1 1 2 3 2
-6 -31998
3 3 1 2 2
-6 -31997
1 1 3 2 3
-6 -31996
1 3 1 3 2
-8 -31995
Interpreted in accordance with line 1912 and line 1927, the output through JJJJ=-31995 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.
Reference
Carlson, R. C. and G. L. Nemhauser, "Scheduling to Minimize Interaction Cost," Operations Research 14, 52-58 (Jan.-Feb., 1966).
