Jsun Yui Wong
The complete computer program listed below illustrates an algorithm for solving the Carlson and Nemhauser (1966) scheduling problem. Modeled after that of the July 24 post of the present blog, the following computer program has 56 activities and 6 facilities. The interaction costs in line 51 through line 219 are from Skorin-Kapov (1990, Figure 11C).
0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(80),A(80),L(80),K(80),P(80),B(80),S(80)
6 DIM T(70,70),TZ(70,70)
51 T(1,2)=1:T(1,4)=4:T(1,6)=3:T(1,7)=5:T(1,8)=2:T(1,9)=4:T(1,12)=1:T(1,5)=1:T(1,16)=5
52 T(1,17)=2:T(1,18)=2:T(1,20)=5:T(1,21)=4:T(1,16)=1:T(1,27)=5:T(1,28)=10:T(1,29)=5:T(1,30)=1:T(1,32)=5
53 T(1,33)=2:T(1,36)=5:T(1,37)=10:T(1,39)=4:T(1,40)=5:T(1,41)=2:T(1,42)=1:T(1,43)=2:T(1,44)=1:T(1,45)=5
54 T(1,46)=2:T(1,47)=5:T(1,48)=10:T(1,49)=5:T(1,50)=10:T(1,52)=2:T(1,53)=1:T(1,55)=1:T(1,56)=1
63 T(2,4)=5:T(2,6)=10:T(2,8)=5:T(2,9)=10:T(2,10)=5:T(2,11)=5:T(2,12)=10: T(2,15)=1
64 T(2,16)=2:T(2,18)=5:T(2,21)=2:T(2,23)=2:T(2,24)=1:T(2,25)=1:T(2,26)=2:T(2,27)=10:T(2,28)=5:T(2,30)=10
65 T(2,31)=1:T(2,33)=3:T(2,36)=1:T(2,37)=2:T(2,38)=5:T(2,39)=2:T(2,40)=1:T(2,42)=1:T(2,43)=1:T(2,44)=1
66 T(2,45)=5:T(2,46)=6:T(2,47)=3:T(2,48)=2:T(2,56)=5
67 T(3,4)=1:T(3,5)=5:T(3,6)=2:T(3,12)=6:T(3,13)=1:T(3,15)=1:T(3,16)=1
68 T(3,17)=1:T(3,19)=2:T(3,21)=2:T(3,22)=1:T(3,23)=1:T(3,24)=2:T(3,25)=1:T(3,26)=3:T(3,27)=2:T(3,28)=5
69 T(3,30)=10:T(3,31)=2:T(3,32)=10:T(3,38)=5:T(3,39)=1:T(3,41)=3:T(3,42)=5:T(3,44)=5:T(3,46)=5:T(3,47)=5
70 T(3,49)=10:T(3,51)=2:T(3,52)=5:T(3,55)=10:T(3,56)=2
77 T(4,5)=5:T(4,6)=4:T(4,7)=10:T(4,8)=4:T(4,9)=3:T(4,10)=5
78 T(4,12)=5:T(4,15)=10:T(4,16)=5:T(4,18)=2:T(4,19)=2:T(4,20)=10:T(4,21)=2:T(4,22)=1:T(4,23)=2:T(4,25)=10
79 T(4,27)=1:T(4,29)=6:T(4,30)=2:T(4,32)=5:T(4,33)=1:T(4,34)=5:T(4,35)=2:T(4,36)=5:T(4,37)=1:T(4,39)=1
80 T(4,41)=2:T(4,42)=2:T(4,45)=4:T(4,46)=10:T(4,48)=5:T(4,52)=2:T(4,53)=10:T(4,54)=1:T(4,55)=10:T(4,56)=5
81 T(5,6)=1:T(5,7)=1:T(5,8)=1:T(5,9)=2:T(5,11)=10:T(5,12)=5:T(5,13)=2:T(5,14)=5:T(5,15)=5:T(5,16)=2
82 T(5,18)=5:T(5,19)=5:T(5,20)=10:T(5,22)=1:T(5,23)=2:T(5,24)=1:T(5,25)=2:T(5,26)=2:T(5,27)=5:T(5,28)=6
83 T(5,29)=10:T(5,30)=2:T(5,31)=5:T(5,32)=10:T(5,33)=10:T(5,34)=10:T(5,35)=1:T(5,36)=2:T(5,37)=2:T(5,38)=2
84 T(5,39)=2:T(5,40)=5:T(5,41)=4:T(5,44)=5:T(5,45)=5:T(5,46)=2:T(5,47)=5:T(5,48)=10:T(5,50)=5:T(5,51)=5
85 T(5,52)=5:T(5,54)=2:T(5,55)=3:T(5,56)=10
93 T(6,7)=1:T(6,8)=1:T(6,11)=2:T(6,12)=2
94 T(6,17)=1:T(6,19)=5:T(6,20)=10:T(6,21)=5:T(6,22)=10:T(6,23)=1:T(6,24)=10:T(6,25)=2:T(6,26)=10:T(6,27)=2
95 T(6,28)=5:T(6,29)=5:T(6,31)=2:T(6,32)=2:T(6,33)=1:T(6,35)=1:T(6,36)=5:T(6,37)=5:T(6,38)=10:T(6,40)=2
96 T(6,41)=1:T(6,42)=2:T(6,43)=1:T(6,44)=1:T(6,45)=10:T(6,46)=10:T(6,49)=5:T(6,52)=1:T(6,53)=2:T(6,54)=5:T(6,55)=10:T(6,56)=1
97 T(7,8)=6:T(7,9)=2:T(7,10)=2
98 T(7,11)=10:T(7,12)=2:T(7,13)=10:T(7,14)=2:T(7,15)=4:T(7,16)=6:T(7,19)=1:T(7,20)=4:T(7,21)=4:T(7,22)=2
99 T(7,23)=5:T(7,24)=5:T(7,25)=2:T(7,26)=1:T(7,29)=10:T(7,30)=2:T(7,31)=6:T(7,32)=2:T(7,33)=2:T(7,34)=6
100 T(7,36)=5:T(7,37)=4:T(7,38)=2:T(7,40)=2:T(7,41)=2:T(7,43)=1:T(7,44)=5:T(7,45)=2:T(7,47)=2:T(7,49)=1:T(7,51)=2:T(7,52)=10
101 T(8,9)=5:T(8,11)=10
102 T(8,12)=5:T(8,15)=2:T(8,16)=4:T(8,19)=5:T(8,20)=5:T(8,21)=2:T(8,22)=5:T(8,23)=2:T(8,24)=5:T(8,25)=5
103 T(8,28)=2:T(8,29)=2:T(8,30)=5:T(8,31)=1:T(8,36)=5:T(8,37)=5:T(8,39)=1:T(8,40)=1:T(8,41)=3:T(8,43)=1
104 T(8,44)=5:T(8,45)=2:T(8,46)=3:T(8,47)=2:T(8,48)=5:T(8,50)=10:T(8,52)=4:T(8,53)=5:T(8,54)=5:T(8,55)=5:T(8,56)=10
105 T(9,10)=4
106 T(9,12)=5:T(9,14)=5:T(9,16)=2:T(9,18)=2:T(9,19)=1:T(9,20)=2:T(9,23)=5:T(9,24)=10:T(9,25)=10:T(9,26)=1
107 T(9,27)=5:T(9,28)=2:T(9,29)=1:T(9,30)=10:T(9,31)=1:T(9,33)=10:T(9,34)=1:T(9,35)=2:T(9,36)=5:T(9,37)=5
108 T(9,38)=4:T(9,39)=3:T(9,40)=10:T(9,41)=1:T(9,42)=10:T(9,43)=1:T(9,44)=5:T(9,46)=1:T(9,50)=10:T(9,51)=6:T(9,52)=5:T(9,55)=2:T(9,56)=5
110 T(10,12)=2:T(10,13)=5:T(10,15)=5:T(10,17)=1:T(10,20)=10:T(10,21)=1:T(10,22)=3:T(10,26)=2:T(10,27)=3:T(10,29)=3
111 T(10,30)=2:T(10,33)=5:T(10,34)=3:T(10,35)=5:T(10,36)=10:T(10,39)=5:T(10,40)=10:T(10,42)=2:T(10,44)=5:T(10,45)=2
112 T(10,46)=2:T(10,47)=2:T(10,48)=1:T(10,49)=6:T(10,50)=10:T(10,51)=5:T(10,52)=6:T(10,53)=2:T(10,54)=2:T(10,55)=1
114 T(11,13)=1:T(11,14)=5:T(11,18)=5:T(11,19)=1:T(11,20)=1:T(11,21)=10:T(11,22)=10:T(11,23)=4:T(11,26)=2
115 T(11,27)=5:T(11,29)=4:T(11,30)=10
116 T(11,32)=5:T(11,35)=1:T(11,36)=5:T(11,37)=10:T(11,40)=2:T(11,41)=1:T(11,42)=1:T(11,43)=2:T(11,44)=5:T(11,45)=2
117 T(11,46)=1:T(11,48)=1:T(11,49)=10:T(11,50)=5:T(11,51)=1:T(11,53)=2:T(11,54)=1:T(11,55)=4:T(11,56)=5
118 T(12,13)=10:T(12,14)=10:T(12,15)=3:T(12,17)=1:T(12,18)=5:T(12,19)=1:T(12,20)=5:T(12,21)=2
119 T(12,22)=1:T(12,25)=1:T(12,27)=10:T(12,28)=3:T(12,30)=1:T(12,31)=5:T(12,32)=1:T(12,33)=5:T(12,34)=2:T(12,35)=2
120 T(12,37)=6:T(12,38)=1:T(12,39)=5:T(12,41)=5:T(12,42)=5:T(12,45)=5:T(12,46)=3:T(12,47)=1:T(12,48)=10:T(12,50)=5
121 T(12,51)=2:T(12,52)=1:T(12,53)=5:T(12,55)=5:T(12,56)=5
122 T(13,14)=1:T(13,17)=2:T(13,18)=10:T(13,19)=1:T(13,20)=1:T(13,21)=5:T(13,23)=2
123 T(13,24)=5:T(13,25)=5:T(13,27)=5:T(13,28)=1:T(13,29)=2:T(13,30)=4:T(13,32)=2:T(13,33)=2:T(13,34)=6:T(13,35)=5
124 T(13,36)=5:T(13,37)=5:T(13,38)=5:T(13,40)=10:T(13,41)=2:T(13,42)=5:T(13,44)=10:T(13,46)=1:T(13,48)=4:T(13,51)=2
125 T(13,53)=1:T(13,55)=5:T(13,56)=10
126 T(14,15)=1:T(14,16)=2:T(14,18)=3:T(14,19)=1:T(14,20)=1:T(14,21)=2
127 T(14,22)=2:T(14,23)=2:T(14,24)=10:T(14,25)=4:T(14,26)=2:T(14,27)=4:T(14,28)=10:T(14,29)=2:T(14,31)=4:T(14,33)=2
128 T(14,35)=5:T(14,36)=10:T(14,37)=3:T(14,38)=1:T(14,40)=2:T(14,41)=10:T(14,42)=5:T(14,44)=5:T(14,46)=2:T(14,47)=5
129 T(14,48)=2:T(14,49)=10:T(14,51)=1:T(14,52)=5:T(14,53)=10:T(14,54)=5:T(14,55)=5
136 T(15,17)=10:T(15,18)=10:T(15,21)=2:T(15,22)=5:T(15,24)=2
137 T(15,25)=5:T(15,26)=6:T(15,28)=5:T(15,29)=2:T(15,31)=5:T(15,32)=2:T(15,35)=2:T(15,36)=2:T(15,37)=2:T(15,38)=1
138 T(15,40)=5:T(15,41)=1:T(15,42)=4:T(15,46)=10:T(15,49)=2:T(15,50)=1:T(15,54)=5:T(15,55)=1:T(15,56)=1
140 T(16,20)=5:T(16,21)=10:T(16,22)=2:T(16,23)=2
141 T(16,24)=2:T(16,25)=5:T(16,26)=4:T(16,27)=10:T(16,28)=1:T(16,31)=2:T(16,32)=3:T(16,33)=4:T(16,34)=2:T(16,36)=1
143 T(16,38)=1:T(16,42)=1:T(16,43)=2:T(16,44)=5:T(16,46)=4:T(16,47)=5:T(16,48)=2:T(16,49)=2:T(16,50)=5:T(16,51)=2:T(16,52)=1:T(16,53)=3:T(16,54)=1:T(16,55)=5:T(16,56)=5
144 T(17,18)=1:T(17,19)=5:T(17,20)=10
145 T(17,21)=1:T(17,22)=5:T(17,23)=10:T(17,24)=6:T(17,26)=5:T(17,27)=10:T(17,28)=5:T(17,30)=5:T(17,31)=5:T(17,33)=4
146 T(17,35)=1:T(17,36)=3:T(17,37)=1:T(17,38)=2:T(17,39)=5:T(17,40)=2:T(17,41)=1:T(17,42)=3:T(17,43)=1:T(17,44)=1
147 T(17,45)=5:T(17,46)=6:T(17,47)=1:T(17,48)=10:T(17,49)=2:T(17,51)=10:T(17,53)=1:T(17,54)=2
148 T(18,19)=6:T(18,23)=10
149 T(18,24)=2:T(18,25)=2:T(18,26)=4:T(18,30)=3:T(18,31)=5:T(18,32)=6:T(18,33)=3:T(18,35)=10:T(18,36)=6:T(18,37)=5
150 T(18,39)=5:T(18,40)=5:T(18,41)=1:T(18,42)=2:T(18,43)=3:T(18,44)=10:T(18,45)=1:T(18,47)=10:T(18,48)=5:T(18,49)=5
151 T(18,51)=1:T(18,52)=1:T(18,53)=1:T(18,55)=2:T(18,56)=2
152 T(19,20)=2
153 T(19,22)=5:T(19,24)=4:T(19,25)=1:T(19,26)=2:T(19,27)=5:T(19,31)=1:T(19,33)=5:T(19,34)=5:T(19,35)=10:T(19,39)=2
154 T(19,40)=1:T(19,42)=2:T(19,44)=1:T(19,45)=1:T(19,47)=5:T(19,49)=6:T(19,50)=1:T(19,51)=2:T(19,52)=2:T(19,53)=2
155 T(19,54)=10:T(19,55)=5:T(19,56)=1
157 T(20,21)=1:T(20,22)=2:T(20,26)=10:T(20,27)=10:T(20,29)=10:T(20,30)=5:T(20,32)=10:T(20,34)=5:T(20,35)=5
158 T(20,36)=2:T(20,37)=4:T(20,39)=1:T(20,40)=2:T(20,41)=4:T(20,45)=4:T(20,47)=5:T(20,48)=5:T(20,50)=5
159 T(20,52)=5:T(20,53)=5:T(20,55)=1
160 T(21,23)=2:T(21,24)=3:T(21,25)=10:T(21,26)=5:T(21,28)=5:T(21,30)=1:T(21,31)=5:T(21,34)=1:T(21,36)=2
163 T(21,37)=5:T(21,42)=1:T(21,44)=1:T(21,45)=3:T(21,46)=5:T(21,49)=1:T(21,51)=2:T(21,53)=4:T(21,54)=3
164 T(21,55)=2:T(21,56)=5
167 T(22,23)=10:T(22,24)=2:T(22,25)=4:T(22,27)=5:T(22,28)=5:T(22,29)=2:T(22,30)=5:T(22,31)=5
168 T(22,32)=5:T(22,33)=5:T(22,34)=5:T(22,38)=4:T(22,41)=5:T(22,43)=5:T(22,45)=10:T(22,49)=5
169 T(22,50)=5:T(22,51)=1:T(22,52)=10:T(22,53)=10:T(22,55)=2:T(22,56)=2
171 T(23,24)=10:T(23,25)=2:T(23,26)=5:T(23,27)=1:T(23,28)=6:T(23,29)=10:T(23,30)=10
172 T(23,32)=1:T(23,33)=5:T(23,34)=2:T(23,35)=5:T(23,37)=2:T(23,38)=10:T(23,40)=5
173 T(23,41)=1:T(23,42)=2:T(23,45)=2:T(23,47)=1:T(23,48)=5:T(23,50)=1:T(23,51)=10
174 T(23,52)=5:T(23,54)=1:T(23,55)=4:T(23,56)=2
175 T(24,25)=5:T(24,26)=10:T(24,27)=2:T(24,28)=10:T(24,29)=2:T(24,30)=2
176 T(24,31)=1:T(24,33)=5:T(24,36)=3:T(24,38)=5:T(24,42)=2:T(24,43)=2
177 T(24,44)=2:T(24,45)=2:T(24,46)=2:T(24,48)=2:T(24,49)=1:T(24,50)=10
178 T(24,52)=2:T(24,53)=5:T(24,54)=10:T(24,55)=10:T(24,56)=5
179 T(25,29)=1:T(25,31)=5:T(25,32)=4:T(25,33)=2:T(25,34)=5
180 T(25,36)=2:T(25,37)=2:T(25,38)=2:T(25,39)=2:T(25,42)=5
181 T(25,44)=5:T(25,45)=5:T(25,46)=5:T(25,48)=2:T(25,50)=5
182 T(25,52)=3:T(25,53)=1:T(25,54)=10:T(25,56)=1
183 T(26,27)=5:T(26,28)=5:T(26,29)=5:T(26,30)=1
184 T(26,32)=1:T(26,33)=2:T(26,34)=4:T(26,36)=2
185 T(26,37)=2:T(26,38)=2:T(26,39)=5:T(26,41)=2
186 T(26,43)=10:T(26,46)=5:T(26,50)=2:T(26,51)=2:T(26,52)=1:T(26,53)=3:T(26,54)=2:T(26,55)=2:T(26,56)=2
187 T(27,29)=3:T(27,30)=1:T(27,31)=1
188 T(27,32)=5:T(27,33)=2:T(27,34)=1
189 T(27,36)=5:T(27,37)=5:T(27,39)=6
190 T(27,41)=6:T(27,43)=5:T(27,44)=5:T(27,45)=10:T(27,46)=1:T(27,47)=6:T(27,49)=10:T(27,50)=2:T(27,52)=5:T(27,53)=10:T(27,55)=2
191 T(28,29)=5:T(28,30)=5
192 T(28,32)=10:T(28,34)=1:T(28,36)=2:T(28,37)=5:T(28,40)=6:T(28,41)=5:T(28,42)=1:T(28,43)=2:T(28,44)=5:T(28,46)=1:T(28,47)=10
193 T(28,49)=5:T(28,50)=5:T(28,55)=2:T(28,56)=5
195 T(29,30)=10
196 T(29,33)=10:T(29,35)=10:T(29,36)=10:T(29,37)=10:T(29,38)=5:T(29,39)=3:T(29,41)=4:T(29,42)=1:T(29,43)=3:T(29,44)=10:T(29,47)=10
197 T(29,48)=5:T(29,49)=1:T(29,50)=1:T(29,51)=5:T(29,52)=5:T(29,53)=3:T(29,54)=2:T(29,55)=3:T(29,56)=1
198 T(30,32)=10:T(30,33)=5:T(30,34)=5:T(30,36)=2:T(30,37)=4:T(30,39)=1:T(30,42)=10:T(30,49)=6:T(30,51)=2:T(30,52)=3:T(30,54)=1:T(30,55)=1:T(30,56)=5
199 T(31,32)=1:T(31,33)=2:T(31,34)=3:T(31,35)=2:T(31,36)=5:T(31,37)=5:T(31,40)=2:T(31,41)=2:T(31,42)=5:T(31,43)=10:T(31,44)=10:T(31,45)=10:T(31,47)=5:T(31,50)=3:T(31,53)=1:T(31,54)=1
200 T(32,33)=4:T(32,34)=2:T(32,35)=5:T(32,36)=5:T(32,38)=2:T(32,39)=2:T(32,42)=2:T(32,43)=2:T(32,44)=2:T(32,45)=1:T(32,46)=5:T(32,48)=5:T(32,50)=5:T(32,51)=1:T(32,53)=4:T(32,54)=1:T(32,55)=5
201 T(33,35)=1:T(33,36)=1:T(33,37)=1:T(33,38)=5:T(33,39)=2:T(33,40)=2:T(33,42)=5:T(33,43)=10:T(33,46)=2:T(33,47)=5:T(33,48)=6:T(33,49)=5:T(33,50)=5:T(33,51)=1:T(33,52)=1:T(33,53)=5:T(33,54)=10:T(33,55)=1:T(33,56)=2
202 T(34,35)=5:T(34,37)=10:T(34,39)=5:T(34,41)=5:T(34,42)=3:T(34,43)=2:T(34,44)=3:T(34,46)=10:T(34,47)=5:T(34,48)=10:T(34,50)=6:T(34,51)=2:T(34,53)=6:T(34,54)=1:T(34,55)=4
203 T(35,36)=10:T(35,38)=2:T(35,40)=5:T(35,42)=1:T(35,43)=4:T(35,44)=4:T(35,45)=6:T(35,47)=5:T(35,48)=2:T(35,51)=1:T(35,52)=2:T(35,53)=1:T(35,54)=1:T(35,55)=5:T(35,56)=4
204 T(36,37)=1:T(36,38)=5:T(36,41)=1:T(36,42)=3:T(36,43)=2:T(36,44)=5:T(36,45)=4:T(36,47)=2:T(36,49)=1:T(36,50)=1:T(36,51)=10:T(36,52)=1:T(36,53)=10:T(36,54)=5:T(36,56)=5
205 T(37,38)=5:T(37,39)=3:T(37,42)=3:T(37,43)=1:T(37,45)=5:T(37,47)=5:T(37,50)=2:T(37,51)=5:T(37,52)=5:T(37,53)=5:T(37,54)=2:T(37,55)=2:T(37,56)=1
206 T(38,39)=2:T(38,44)=1:T(38,45)=4:T(38,47)=1:T(38,50)=3:T(38,51)=1:T(38,53)=10:T(38,54)=3:T(38,55)=5:T(38,56)=1
207 T(39,40)=5:T(39,41)=3:T(39,45)=2:T(39,46)=2:T(39,47)=2:T(39,48)=5:T(39,49)=2:T(39,50)=2:T(39,52)=4:T(39,55)=5:T(39,56)=5
208 T(40,41)=5:T(40,43)=5:T(40,44)=5:T(40,45)=2:T(40,46)=2:T(40,48)=2:T(40,49)=5:T(40,50)=2:T(40,51)=2:T(40,52)=10:T(40,53)=5:T(40,54)=2
209 T(41,42)=5:T(41,43)=2:T(41,44)=5:T(41,45)=2:T(41,46)=5:T(41,47)=5:T(41,48)=5:T(41,49)=2:T(41,50)=5:T(41,51)=10:T(41,54)=3:T(41,55)=1
210 T(42,44)=5:T(42,47)=2:T(42,48)=2:T(42,49)=6:T(42,50)=2:T(42,51)=2:T(42,52)=2:T(42,53)=5:T(42,54)=2:T(42,55)=5:T(42,56)=10
211 T(43,45)=10:T(43,46)=5:T(43,47)=4:T(43,49)=1:T(43,50)=2:T(43,51)=1:T(43,54)=2:T(43,55)=10:T(43,56)=3
212 T(44,46)=5:T(44,47)=2:T(44,48)=1:T(44,52)=10:T(44,55)=2:T(44,56)=2
213 T(45,46)=10:T(45,48)=2:T(45,50)=3:T(45,51)=1:T(45,53)=5:T(45,54)=3: T(45,56)=10
214 T(46,47)=5:T(46,48)=2:T(46,49)=1:T(46,50)=5:T(46,51)=6:T(46,54)=5:T(46,55)=1:T(46,56)=2
215 T(47,48)=2:T(47,49)=3:T(47,50)=2:T(47,52)=2:T(47,55)=1:T(47,56)=1
216 T(48,50)=2:T(48,51)=2:T(48,52)=5:T(48,54)=5
217 T(49,51)=5:T(49,53)=4:T(49,56)=5
218 T(50,51)=6:T(50,52)=5:T(50,53)=6:T(50,55)=5:T(50,56)=3
219 T(51,52)=5:T(51,53)=2:T(51,54)=4:T(51,55)=2:T(51,56)=2:T(52,53)=2:T(52,55)=5:T(52,56)=5:T(53,54)=1:T(53,55)=1:T(54,55)=1:T(54,56)=5:T(55,56)=5
220 FOR JJJJ=-32000 TO 32000
221 RANDOMIZE JJJJ
222 M=-1D+17
223 FOR I=1 TO 58
224 A(I)=1+FIX(RND*6)
225 NEXT I
226 IMAR=10+FIX(RND*2000)
228 FOR I=1 TO IMAR
229 FOR KK=1 TO 58
231 X(KK)=A(KK)
232 NEXT KK
242 IJL=1+FIX(RND*58):IJM=1+FIX(RND*58):IJN=1+FIX(RND*58)
253 IF RND<.7 THEN X(IJL)=1+FIX(RND*6) ELSE IF RND<.05 THEN X(IJL)=A(IJL) ELSE GOTO 264
255 GOTO 351
264 X(IJM)=A(IJN):X(IJN)=A(IJM)
301 IF RND<.5 GOTO 351
302 IJM=1+FIX(RND*58):IJN=1+FIX(RND*58)
304 X(IJM)=A(IJN):X(IJN)=A(IJM)
351 FOR K=1 TO 58
361 FOR J=K+1 TO 58
363 IF X(K)=X(J) THEN TZ(K,J)=T(K,J) ELSE TZ(K,J)=0
366 NEXT J
399 NEXT K
1590 SUMTZ=0
1591 FOR K=1 TO 58
1594 FOR J=K+1 TO 58
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 58
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 228
1670 NEXT I
1890 IF M>-240 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)
1918 PRINT A(31),A(32),A(33),A(34),A(35)
1919 PRINT A(36),A(37),A(38),A(39),A(40)
1920 PRINT A(41),A(42),A(43),A(44),A(45)
1921 PRINT A(46),A(47),A(48),A(49),A(50)
1922 PRINT A(51),A(52),A(53),A(54),A(55)
1927 PRINT A(56),M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the best candidate solutions produced during the first 4.1 hours of running are presented below. What immediately follows is a manual copy from the computer screen.
44234
15215
16121
12253
24346
65526
51224
63546
14332
56533
41136
5 -218 -31457
15345
25461
11622
15423
43215
64412
16415
33423
54226
36362
46565
3 -213 -31397
213 may be or may not be optimal. Interpreted in accordance with line 1912 through line 1927, the candidate solutions presented above were produced during the first 4.1 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).
Skorin-Kapov, J., "Tabu Search Applied to the Quadratic Assignment Problem," ORSA Journal on Computing 2, 33-45 (1990).
Vredeveld, T., and J. K. Lenstra, "On Local Search for the Generalized Graph Coloring Problem,"Operations Research Letters 31, 28-34 (2003).
