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 51 through line 195 are from Nugent, Vollmann, and Ruml (1968, p. 170); this illustration has thirty activities and seven 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),T(466)
6 DIM TBM(33,33),TZ(33,33)
51 TBM(1,2)=1:TBM(1,3)=2:TBM(1,4)=3:TBM(1,5)=4:TBM(1,6)=5:TBM(1,7)=1:TBM(1,8)=2:TBM(1,9)=3:TBM(1,10)=4
52 TBM(1,11)=5:TBM(1,12)=6:TBM(1,13)=2:TBM(1,14)=3:TBM(1,15)=4:TBM(1,16)=5:TBM(1,17)=6:TBM(1,18)=7:TBM(1,19)=3:TBM(1,20)=4
53 TBM(1,21)=5:TBM(1,22)=6:TBM(1,23)=7:TBM(1,24)=8:TBM(1,25)=4:TBM(1,26)=5:TBM(1,27)=6:TBM(1,28)=7:TBM(1,29)=8:TBM(1,30)=9
63 TBM(2,3)=1:TBM(2,4)=2:TBM(2,5)=3:TBM(2,6)=4:TBM(2,7)=2:TBM(2,8)=1:TBM(2,9)=2:TBM(2,10)=3
64 TBM(2,11)=4:TBM(2,12)=5:TBM(2,13)=3:TBM(2,14)=2:TBM(2,15)=3:TBM(2,16)=4:TBM(2,17)=5:TBM(2,18)=6:TBM(2,19)=4:TBM(2,20)=3
65 TBM(2,21)=4:TBM(2,22)=5:TBM(2,23)=6:TBM(2,24)=7:TBM(2,25)=5:TBM(2,26)=4:TBM(2,27)=5:TBM(2,28)=6:TBM(2,29)=7:TBM(2,30)=8
67 TBM(3,4)=1:TBM(3,5)=2:TBM(3,6)=3:TBM(3,7)=3:TBM(3,8)=2:TBM(3,9)=1:TBM(3,10)=2
68 TBM(3,11)=3:TBM(3,12)=4:TBM(3,13)=4:TBM(3,14)=3:TBM(3,15)=2:TBM(3,16)=3:TBM(3,17)=4:TBM(3,18)=5:TBM(3,19)=5:TBM(3,20)=4
69 TBM(3,21)=3:TBM(3,22)=4:TBM(3,23)=5:TBM(3,24)=6:TBM(3,25)=6:TBM(3,26)=5:TBM(3,27)=4:TBM(3,28)=5:TBM(3,29)=6:TBM(3,30)=7
77 TBM(4,5)=1:TBM(4,6)=2:TBM(4,7)=4:TBM(4,8)=3:TBM(4,9)=2:TBM(4,10)=1
78 TBM(4,11)=2:TBM(4,12)=3:TBM(4,13)=5:TBM(4,14)=4:TBM(4,15)=3:TBM(4,16)=2:TBM(4,17)=3:TBM(4,18)=4:TBM(4,19)=6:TBM(4,20)=5
79 TBM(4,21)=4:TBM(4,22)=3:TBM(4,23)=4:TBM(4,24)=5:TBM(4,25)=7:TBM(4,26)=6:TBM(4,27)=5:TBM(4,28)=4:TBM(4,29)=5:TBM(4,30)=6
81 TBM(5,1)=4:TBM(5,2)=3:TBM(5,3)=2:TBM(5,4)=1:TBM(5,5)=999:TBM(5,6)=1:TBM(5,7)=5:TBM(5,8)=4:TBM(5,9)=3:TBM(5,10)=2
82 TBM(5,11)=1:TBM(5,12)=2:TBM(5,13)=6:TBM(5,14)=5:TBM(5,15)=4:TBM(5,16)=3:TBM(5,17)=2:TBM(5,18)=3:TBM(5,19)=7:TBM(5,20)=6
83 TBM(5,21)=5:TBM(5,22)=4:TBM(5,23)=3:TBM(5,24)=4:TBM(5,25)=8:TBM(5,26)=7:TBM(5,27)=6:TBM(5,28)=5:TBM(5,29)=4:TBM(5,30)=5
93 TBM(6,7)=6:TBM(6,8)=5:TBM(6,9)=4:TBM(6,10)=3
94 TBM(6,11)=2:TBM(6,12)=1:TBM(6,13)=7:TBM(6,14)=6:TBM(6,15)=5:TBM(6,16)=4:TBM(6,17)=3:TBM(6,18)=2:TBM(6,19)=8:TBM(6,20)=7
95 TBM(6,21)=6:TBM(6,22)=5:TBM(6,23)=4:TBM(6,24)=3:TBM(6,25)=9:TBM(6,26)=8:TBM(6,27)=7:TBM(6,28)=6:TBM(6,29)=5:TBM(6,30)=4
97 TBM(7,8)=1:TBM(7,9)=2:TBM(7,10)=3
98 TBM(7,11)=4:TBM(7,12)=5:TBM(7,13)=1:TBM(7,14)=2:TBM(7,15)=3:TBM(7,16)=4:TBM(7,17)=5:TBM(7,18)=6:TBM(7,19)=2:TBM(7,20)=3
99 TBM(7,21)=4:TBM(7,22)=5:TBM(7,23)=6:TBM(7,24)=7:TBM(7,25)=3:TBM(7,26)=4:TBM(7,27)=5:TBM(7,28)=6:TBM(7,29)=7:TBM(7,30)=8
101 TBM(8,9)=1:TBM(8,10)=2
102 TBM(8,11)=3:TBM(8,12)=4:TBM(8,13)=2:TBM(8,14)=1:TBM(8,15)=2:TBM(8,16)=3:TBM(8,17)=4:TBM(8,18)=5:TBM(8,19)=3:TBM(8,20)=2
103 TBM(8,21)=3:TBM(8,22)=4:TBM(8,23)=5:TBM(8,24)=6:TBM(8,25)=4:TBM(8,26)=3:TBM(8,27)=4:TBM(8,28)=5:TBM(8,29)=6:TBM(8,30)=7
105 TBM(9,10)=1
106 TBM(9,11)=2:TBM(9,12)=3:TBM(9,13)=3:TBM(9,14)=2:TBM(9,15)=1:TBM(9,16)=2:TBM(9,17)=3:TBM(9,18)=4:TBM(9,19)=4:TBM(9,20)=3
107 TBM(9,21)=2:TBM(9,22)=3:TBM(9,23)=4:TBM(9,24)=5:TBM(9,25)=5:TBM(9,26)=4:TBM(9,27)=3:TBM(9,28)=4:TBM(9,29)=5:TBM(9,30)=6
110 TBM(10,11)=1:TBM(10,12)=2:TBM(10,13)=4:TBM(10,14)=3:TBM(10,15)=2:TBM(10,16)=1:TBM(10,17)=2:TBM(10,18)=3:TBM(10,19)=5:TBM(10,20)=4
111 TBM(10,21)=3:TBM(10,22)=2:TBM(10,23)=3:TBM(10,24)=4:TBM(10,25)=6:TBM(10,26)=5:TBM(10,27)=4:TBM(10,28)=3:TBM(10,29)=4:TBM(10,30)=5
114 TBM(11,12)=1:TBM(11,13)=5:TBM(11,14)=4:TBM(11,15)=3:TBM(11,16)=2:TBM(11,17)=1:TBM(11,18)=2:TBM(11,19)=6:TBM(11,20)=5
115 TBM(11,21)=4:TBM(11,22)=3:TBM(11,23)=2:TBM(11,24)=3:TBM(11,25)=7:TBM(11,26)=6:TBM(11,27)=5:TBM(11,28)=4:TBM(11,29)=3:TBM(11,30)=4
118 TBM(12,13)=6:TBM(12,14)=5:TBM(12,15)=4:TBM(12,16)=3:TBM(12,17)=2:TBM(12,18)=1:TBM(12,19)=7:TBM(12,20)=6
119 TBM(12,21)=5:TBM(12,22)=4:TBM(12,23)=3:TBM(12,24)=2:TBM(12,25)=8:TBM(12,26)=7:TBM(12,27)=6:TBM(12,28)=5:TBM(12,29)=4:TBM(12,30)=3
122 TBM(13,14)=1:TBM(13,15)=2:TBM(13,16)=3:TBM(13,17)=4:TBM(13,18)=5:TBM(13,19)=1:TBM(13,20)=2
123 TBM(13,21)=3:TBM(13,22)=4:TBM(13,23)=5:TBM(13,24)=6:TBM(13,25)=2:TBM(13,26)=3:TBM(13,27)=4:TBM(13,28)=5:TBM(13,29)=6:TBM(13,30)=7
126 TBM(14,15)=1:TBM(14,16)=2:TBM(14,17)=3:TBM(14,18)=4:TBM(14,19)=2:TBM(14,20)=1
127 TBM(14,21)=2:TBM(14,22)=3:TBM(14,23)=4:TBM(14,24)=5:TBM(14,25)=3:TBM(14,26)=2:TBM(14,27)=3:TBM(14,28)=4:TBM(14,29)=5:TBM(14,30)=6
136 TBM(15,16)=1:TBM(15,17)=2:TBM(15,18)=3:TBM(15,19)=3:TBM(15,20)=2
137 TBM(15,21)=1:TBM(15,22)=2:TBM(15,23)=3:TBM(15,24)=4:TBM(15,25)=4:TBM(15,26)=3:TBM(15,27)=2:TBM(15,28)=3:TBM(15,29)=4:TBM(15,30)=5
140 TBM(16,17)=1:TBM(16,18)=2:TBM(16,19)=4:TBM(16,20)=3
141 TBM(16,21)=2:TBM(16,22)=1:TBM(16,23)=2:TBM(16,24)=3:TBM(16,25)=5:TBM(16,26)=4:TBM(16,27)=3:TBM(16,28)=2:TBM(16,29)=3:TBM(16,30)=4
144 TBM(17,18)=1:TBM(17,19)=5:TBM(17,20)=4
145 TBM(17,21)=3:TBM(17,22)=2:TBM(17,23)=1:TBM(17,24)=2:TBM(17,25)=6:TBM(17,26)=5:TBM(17,27)=4:TBM(17,28)=3:TBM(17,29)=2:TBM(17,30)=3
148 TBM(18,19)=6:TBM(18,20)=5
149 TBM(18,21)=4:TBM(18,22)=3:TBM(18,23)=2:TBM(18,24)=1:TBM(18,25)=7:TBM(18,26)=6:TBM(18,27)=5:TBM(18,28)=4:TBM(18,29)=3:TBM(18,30)=2
152 TBM(19,20)=1
153 TBM(19,21)=2:TBM(19,22)=3:TBM(19,23)=4:TBM(19,24)=5:TBM(19,25)=1:TBM(19,26)=2:TBM(19,27)=3:TBM(19,28)=4:TBM(19,29)=5:TBM(19,30)=6
157 TBM(20,21)=1:TBM(20,22)=2:TBM(20,23)=3:TBM(20,24)=4:TBM(20,25)=2:TBM(20,26)=1:TBM(20,27)=2:TBM(20,28)=3:TBM(20,29)=4:TBM(20,30)=5
163 TBM(21,22)=1:TBM(21,23)=2:TBM(21,24)=3:TBM(21,25)=3:TBM(21,26)=2:TBM(21,27)=1:TBM(21,28)=2:TBM(21,29)=3:TBM(21,30)=4
167 TBM(22,23)=1:TBM(22,24)=2:TBM(22,25)=4:TBM(22,26)=3:TBM(22,27)=2:TBM(22,28)=1:TBM(22,29)=2:TBM(22,30)=3
171 TBM(23,24)=1:TBM(23,25)=5:TBM(23,26)=4:TBM(23,27)=3:TBM(23,28)=2:TBM(23,29)=1:TBM(23,30)=2
175 TBM(24,25)=6:TBM(24,26)=5:TBM(24,27)=4:TBM(24,28)=3:TBM(24,29)=2:TBM(24,30)=1
179 TBM(25,26)=1:TBM(25,27)=2:TBM(25,28)=3:TBM(25,29)=4:TBM(25,30)=5
183 TBM(26,27)=1:TBM(26,28)=2:TBM(26,29)=3:TBM(26,30)=4
187 TBM(27,28)=1:TBM(27,29)=2:TBM(27,30)=3
191 TBM(28,29)=1:TBM(28,30)=2
195 TBM(29,30)=1
220 FOR JJJJ=-32000 TO 32000
221 RANDOMIZE JJJJ
222 M=-1D+17
223 FOR I=1 TO 30
224 A(I)=1+FIX(RND*7)
225 NEXT I
226 IMAR=10+FIX(RND*1000)
228 FOR I=1 TO IMAR
229 FOR KK=1 TO 30
231 X(KK)=A(KK)
232 NEXT KK
330 IJM=1+FIX(RND*30)
331 IJN=1+FIX(RND*30)
333 X(IJM)=A(IJN):X(IJN)=A(IJM)
351 FOR K=1 TO 30
361 FOR J=K+1 TO 30
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 30
1594 FOR J=K+1 TO 30
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 30
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 228
1670 NEXT I
1890 IF M>-80 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),A(19),A(20)
1916 PRINT A(21),A(22),A(23),A(24),A(25)
1917 PRINT A(26),A(27),A(28),A(29),A(30)
1927 PRINT M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the best candidate solution produced during the first four hours of running is presented below. What immediately follows is a manual copy from the computer screen.
2 2 2 2 1
1 7 7 3 3
1 1 7 7 3
3 3 1 4 4
5 5 6 6 4
4 5 5 6 6
-74 -30740
74 may or may not be optimal. Interpreted in accordance with line 1912 through line 1927, the candidate solution presented above was produced during the first four hours 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).
Nugent, C. E., T. E. Vollmann, and J. Ruml, "An Experimental Comparison of Techniques for the Assignment of Facilities to Locations," Operations Research 16, 150-173 (Jan.-Feb., 1968).
Vredeveld, T., and J. K. Lenstra, "On Local Search for the Generalized Graph Coloring Problem," Operations Research Letters 31, 28-34 (2003).
