Jsun Yui Wong
The computer programn listed below is concerned with the scheduling problem of Carlson and Nemhauser (1966). As shown in line 32 below for a case of scheduling eight activities among three facilities, the interaction cost between activity 1 and activity 2 (if scheduled on the same facility), the interaction cost between activity 1 and activity 3, the interaction cost between activity 1 and activity 4, ..., and the interaction cost between activity 7 and activity 8 are 10, 12, 11, ..., and 12, 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(33),HT(33,33),TM(24,24),HR(24,24)
21 FOR IW=1 TO 7
23 FOR JW=IW+1 TO 8
26 READ HR(IW,JW)
28 NEXT JW
29 NEXT IW
32 DATA 10,12,11,12,17,13,9,12,11,12,17,13,9,13,14,19,15,11,13,18,14,10,19,15,11,20,16,12
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 8
88 A(I)=FIX(RND*3)
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*3)
533 FOR IX=1 TO 7
534 FOR JX=IX+1 TO 8
542 IF X(IX)=X(JX) THEN TM(IX,JX)=HR(IX,JX) ELSE TM(IX,JX)=0
545 NEXT JX
547 NEXT IX
1611 SUMTL=0
1612 FOR IR1=1 TO 7
1614 FOR IR2=IR1+1 TO 8
1616 SUMTL=SUMTL+TM(IR1,IR2)
1617 NEXT IR2
1619 NEXT IR1
1645 P=-SUMTL
1656 IF P<=M THEN 1670
1657 FOR KEW=1 TO 8
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-90 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),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 three seconds of running is presented below. What immediately follows is a manual copy from the computer screen.
1 2 2 1 2
0 0 1 -88 -31997
1 0 0 0 1
2 2 1 -88 -31996
2 2 0 0 1
1 0 2 -89 -31994
0 0 2 2 0
1 1 2 -88 -31992
Interpreted in accordance with line 1912 and line 1914, the output above was produced during the first three seconds 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
Carlson, R. C., and G. L. Nemhauser, "Scheduling to Minimize Interaction Cost," Operations Research 14, 52-58 (1966).
