A Computer Program for Scheduling 107 Activities among Eight Facilities

Jsun Yui Wong

The computer program listed below is concerned with the scheduling problem of Carlson and Nemhauser (1966). As shown in line 101 through line 263 for a case of scheduling 107 activities among eight 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 106 and activity 107 are 1, 4, 1, ..., and 9, respectively. These data were not selected randomly or scientifically; most of the numbers in line 101 below were obtained from Simmons (1969).

0 DEFINT A-Z
4 DIM X(107),A(107)
7 DIM TM(107,107),HR(107,107)
21 FOR IW=1 TO 106
23 FOR JW=IW+1 TO 107
26 READ HR(IW,JW)
28 NEXT JW
29 NEXT IW
101 DATA 1,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,1
102 DATA 2,3,1,6,6,3,0,1,2,4,4,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,4,3,4
103 DATA 1,9,3,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,5,6,3,4,2,7,4,2,3,4,3,2
104 DATA 4,3,1,7,7,1,0,4,2,3,7,4,3,0,6,3,2,2,3,2,3,5,0,6,5,3,5,4,2,9,2,7,9,3,7
105 DATA 3,4,5,7,3,5,0,1,2,5,5,2,3,0,6,3,2,2,3,4,0,4,0,2,6,3,5,2,6,8,2,3,4,3,2
106 DATA 9,3,1,7,3,4,0,1,2,5,5,4,3,0,6,3,2,2,8,4,0,1,0,6,2,3,5,2,7,1,2,7,8,3,2
107 DATA 7,4,1,0,3,5,0,1,2,4,5,4,3,0,6,3,2,2,3,4,1,1,0,6,5,5,8,2,7,9,2,7,8,3,6
108 DATA 2,2,3,7,3,5,3,3,2,5,5,4,3,3,6,3,2,2,3,4,0,3,0,2,6,3,5,2,3,8,2,7,8,3,4
109 DATA 5,4,1,6,5,7,0,1,2,5,5,4,3,0,6,3,2,2,3,4,2,1,2,6,6,3,5,2,7,8,2,7,2,3,5
110 DATA 2,4,1,7,3,5,1,1,2,4,2,4,3,0,5,3,2,2,3,4,0,1,2,6,6,4,5,9,7,9,2,7,9,3,2
111 DATA 7,3,4,4,3,5,5,1,2,5,5,4,3,0,6,3,2,2,3,4,5,1,0,6,6,3,5,2,4,4,2,4,4,3,1
112 DATA 2,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,2
113 DATA 3,4,6,7,3,5,1,1,2,5,5,4,3,4,6,3,2,2,3,4,3,3,1,6,6,3,5,2,7,9,2,7,9,3,8
114 DATA 4,4,1,7,4,5,0,1,2,5,5,4,3,1,6,3,2,2,3,4,0,1,1,4,6,4,6,2,7,9,2,7,9,3,1
115 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,2
116 DATA 2,5,1,3,6,2,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,6,2,7,9,3,2
117 DATA 9,3,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,5,4,5,2,7,2,2,4,4,3,7
118 DATA 3,4,1,7,4,5,3,1,2,5,3,4,3,0,6,3,2,2,3,4,5,1,4,6,4,3,5,2,3,4,2,7,4,3,1
119 DATA 6,4,1,7,3,5,0,1,2,5,5,4,3,6,6,3,2,2,3,4,0,1,6,6,6,3,5,2,7,0,2,7,9,3,7
120 DATA 4,2,1,2,7,0,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,3,6,6,3,2,2,3,2,2,4,4,3
121 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,3
122 DATA 3,4,2,7,3,0,0,1,2,4,6,4,3,0,6,3,2,2,3,4,0,2,0,5,6,3,5,2,7,2,2,7,2,3,2
123 DATA 8,4,1,7,3,5,0,1,2,4,7,4,3,0,6,3,2,2,3,4,0,1,0,7,6,3,5,2,7,0,2,7,9,3,8
124 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,7,3,2,2,3,4,0,1,0,4,2,3,5,2,7,8,2,7,0,3,1
125 DATA 9,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,3,2,3,4,0,1,0,6,2,3,5,2,7,9,2,7,0,3,7
126 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,7,3,2,2,3,4,0,1,0,6,6,3,5,2,7,8,2,7,6,3,2
127 DATA 1,3,1,6,3,5,0,1,2,5,6,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,3
128 DATA 7,4,1,7,7,8,0,1,2,5,7,4,3,0,6,3,2,2,3,4,0,1,0,7,6,3,5,2,7,3,2,7,9,3,1
129 DATA 5,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,2,6,3,5,2,7,9,2,7,9,3,3
130 DATA 3,4,2,8,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,3,6,8,3,5,2,7,8,2,8,0,3,4
131 DATA 6,4,1,7,8,9,0,1,2,5,4,4,3,0,6,3,2,2,3,4,0,1,0,3,6,3,5,2,7,9,2,7,8,3,5
132 DATA 3,4,1,7,3,5,0,1,2,1,2,4,3,0,6,3,2,2,3,4,0,1,0,6,4,3,5,2,7,9,2,7,9,3,9
133 DATA 5,4,1,7,3,5,0,1,2,5,5,4,3,1,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,2,3,3
134 DATA 1,4,1,7,5,2,3,1,2,5,5,4,3,1,6,3,2,2,3,4,2,1,0,6,6,3,5,2,7,9,2,7,9,3,1
135 DATA 1,4,1,7,3,5,5,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,6,6,6,3,5,2,2,6,2,7,9,3,1
136 DATA 2,4,1,7,3,5,2,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,4,9,2,7,6,3,1
137 DATA 7,4,4,5,6,5,0,1,2,5,5,4,3,2,6,3,2,2,3,4,0,1,5,6,7,3,5,2,7,1,2,4,6,3,2
138 DATA 5,4,1,7,3,5,0,5,2,5,5,4,3,0,6,3,2,2,3,4,0,4,0,6,6,3,5,2,7,1,2,7,4,3,2
139 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,3,6,6,3,5,2,7,2,2,7,9,3,2
140 DATA 4,4,1,7,8,5,3,1,2,5,5,4,3,0,5,3,2,2,3,4,0,1,0,6,5,3,5,2,7,9,2,7,2,3,2
141 DATA 2,4,1,7,4,5,0,1,2,5,2,4,3,0,6,3,2,2,3,2,0,1,0,5,6,3,5,2,4,9,2,7,4,3,4
142 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,5,0,1,0,4,6,3,5,2,7,3,2,7,4,3,1
143 DATA 1,4,1,4,3,4,4,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,2
144 DATA 6,4,5,7,3,5,0,1,2,3,5,4,3,3,6,3,2,2,3,4,0,1,0,4,7,3,5,2,7,3,2,7,5,3,3
145 DATA 3,4,1,7,3,5,0,1,2,3,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,7,3,2,7,4,3,2
146 DATA 5,4,1,7,4,6,0,1,2,5,5,4,3,0,5,3,2,2,3,4,0,1,0,5,6,3,5,2,7,9,2,7,9,3,4
147 DATA 3,4,1,7,3,5,0,1,2,5,3,4,3,0,6,3,2,2,3,4,0,1,0,3,6,3,5,2,7,9,2,7,3,3,1
148 DATA 6,4,1,7,3,5,6,1,2,5,5,4,3,0,6,3,2,2,3,4,6,1,0,5,5,3,3,2,7,3,2,7,9,3,3
149 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,7,6,6,3,5,2,7,7,2,7,2,3,2
150 DATA 1,4,1,7,3,5,2,1,2,5,5,4,3,2,6,3,2,2,3,4,2,1,1,6,6,3,5,2,7,1,2,7,9,3,1
151 DATA 3,4,1,7,3,5,3,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,7,9,2,7,2,3,2
152 DATA 7,4,1,7,3,5,7,1,2,5,5,4,3,0,6,3,2,2,3,4,7,1,0,6,6,3,5,2,0,0,2,7,9,3,1
153 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,1
154 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,0
155 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,7,9,2,7,3,3,1
156 DATA 1,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,3
157 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,1,1,3,5,2,7,9,2,7,9,3,2
158 DATA 1,4,1,7,3,5,0,1,2,5,0,4,3,0,6,3,2,2,3,1,0,1,0,6,6,3,5,2,7,9,2,7,9,3,4
159 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,1,2,7,9,3,2
160 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,0,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,7
161 DATA 4,4,1,5,3,5,0,1,2,5,5,4,3,0,5,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,1,3,5
162 DATA 9,4,1,3,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,2,2,7,9,3,8
163 DATA 7,4,1,7,3,5,0,1,2,0,5,4,3,0,0,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,4
164 DATA 3,4,1,7,3,0,0,1,2,0,5,4,3,0,6,3,2,2,3,4,0,1,0,7,6,3,5,2,7,9,2,7,9,3,6
165 DATA 6,2,5,3,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,2,0,2,6,3,5,2,7,2,2,7,2,3,4
166 DATA 3,4,1,7,3,5,0,1,2,3,5,4,3,0,6,3,3,2,3,4,0,1,0,6,6,3,5,2,7,3,2,7,9,3,7
167 DATA 1,2,1,7,3,5,0,1,2,5,5,4,3,0,5,3,2,2,3,4,0,1,0,4,6,3,5,2,7,9,2,7,4,3,3
168 DATA 3,4,1,7,3,5,0,3,2,5,3,4,3,0,6,3,2,2,3,4,0,2,0,6,6,3,5,2,7,3,2,7,9,3,2
169 DATA 3,4,1,7,3,5,0,1,2,5,0,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,3
170 DATA 5,0,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,3
171 DATA 5,4,3,7,5,5,2,5,2,5,5,4,3,0,6,3,2,2,3,4,3,4,4,6,3,3,5,2,7,9,2,7,6,3,4
172 DATA 3,4,1,7,3,5,7,1,2,5,5,4,3,3,6,3,2,2,3,4,0,1,0,1,2,3,5,2,7,9,2,7,5,3,3
173 DATA 5,4,1,7,2,4,0,1,2,5,5,4,3,0,2,3,2,2,3,4,0,1,0,6,6,3,5,2,7,5,2,7,9,3,9
174 DATA 3,4,1,0,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,0,6,3,5,2,7,9,2,7,0,3,4
175 DATA 9,4,2,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,2,2,3,3,5,2,7,3,2,7,9,3,7
176 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,2,2,3,5,2,7,3,2,7,9,3,4
177 DATA 4,4,4,7,3,5,0,1,2,2,3,4,3,0,6,3,2,2,3,4,0,5,0,6,1,3,5,2,7,9,2,7,9,3,6
178 DATA 3,4,1,7,3,5,3,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,7,9,2,7,3,3,2
179 DATA 3,4,3,7,3,5,0,1,2,5,5,4,3,2,6,3,2,2,3,4,2,1,0,6,6,3,3,2,7,1,2,7,9,3,4
180 DATA 2,4,1,7,3,5,6,1,2,5,5,4,3,3,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,0,3,2
181 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,1,2,3,5,2,7,3,2,7,9,3,4
182 DATA 6,5,2,2,3,5,2,1,2,5,5,4,3,0,6,3,2,2,3,4,0,3,3,3,6,3,5,2,7,3,2,7,2,3,5
183 DATA 2,4,1,7,3,2,2,1,2,5,5,4,3,0,4,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,6,3,3
184 DATA 3,4,1,7,3,5,0,1,2,4,5,4,3,0,6,3,2,2,3,4,7,1,0,6,4,3,5,2,7,9,2,7,9,3,3
185 DATA 4,4,1,7,3,5,1,1,2,5,5,4,3,3,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,3,3,6
186 DATA 2,8,2,7,3,5,1,1,2,5,5,4,3,3,2,3,2,2,3,4,9,1,0,6,6,3,5,8,7,9,2,2,3,3,9
187 DATA 6,4,1,7,4,5,1,1,2,5,4,4,3,3,6,3,2,2,3,4,6,1,0,6,6,3,5,2,7,6,2,7,3,3,4
188 DATA 7,4,1,7,3,5,6,1,2,5,7,4,6,3,6,3,2,2,3,4,0,4,0,6,2,3,5,2,7,9,2,7,4,3,2
189 DATA 2,9,1,4,3,2,1,1,2,5,5,4,3,3,6,3,5,2,3,4,0,1,0,2,6,3,9,2,7,9,2,4,3,3,4
190 DATA 7,4,1,7,3,2,1,1,2,5,3,4,3,3,6,3,7,2,3,4,0,3,0,6,6,3,5,2,7,7,2,7,3,3,3
191 DATA 4,7,1,1,3,5,1,1,2,5,1,4,7,3,6,3,2,2,3,4,0,1,0,1,6,3,5,2,7,1,2,7,3,3,1
192 DATA 5,4,9,7,3,5,1,1,2,9,5,4,5,3,9,3,2,2,3,4,0,1,0,5,6,3,5,2,7,9,2,7,3,3,9
193 DATA 9,9,1,8,3,5,1,1,2,5,8,4,9,3,6,3,2,2,3,4,9,1,0,6,6,8,5,5,7,9,2,7,3,5,8
194 DATA 8,4,1,7,2,5,8,1,2,5,5,4,3,2,6,3,8,2,3,4,0,1,0,6,8,3,5,2,7,9,2,7,3,3,2
195 DATA 2,4,1,7,3,5,1,1,5,2,5,4,3,5,6,3,2,3,5,4,0,1,0,3,6,3,5,2,7,9,2,7,3,5,3
196 DATA 9,6,1,7,3,5,1,7,2,5,5,4,3,7,7,3,2,2,3,9,0,7,6,9,6,3,6,2,7,9,2,7,6,3,9
197 DATA 7,4,1,7,3,5,8,3,2,5,7,4,3,8,6,3,2,2,3,4,0,1,0,6,8,3,5,2,7,9,2,7,7,3,8
198 DATA 6,4,2,7,3,5,1,2,2,5,5,4,6,3,2,3,2,4,3,4,0,1,0,7,6,3,5,2,4,9,2,7,2,3,7
199 DATA 5,7,1,6,3,5,7,1,2,5,5,4,3,3,6,3,7,2,3,4,9,1,9,6,5,3,5,6,7,9,6,6,9,3,5
200 DATA 3,8,1,7,3,5,1,8,2,3,5,4,3,3,6,3,2,2,3,4,0,3,0,6,6,3,5,8,7,9,2,7,3,3,8
201 DATA 6,4,1,7,3,5,1,1,2,5,6,4,3,3,6,3,2,2,3,4,6,1,6,6,6,3,5,2,7,6,2,7,3,6,7
202 DATA 4,7,1,7,3,5,1,7,2,7,5,4,3,3,6,3,7,2,3,4,0,1,0,7,6,3,5,2,6,9,2,7,3,3,3
203 DATA 4,6,1,7,3,5,1,1,2,5,6,4,6,3,6,3,2,6,3,6,6,1,0,6,6,3,6,6,7,9,2,7,6,3,1
204 DATA 6,4,1,7,3,5,1,1,2,6,5,4,3,6,6,3,2,2,6,4,0,2,0,6,6,3,6,2,7,6,3,7,3,6,2
205 DATA 5,5,1,4,4,4,5,4,2,5,5,4,3,3,6,4,2,2,3,4,5,1,0,6,4,5,5,2,7,5,2,7,3,4,5
206 DATA 5,4,1,7,3,5,1,1,2,2,7,7,3,3,2,3,2,7,3,4,0,1,0,7,6,3,5,2,7,9,2,7,7,3,1
207 DATA 4,3,4,7,4,5,1,1,2,3,5,4,4,3,6,3,2,2,4,3,3,1,0,6,6,3,5,2,7,3,2,7,3,4,6
208 DATA 6,5,5,7,3,5,6,1,2,5,5,4,3,3,4,3,2,2,3,4,0,5,0,4,6,3,5,2,7,9,2,7,5,3,4
209 DATA 8,8,1,7,3,5,1,3,4,5,5,4,3,3,6,3,1,2,3,4,1,1,4,8,6,3,5,2,7,8,2,7,3,3,0
210 DATA 9,4,1,6,3,6,1,1,2,5,9,4,3,3,6,9,9,6,3,4,0,1,0,6,6,2,5,2,7,9,2,7,3,2,2
211 DATA 6,4,6,2,3,5,2,1,2,5,5,6,3,3,6,3,2,7,3,4,6,1,0,6,6,3,7,2,7,9,2,7,7,3,7
212 DATA 5,4,5,7,3,5,1,4,5,2,5,4,2,3,2,3,2,2,2,2,0,3,2,6,5,3,5,2,8,9,2,7,7,3,5
213 DATA 0,5,1,7,3,5,5,1,2,5,6,4,3,5,6,3,2,2,3,4,0,1,6,5,6,3,5,2,7,9,2,7,6,3,5
214 DATA 3,4,1,4,2,0,1,1,2,2,0,4,3,3,6,3,2,2,2,4,0,1,0,6,6,2,2,2,7,9,2,7,6,3,0
215 DATA 5,4,1,4,2,0,1,1,5,2,0,4,5,3,6,3,2,2,2,4,0,1,0,5,6,2,5,2,7,9,2,7,6,3,9
216 DATA 7,4,1,4,2,0,1,7,2,2,0,4,3,3,6,3,2,7,2,4,0,1,0,7,6,2,2,2,7,9,2,7,6,3,2
217 DATA 2,3,5,4,2,0,1,3,2,3,0,4,3,3,2,3,2,3,2,4,0,1,0,6,2,2,3,2,7,9,2,7,6,3,3
218 DATA 3,4,1,4,2,0,5,1,2,2,0,5,3,3,6,3,2,2,5,5,0,5,0,6,6,2,2,6,9,9,2,7,6,3,4
219 DATA 7,4,1,3,4,0,1,1,2,2,0,4,3,4,6,3,2,2,2,4,0,1,0,6,6,2,2,2,7,9,2,3,6,3,3
220 DATA 8,4,1,4,2,0,1,1,2,2,0,4,3,3,6,8,2,2,2,4,8,1,0,8,6,2,2,2,7,4,2,7,4,4,2
221 DATA 3,2,4,4,2,0,4,1,8,4,0,4,3,3,8,3,4,2,2,4,0,4,0,6,6,6,6,2,7,9,2,7,6,3,0
222 DATA 8,4,1,4,2,0,1,1,2,2,0,4,3,3,6,3,2,2,2,4,0,1,0,6,8,2,2,9,9,9,2,7,6,3,0
223 DATA 7,4,1,7,8,0,1,1,2,2,0,4,8,7,6,3,2,2,2,4,0,1,0,7,6,2,2,2,7,9,2,7,6,3,8
224 DATA 5,3,1,4,2,3,1,1,2,2,0,4,3,3,6,3,2,5,2,5,0,1,2,6,6,2,2,2,7,9,2,7,5,3,4
225 DATA 3,4,5,4,2,0,1,1,4,2,0,4,3,3,3,5,2,2,2,4,0,5,0,6,6,2,5,2,7,9,2,5,6,3,5
226 DATA 7,4,1,4,2,0,1,7,2,2,7,7,3,3,6,3,7,2,7,4,7,1,0,6,7,7,2,2,8,8,2,7,6,3,4
227 DATA 7,2,1,8,2,0,1,1,2,7,0,4,3,8,6,3,2,7,2,4,0,1,3,3,6,2,2,2,7,9,2,7,6,3,3
228 DATA 2,2,1,3,2,0,1,1,2,2,0,4,3,3,2,3,2,2,2,2,0,1,0,6,2,2,2,2,7,2,2,5,6,3,4
229 DATA 6,4,1,6,2,0,1,1,2,2,6,4,3,3,8,3,2,2,2,4,0,1,0,6,6,2,3,3,7,3,2,7,6,3,4
230 DATA 8,4,8,4,8,0,1,1,2,2,0,4,3,3,6,3,2,2,2,4,8,1,0,6,6,2,2,2,6,9,2,7,7,3,2
231 DATA 5,4,2,4,2,0,5,1,2,2,2,5,3,3,6,3,2,5,2,4,0,1,0,6,6,2,5,2,7,9,2,7,6,3,2
232 DATA 2,4,5,4,2,0,1,5,2,2,2,4,3,3,6,3,2,2,2,4,7,1,0,9,6,2,2,2,7,9,2,7,9,3,5
233 DATA 7,4,4,4,2,7,5,1,2,2,0,3,3,3,6,3,5,2,2,5,0,1,0,6,6,2,3,2,7,9,2,5,6,3,4
234 DATA 9,8,1,4,2,0,1,3,2,2,0,4,3,3,6,3,8,2,2,4,0,1,0,8,6,2,2,2,7,9,2,7,6,3,7
235 DATA 8,4,7,4,2,0,1,1,2,2,0,4,3,3,6,3,2,2,8,4,8,1,0,6,6,2,8,2,4,9,2,7,6,3,8
236 DATA 6,4,7,4,2,0,1,6,2,2,0,4,3,3,7,3,7,2,2,4,0,1,0,7,6,2,2,2,7,9,2,7,6,3,1
237 DATA 4,5,1,4,2,0,5,1,2,2,4,4,3,3,6,3,2,4,2,4,0,1,0,4,6,2,2,2,7,9,2,4,6,3,5
238 DATA 5,3,4,4,2,0,1,3,2,4,0,4,3,3,6,3,2,3,2,4,0,9,0,4,6,2,4,2,7,9,2,7,6,3,9
239 DATA 4,6,1,4,2,0,1,4,2,4,0,4,6,3,6,3,2,4,5,4,0,1,0,6,6,2,6,2,7,9,2,7,5,3,6
240 DATA 5,4,6,5,2,0,1,6,2,4,0,4,3,4,6,3,2,6,2,4,0,1,0,7,6,2,2,2,7,9,2,7,6,3,0
241 DATA 1,4,1,3,2,0,1,7,2,3,0,4,1,3,6,3,2,7,2,4,0,1,0,6,1,3,7,2,7,9,2,3,6,7,4
242 DATA 3,4,1,4,2,0,4,7,3,2,3,4,7,3,6,3,3,7,2,4,2,2,4,6,7,2,7,2,3,9,2,1,6,7,5
243 DATA 7,8,1,4,2,0,1,7,2,8,0,4,7,5,6,3,2,7,2,4,0,1,0,6,5,2,0,2,7,9,2,3,6,7,0
244 DATA 4,5,8,4,2,0,1,7,2,2,0,8,5,3,6,3,2,7,2,7,0,1,5,6,7,2,7,2,7,9,5,7,6,7,8
245 DATA 5,3,1,4,2,0,1,7,2,2,3,4,7,3,6,5,5,7,2,4,5,1,0,4,7,2,7,2,7,5,2,7,5,7,8
246 DATA 9,4,1,2,6,3,1,7,9,2,0,4,7,3,6,3,2,9,2,4,0,1,0,6,7,2,3,2,7,9,2,9,6,9,3
247 DATA 2,4,1,4,2,0,3,6,2,3,0,4,3,3,6,3,2,7,6,3,0,3,0,6,7,2,7,2,7,9,3,7,6,7,5
248 DATA 7,9,4,4,2,0,1,4,8,2,0,4,7,3,4,8,2,7,2,4,4,1,8,8,4,2,7,2,4,9,2,7,4,8,9
249 DATA 4,7,3,5,2,0,1,7,2,7,0,7,7,5,6,3,2,5,5,4,0,1,0,6,7,7,7,7,7,9,2,6,6,7,6
250 DATA 7,4,1,4,6,7,1,7,2,2,8,6,7,3,6,5,2,7,2,4,0,3,0,5,7,2,7,2,7,5,2,7,6,3,7
251 DATA 3,4,3,4,2,3,1,7,2,2,3,2,7,3,6,3,2,7,6,6,0,1,3,4,7,2,4,3,7,9,4,7,6,7,3
252 DATA 7,3,1,6,2,0,4,7,2,2,0,8,7,3,6,3,2,8,2,4,4,1,0,4,4,8,7,2,4,9,8,4,6,5,4
253 DATA 7,4,2,4,2,0,2,7,2,2,2,4,7,3,2,3,5,7,2,4,5,5,0,6,5,2,5,2,5,5,2,7,5,5,2
254 DATA 3,4,1,4,2,3,1,7,2,2,0,4,3,4,4,3,2,7,2,6,0,6,0,6,7,6,7,6,7,9,6,7,3,7,3
255 DATA 2,4,1,4,2,0,1,6,4,5,0,4,7,8,6,3,2,6,8,4,8,1,6,6,5,2,5,2,7,6,2,5,4,7,5
256 DATA 7,4,4,4,2,3,4,5,2,2,5,3,7,3,6,6,2,7,2,4,0,5,5,5,4,2,5,2,5,9,5,5,6,2,4
257 DATA 2,2,1,2,2,2,4,7,4,4,4,6,6,6,3,3,3,7,2,3,3,1,0,6,7,3,7,2,7,3,2,7,6,7,2
258 DATA 2,4,2,4,4,0,1,4,2,2,4,4,7,3,5,3,2,5,2,4,1,1,0,6,7,2,7,2,7,9,2,7,1,7,2
259 DATA 9,3,1,3,2,3,4,9,2,2,0,5,5,3,6,3,2,7,2,2,0,2,2,6,7,2,2,9,7,9,2,7,6,2,5
260 DATA 7,4,4,4,2,0,5,7,2,5,5,4,7,3,7,3,2,8,8,4,0,1,8,6,8,2,7,2,8,8,2,7,6,7,0
261 DATA 5,4,1,4,2,0,1,5,2,2,0,4,7,8,6,3,2,7,2,8,5,3,0,6,7,4,6,4,7,4,2,7,6,7,4
262 DATA 2,4,1,4,2,0,1,7,3,2,0,4,7,4,7,3,9,7,2,4,0,1,0,6,4,2,7,2,4,4,2,7,6,4,8
263 DATA 9
1065 FOR JJJJ=-32000 TO 32000
1074 RANDOMIZE JJJJ
1076 M=-32000
1085 FOR I=1 TO 107
1088 A(I)=FIX(RND*7)
1089 NEXT I
1126 IMAR=10+FIX(RND*2000)
1128 FOR I=1 TO IMAR
1129 FOR KK=1 TO 107
1131 X(KK)=A(KK)
1132 NEXT KK
1223 IJL=1+FIX(RND*107)
1234 X(IJL)=FIX(RND*8)
1533 FOR IX=1 TO 106
1534 FOR JX=IX+1 TO 107
1542 IF X(IX)=X(JX) THEN TM(IX,JX)=HR(IX,JX) ELSE TM(IX,JX)=0
1545 NEXT JX
1547 NEXT IX
1611 SUMTL=0
1612 FOR IR1=1 TO 106
1614 FOR IR2=IR1+1 TO 107
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 107
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 1128
1670 NEXT I
1890 IF M>-1330 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)
1923 PRINT A(56),A(57),A(58),A(59),A(60)
1924 PRINT A(61),A(62),A(63),A(64),A(65)
1925 PRINT A(66),A(67),A(68),A(69),A(70)
1926 PRINT A(71),A(72),A(73),A(74),A(75)
1927 PRINT A(76),A(77),A(78),A(79),A(80)
1928 PRINT A(81),A(82),A(83),A(84),A(85)
1929 PRINT A(86),A(87),A(88),A(89),A(90)
1930 PRINT A(91),A(92),A(93),A(94),A(95)
1931 PRINT A(96),A(97),A(98),A(99),A(100)
1932 PRINT A(101),A(102),A(103),A(104),A(105)
1937 PRINT A(106),A(107),M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, and the best candidate solutions produced during the first 20 hours of running are presented below. Only the candidate solution at JJJJ=-31926 is presented in full; each of the other candidate solutions below is briefly presented with its line
1937.

1 1 6 3 5
7 2 1 1 6
7 2 3 4 1
4 2 7 6 7
0 4 1 4 3
5 7 6 1 6
2 7 5 0 5
1 2 6 0 6
7 2 1 2 6
7 2 3 7 1
0 0 7 4 3
5 0 6 4 7
4 4 6 1 6
4 4 5 2 3
0 2 5 2 3
0 0 1 6 6
3 0 3 7 1
3 4 3 7 7
5 0 5 2 6
5 0 5 1 5
4 4 5 7 3
1 4 -1315 -31926

4 1 -1328 -31908

7 1 -1328 -31897

7 5 -1326 -31838

4 3 -1320 -31681

Interpreted in accordance with line 1912 through line 1937, these candidate solutions were produced during the first 20 hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter, which is not a compiler.

References

Carlson, R. C., and G. L. Nemhauser, "Scheduling to Minimize Interaction Cost," Operations Research 14, 52-58 (1966).

Microsoft Corp. BASIC. Second Edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C, Boca Raton, Florida 33432, 1981.

Simmons, D. M., "One-Dimensional Space Allocation: an Ordering Algorithm," Operations Research 17, 812-826 (1969).

A Computer Program for Scheduling 100 Activities among Seven Facilities

Jsun Yui Wong

The computer program listed below is concerned with the scheduling problem of Carlson and Nemhauser (1966). As shown in line 101 through line 242 for a case of scheduling 100 activities among seven 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 99 and activity 100 are
1, 4, 1, ..., and 9, respectively. These data were not selected randomly or scientifically.

0 DEFINT A-Z
4 DIM X(100),A(100)
7 DIM TM(100,100),HR(100,100)
21 FOR IW=1 TO 99
23 FOR JW=IW+1 TO 100
26 READ HR(IW,JW)
28 NEXT JW
29 NEXT IW
101 DATA 1,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,1
102 DATA 2,3,1,6,6,3,0,1,2,4,4,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,4,3,4
103 DATA 1,9,3,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,5,6,3,4,2,7,4,2,3,4,3,2
104 DATA 4,3,1,7,7,1,0,4,2,3,7,4,3,0,6,3,2,2,3,2,3,5,0,6,5,3,5,4,2,9,2,7,9,3,7
105 DATA 3,4,5,7,3,5,0,1,2,5,5,2,3,0,6,3,2,2,3,4,0,4,0,2,6,3,5,2,6,8,2,3,4,3,2
106 DATA 9,3,1,7,3,4,0,1,2,5,5,4,3,0,6,3,2,2,8,4,0,1,0,6,2,3,5,2,7,1,2,7,8,3,2
107 DATA 7,4,1,0,3,5,0,1,2,4,5,4,3,0,6,3,2,2,3,4,1,1,0,6,5,5,8,2,7,9,2,7,8,3,6
108 DATA 2,2,3,7,3,5,3,3,2,5,5,4,3,3,6,3,2,2,3,4,0,3,0,2,6,3,5,2,3,8,2,7,8,3,4
109 DATA 5,4,1,6,5,7,0,1,2,5,5,4,3,0,6,3,2,2,3,4,2,1,2,6,6,3,5,2,7,8,2,7,2,3,5
110 DATA 2,4,1,7,3,5,1,1,2,4,2,4,3,0,5,3,2,2,3,4,0,1,2,6,6,4,5,9,7,9,2,7,9,3,2
111 DATA 7,3,4,4,3,5,5,1,2,5,5,4,3,0,6,3,2,2,3,4,5,1,0,6,6,3,5,2,4,4,2,4,4,3,1
112 DATA 2,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,2
113 DATA 3,4,6,7,3,5,1,1,2,5,5,4,3,4,6,3,2,2,3,4,3,3,1,6,6,3,5,2,7,9,2,7,9,3,8
114 DATA 4,4,1,7,4,5,0,1,2,5,5,4,3,1,6,3,2,2,3,4,0,1,1,4,6,4,6,2,7,9,2,7,9,3,1
115 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,2
116 DATA 2,5,1,3,6,2,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,6,2,7,9,3,2
117 DATA 9,3,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,5,4,5,2,7,2,2,4,4,3,7
118 DATA 3,4,1,7,4,5,3,1,2,5,3,4,3,0,6,3,2,2,3,4,5,1,4,6,4,3,5,2,3,4,2,7,4,3,1
119 DATA 6,4,1,7,3,5,0,1,2,5,5,4,3,6,6,3,2,2,3,4,0,1,6,6,6,3,5,2,7,0,2,7,9,3,7
120 DATA 4,2,1,2,7,0,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,3,6,6,3,2,2,3,2,2,4,4,3
121 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,3
122 DATA 3,4,2,7,3,0,0,1,2,4,6,4,3,0,6,3,2,2,3,4,0,2,0,5,6,3,5,2,7,2,2,7,2,3,2
123 DATA 8,4,1,7,3,5,0,1,2,4,7,4,3,0,6,3,2,2,3,4,0,1,0,7,6,3,5,2,7,0,2,7,9,3,8
124 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,7,3,2,2,3,4,0,1,0,4,2,3,5,2,7,8,2,7,0,3,1
125 DATA 9,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,3,2,3,4,0,1,0,6,2,3,5,2,7,9,2,7,0,3,7
126 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,7,3,2,2,3,4,0,1,0,6,6,3,5,2,7,8,2,7,6,3,2
127 DATA 1,3,1,6,3,5,0,1,2,5,6,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,3
128 DATA 7,4,1,7,7,8,0,1,2,5,7,4,3,0,6,3,2,2,3,4,0,1,0,7,6,3,5,2,7,3,2,7,9,3,1
129 DATA 5,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,2,6,3,5,2,7,9,2,7,9,3,3
130 DATA 3,4,2,8,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,3,6,8,3,5,2,7,8,2,8,0,3,4
131 DATA 6,4,1,7,8,9,0,1,2,5,4,4,3,0,6,3,2,2,3,4,0,1,0,3,6,3,5,2,7,9,2,7,8,3,5
132 DATA 3,4,1,7,3,5,0,1,2,1,2,4,3,0,6,3,2,2,3,4,0,1,0,6,4,3,5,2,7,9,2,7,9,3,9
133 DATA 5,4,1,7,3,5,0,1,2,5,5,4,3,1,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,2,3,3
134 DATA 1,4,1,7,5,2,3,1,2,5,5,4,3,1,6,3,2,2,3,4,2,1,0,6,6,3,5,2,7,9,2,7,9,3,1
135 DATA 1,4,1,7,3,5,5,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,6,6,6,3,5,2,2,6,2,7,9,3,1
136 DATA 2,4,1,7,3,5,2,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,4,9,2,7,6,3,1
137 DATA 7,4,4,5,6,5,0,1,2,5,5,4,3,2,6,3,2,2,3,4,0,1,5,6,7,3,5,2,7,1,2,4,6,3,2
138 DATA 5,4,1,7,3,5,0,5,2,5,5,4,3,0,6,3,2,2,3,4,0,4,0,6,6,3,5,2,7,1,2,7,4,3,2
139 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,3,6,6,3,5,2,7,2,2,7,9,3,2
140 DATA 4,4,1,7,8,5,3,1,2,5,5,4,3,0,5,3,2,2,3,4,0,1,0,6,5,3,5,2,7,9,2,7,2,3,2
141 DATA 2,4,1,7,4,5,0,1,2,5,2,4,3,0,6,3,2,2,3,2,0,1,0,5,6,3,5,2,4,9,2,7,4,3,4
142 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,5,0,1,0,4,6,3,5,2,7,3,2,7,4,3,1
143 DATA 1,4,1,4,3,4,4,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,2
144 DATA 6,4,5,7,3,5,0,1,2,3,5,4,3,3,6,3,2,2,3,4,0,1,0,4,7,3,5,2,7,3,2,7,5,3,3
145 DATA 3,4,1,7,3,5,0,1,2,3,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,7,3,2,7,4,3,2
146 DATA 5,4,1,7,4,6,0,1,2,5,5,4,3,0,5,3,2,2,3,4,0,1,0,5,6,3,5,2,7,9,2,7,9,3,4
147 DATA 3,4,1,7,3,5,0,1,2,5,3,4,3,0,6,3,2,2,3,4,0,1,0,3,6,3,5,2,7,9,2,7,3,3,1
148 DATA 6,4,1,7,3,5,6,1,2,5,5,4,3,0,6,3,2,2,3,4,6,1,0,5,5,3,3,2,7,3,2,7,9,3,3
149 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,7,6,6,3,5,2,7,7,2,7,2,3,2
150 DATA 1,4,1,7,3,5,2,1,2,5,5,4,3,2,6,3,2,2,3,4,2,1,1,6,6,3,5,2,7,1,2,7,9,3,1
151 DATA 3,4,1,7,3,5,3,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,7,9,2,7,2,3,2
152 DATA 7,4,1,7,3,5,7,1,2,5,5,4,3,0,6,3,2,2,3,4,7,1,0,6,6,3,5,2,0,0,2,7,9,3,1
153 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,1
154 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,0
155 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,7,9,2,7,3,3,1
156 DATA 1,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,3
157 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,1,1,3,5,2,7,9,2,7,9,3,2
158 DATA 1,4,1,7,3,5,0,1,2,5,0,4,3,0,6,3,2,2,3,1,0,1,0,6,6,3,5,2,7,9,2,7,9,3,4
159 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,1,2,7,9,3,2
160 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,0,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,7
161 DATA 4,4,1,5,3,5,0,1,2,5,5,4,3,0,5,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,1,3,5
162 DATA 9,4,1,3,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,2,2,7,9,3,8
163 DATA 7,4,1,7,3,5,0,1,2,0,5,4,3,0,0,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,4
164 DATA 3,4,1,7,3,0,0,1,2,0,5,4,3,0,6,3,2,2,3,4,0,1,0,7,6,3,5,2,7,9,2,7,9,3,6
165 DATA 6,2,5,3,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,2,0,2,6,3,5,2,7,2,2,7,2,3,4
166 DATA 3,4,1,7,3,5,0,1,2,3,5,4,3,0,6,3,3,2,3,4,0,1,0,6,6,3,5,2,7,3,2,7,9,3,7
167 DATA 1,2,1,7,3,5,0,1,2,5,5,4,3,0,5,3,2,2,3,4,0,1,0,4,6,3,5,2,7,9,2,7,4,3,3
168 DATA 3,4,1,7,3,5,0,3,2,5,3,4,3,0,6,3,2,2,3,4,0,2,0,6,6,3,5,2,7,3,2,7,9,3,2
169 DATA 3,4,1,7,3,5,0,1,2,5,0,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,3
170 DATA 5,0,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,3
171 DATA 5,4,3,7,5,5,2,5,2,5,5,4,3,0,6,3,2,2,3,4,3,4,4,6,3,3,5,2,7,9,2,7,6,3,4
172 DATA 3,4,1,7,3,5,7,1,2,5,5,4,3,3,6,3,2,2,3,4,0,1,0,1,2,3,5,2,7,9,2,7,5,3,3
173 DATA 5,4,1,7,2,4,0,1,2,5,5,4,3,0,2,3,2,2,3,4,0,1,0,6,6,3,5,2,7,5,2,7,9,3,9
174 DATA 3,4,1,0,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,0,6,3,5,2,7,9,2,7,0,3,4
175 DATA 9,4,2,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,2,2,3,3,5,2,7,3,2,7,9,3,7
176 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,2,2,3,5,2,7,3,2,7,9,3,4
177 DATA 4,4,4,7,3,5,0,1,2,2,3,4,3,0,6,3,2,2,3,4,0,5,0,6,1,3,5,2,7,9,2,7,9,3,6
178 DATA 3,4,1,7,3,5,3,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,7,9,2,7,3,3,2
179 DATA 3,4,3,7,3,5,0,1,2,5,5,4,3,2,6,3,2,2,3,4,2,1,0,6,6,3,3,2,7,1,2,7,9,3,4
180 DATA 2,4,1,7,3,5,6,1,2,5,5,4,3,3,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,0,3,2
181 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,1,2,3,5,2,7,3,2,7,9,3,4
182 DATA 6,5,2,2,3,5,2,1,2,5,5,4,3,0,6,3,2,2,3,4,0,3,3,3,6,3,5,2,7,3,2,7,2,3,5
183 DATA 2,4,1,7,3,2,2,1,2,5,5,4,3,0,4,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,6,3,3
184 DATA 3,4,1,7,3,5,0,1,2,4,5,4,3,0,6,3,2,2,3,4,7,1,0,6,4,3,5,2,7,9,2,7,9,3,3
185 DATA 4,4,1,7,3,5,1,1,2,5,5,4,3,3,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,3,3,6
186 DATA 2,8,2,7,3,5,1,1,2,5,5,4,3,3,2,3,2,2,3,4,9,1,0,6,6,3,5,8,7,9,2,2,3,3,9
187 DATA 6,4,1,7,4,5,1,1,2,5,4,4,3,3,6,3,2,2,3,4,6,1,0,6,6,3,5,2,7,6,2,7,3,3,4
188 DATA 7,4,1,7,3,5,6,1,2,5,7,4,6,3,6,3,2,2,3,4,0,4,0,6,2,3,5,2,7,9,2,7,4,3,2
189 DATA 2,9,1,4,3,2,1,1,2,5,5,4,3,3,6,3,5,2,3,4,0,1,0,2,6,3,9,2,7,9,2,4,3,3,4
190 DATA 7,4,1,7,3,2,1,1,2,5,3,4,3,3,6,3,7,2,3,4,0,3,0,6,6,3,5,2,7,7,2,7,3,3,3
191 DATA 4,7,1,1,3,5,1,1,2,5,1,4,7,3,6,3,2,2,3,4,0,1,0,1,6,3,5,2,7,1,2,7,3,3,1
192 DATA 5,4,9,7,3,5,1,1,2,9,5,4,5,3,9,3,2,2,3,4,0,1,0,5,6,3,5,2,7,9,2,7,3,3,9
193 DATA 9,9,1,8,3,5,1,1,2,5,8,4,9,3,6,3,2,2,3,4,9,1,0,6,6,8,5,5,7,9,2,7,3,5,8
194 DATA 8,4,1,7,2,5,8,1,2,5,5,4,3,2,6,3,8,2,3,4,0,1,0,6,8,3,5,2,7,9,2,7,3,3,2
195 DATA 2,4,1,7,3,5,1,1,5,2,5,4,3,5,6,3,2,3,5,4,0,1,0,3,6,3,5,2,7,9,2,7,3,5,3
196 DATA 9,6,1,7,3,5,1,7,2,5,5,4,3,7,7,3,2,2,3,9,0,7,6,9,6,3,6,2,7,9,2,7,6,3,9
197 DATA 7,4,1,7,3,5,8,3,2,5,7,4,3,8,6,3,2,2,3,4,0,1,0,6,8,3,5,2,7,9,2,7,7,3,8
198 DATA 6,4,2,7,3,5,1,2,2,5,5,4,6,3,2,3,2,4,3,4,0,1,0,7,6,3,5,2,4,9,2,7,2,3,7
199 DATA 5,7,1,6,3,5,7,1,2,5,5,4,3,3,6,3,7,2,3,4,9,1,9,6,5,3,5,6,7,9,6,6,9,3,5
200 DATA 3,8,1,7,3,5,1,8,2,3,5,4,3,3,6,3,2,2,3,4,0,3,0,6,6,3,5,8,7,9,2,7,3,3,8
201 DATA 6,4,1,7,3,5,1,1,2,5,6,4,3,3,6,3,2,2,3,4,6,1,6,6,6,3,5,2,7,6,2,7,3,6,7
202 DATA 4,7,1,7,3,5,1,7,2,7,5,4,3,3,6,3,7,2,3,4,0,1,0,7,6,3,5,2,6,9,2,7,3,3,3
203 DATA 4,6,1,7,3,5,1,1,2,5,6,4,6,3,6,3,2,6,3,6,6,1,0,6,6,3,6,6,7,9,2,7,6,3,1
204 DATA 6,4,1,7,3,5,1,1,2,6,5,4,3,6,6,3,2,2,6,4,0,2,0,6,6,3,6,2,7,6,3,7,3,6,2
205 DATA 5,5,1,4,4,4,5,4,2,5,5,4,3,3,6,4,2,2,3,4,5,1,0,6,4,5,5,2,7,5,2,7,3,4,5
206 DATA 5,4,1,7,3,5,1,1,2,2,7,7,3,3,2,3,2,7,3,4,0,1,0,7,6,3,5,2,7,9,2,7,7,3,1
207 DATA 4,3,4,7,4,5,1,1,2,3,5,4,4,3,6,3,2,2,4,3,3,1,0,6,6,3,5,2,7,3,2,7,3,4,6
208 DATA 6,5,5,7,3,5,6,1,2,5,5,4,3,3,4,3,2,2,3,4,0,5,0,4,6,3,5,2,7,9,2,7,5,3,4
209 DATA 8,8,1,7,3,5,1,3,4,5,5,4,3,3,6,3,1,2,3,4,1,1,4,8,6,3,5,2,7,8,2,7,3,3,0
210 DATA 9,4,1,6,3,6,1,1,2,5,9,4,3,3,6,9,9,6,3,4,0,1,0,6,6,2,5,2,7,9,2,7,3,2,2
211 DATA 6,4,6,2,3,5,2,1,2,5,5,6,3,3,6,3,2,7,3,4,6,1,0,6,6,3,7,2,7,9,2,7,7,3,7
212 DATA 5,4,5,7,3,5,1,4,5,2,5,4,2,3,2,3,2,2,2,2,0,3,2,6,5,3,5,2,8,9,2,7,7,3,5
213 DATA 0,5,1,7,3,5,5,1,2,5,6,4,3,5,6,3,2,2,3,4,0,1,6,5,6,3,5,2,7,9,2,7,6,3,5
214 DATA 3,4,1,4,2,0,1,1,2,2,0,4,3,3,6,3,2,2,2,4,0,1,0,6,6,2,2,2,7,9,2,7,6,3,0
215 DATA 5,4,1,4,2,0,1,1,5,2,0,4,5,3,6,3,2,2,2,4,0,1,0,5,6,2,5,2,7,9,2,7,6,3,9
216 DATA 7,4,1,4,2,0,1,7,2,2,0,4,3,3,6,3,2,7,2,4,0,1,0,7,6,2,2,2,7,9,2,7,6,3,2
217 DATA 2,3,5,4,2,0,1,3,2,3,0,4,3,3,2,3,2,3,2,4,0,1,0,6,2,2,3,2,7,9,2,7,6,3,3
218 DATA 3,4,1,4,2,0,5,1,2,2,0,5,3,3,6,3,2,2,5,5,0,5,0,6,6,2,2,6,9,9,2,7,6,3,4
219 DATA 7,4,1,3,4,0,1,1,2,2,0,4,3,4,6,3,2,2,2,4,0,1,0,6,6,2,2,2,7,9,2,3,6,3,3
220 DATA 8,4,1,4,2,0,1,1,2,2,0,4,3,3,6,8,2,2,2,4,8,1,0,8,6,2,2,2,7,4,2,7,4,4,2
221 DATA 3,2,4,4,2,0,4,1,8,4,0,4,3,3,8,3,4,2,2,4,0,4,0,6,6,6,6,2,7,9,2,7,6,3,0
222 DATA 8,4,1,4,2,0,1,1,2,2,0,4,3,3,6,3,2,2,2,4,0,1,0,6,8,2,2,9,9,9,2,7,6,3,0
223 DATA 7,4,1,7,8,0,1,1,2,2,0,4,8,7,6,3,2,2,2,4,0,1,0,7,6,2,2,2,7,9,2,7,6,3,8
224 DATA 5,3,1,4,2,3,1,1,2,2,0,4,3,3,6,3,2,5,2,5,0,1,2,6,6,2,2,2,7,9,2,7,5,3,4
225 DATA 3,4,5,4,2,0,1,1,4,2,0,4,3,3,3,5,2,2,2,4,0,5,0,6,6,2,5,2,7,9,2,5,6,3,5
226 DATA 7,4,1,4,2,0,1,7,2,2,7,7,3,3,6,3,7,2,7,4,7,1,0,6,7,7,2,2,8,8,2,7,6,3,4
227 DATA 7,2,1,8,2,0,1,1,2,7,0,4,3,8,6,3,2,7,2,4,0,1,3,3,6,2,2,2,7,9,2,7,6,3,3
228 DATA 2,2,1,3,2,0,1,1,2,2,0,4,3,3,2,3,2,2,2,2,0,1,0,6,2,2,2,2,7,2,2,5,6,3,4
229 DATA 6,4,1,6,2,0,1,1,2,2,6,4,3,3,8,3,2,2,2,4,0,1,0,6,6,2,3,3,7,3,2,7,6,3,4
230 DATA 8,4,8,4,8,0,1,1,2,2,0,4,3,3,6,3,2,2,2,4,8,1,0,6,6,2,2,2,6,9,2,7,7,3,2
231 DATA 5,4,2,4,2,0,5,1,2,2,2,5,3,3,6,3,2,5,2,4,0,1,0,6,6,2,5,2,7,9,2,7,6,3,2
232 DATA 2,4,5,4,2,0,1,5,2,2,2,4,3,3,6,3,2,2,2,4,7,1,0,9,6,2,2,2,7,9,2,7,9,3,5
233 DATA 7,4,4,4,2,7,5,1,2,2,0,3,3,3,6,3,5,2,2,5,0,1,0,6,6,2,3,2,7,9,2,5,6,3,4
234 DATA 9,8,1,4,2,0,1,3,2,2,0,4,3,3,6,3,8,2,2,4,0,1,0,8,6,2,2,2,7,9,2,7,6,3,7
235 DATA 8,4,7,4,2,0,1,1,2,2,0,4,3,3,6,3,2,2,8,4,8,1,0,6,6,2,8,2,4,9,2,7,6,3,8
236 DATA 6,4,7,4,2,0,1,6,2,2,0,4,3,3,7,3,7,2,2,4,0,1,0,7,6,2,2,2,7,9,2,7,6,3,1
237 DATA 4,5,1,4,2,0,5,1,2,2,4,4,3,3,6,3,2,4,2,4,0,1,0,4,6,2,2,2,7,9,2,4,6,3,5
238 DATA 5,3,4,4,2,0,1,3,2,4,0,4,3,3,6,3,2,3,2,4,0,9,0,4,6,2,4,2,7,9,2,7,6,3,9
239 DATA 4,6,1,4,2,0,1,4,2,4,0,4,6,3,6,3,2,4,5,4,0,1,0,6,6,2,6,2,7,9,2,7,5,3,6
240 DATA 5,4,6,5,2,0,1,6,2,4,0,4,3,4,6,3,2,6,2,4,0,1,0,7,6,2,2,2,7,9,2,7,6,3,0
241 DATA 7,4,1,4,2,0,1,7,2,2,0,4,7,3,6,3,2,7,2,4,0,1,0,6,7,2,7,2,7,9,2,7,6,7,5
242 DATA 9,7,1,4,5,0,1,1,7,2,0,4,3,3,9
1065 FOR JJJJ=-32000 TO 32000
1074 RANDOMIZE JJJJ
1076 M=-32000
1085 FOR I=1 TO 100
1088 A(I)=FIX(RND*7)
1089 NEXT I
1126 IMAR=10+FIX(RND*2000)
1128 FOR I=1 TO IMAR
1129 FOR KK=1 TO 100
1131 X(KK)=A(KK)
1132 NEXT KK
1223 IJL=1+FIX(RND*100)
1234 X(IJL)=FIX(RND*7)
1533 FOR IX=1 TO 99
1534 FOR JX=IX+1 TO 100
1542 IF X(IX)=X(JX) THEN TM(IX,JX)=HR(IX,JX) ELSE TM(IX,JX)=0
1545 NEXT JX
1547 NEXT IX
1611 SUMTL=0
1612 FOR IR1=1 TO 99
1614 FOR IR2=IR1+1 TO 100
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 100
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 1128
1670 NEXT I
1890 IF M>-1300 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)
1923 PRINT A(56),A(57),A(58),A(59),A(60)
1924 PRINT A(61),A(62),A(63),A(64),A(65)
1925 PRINT A(66),A(67),A(68),A(69),A(70)
1926 PRINT A(71),A(72),A(73),A(74),A(75)
1927 PRINT A(76),A(77),A(78),A(79),A(80)
1928 PRINT A(81),A(82),A(83),A(84),A(85)
1929 PRINT A(86),A(87),A(88),A(89),A(90)
1930 PRINT A(91),A(92),A(93),A(94),A(95)
1931 PRINT A(96),A(97),A(98),A(99),A(100)
1937 PRINT M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, and the best candidate solutions produced in 20 hours of running are presented below. Only the candidate solution at JJJJ=-31786 is presented in full; each of the other candidate solutions below is briefly presented with its line
1937.

4 4 5 5 6
0 2 4 4 3
0 3 0 3 4
6 2 0 6 0
5 4 6 3 5
3 1 5 4 5
3 1 5 0 3
4 2 5 5 2
2 2 6 3 2
2 3 0 6 4
2 3 0 6 0
1 4 6 5 0
1 1 2 4 1
2 1 0 0 3
4 3 5 5 1
1 0 4 2 6
0 5 6 3 4
3 6 6 2 1
1 6 1 4 0
1 1 0 4 5
-1261 -31786

-1292 -31592

-1299 -31580

-1292 -31485

-1276 -31469

Interpreted in accordance with line 1912 through line 1937, these candidate solutions were produced in 20 hours 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).

An IP Computer Program Applied to a One-Dimensional Space Allocation Problem, Second Edition

An Integer-Programming Computer Program Applied to a One-Dimensional Space
Allocation Problem, Second Edition

Jsun Yui Wong

The computer program listed below seeks to solve Problem S8 of Amaral (2006),
which is a problem from Simmons (1969). In order to have integer locations, the
department lengths used in the computer program below have been made twice as
long as the given department lengths.

0 DEFINT A-Z
15 DIM X(11),A(11)
16 DIM TM(24,24),HR(24,24),HS(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 5,6,7,8,5,9,6,7,8,9,6,10,7,9,10,7,11,8,11,8,12,9,9,13,10,10,7,11
41 FOR IZ=1 TO 7
43 FOR JZ=IZ+1 TO 8
46 READ HS(IZ,JZ)
48 NEXT JZ
49 NEXT IZ
52 DATA 6,4,1,7,3,5,0,1,2,5,2,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-32000
85 FOR II=1 TO 8
88 A(II)=RND*99
89 NEXT II
126 IMAR=10+FIX(RND*2000)
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)=RND*99
533 FOR IX=1 TO 7
534 FOR JX=IX+1 TO 8
543 IF ABS(X(IX)-X(JX))-HR(IX,JX)<-.0001 THEN TM(IX,JX)=1000 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
1631 SUMUL=0
1632 FOR IS1=1 TO 7
1634 FOR IS2=IS1+1 TO 8
1636 SUMUL=SUMUL+HS(IS1,IS2)*ABS(X(IS1)-X(IS2))
1637 NEXT IS2
1639 NEXT IS1
1645 P=-SUMUL-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>-1605 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 best candidate solutions through JJJJ=-21042 are presented below. What immediately follows is a manual copy from the computer screen.

67 72 49 26 59
34 82 41 -1602 -31520

38 33 56 79 46
71 23 64 -1602 -25855

60 65 42 19 52
27 75 34 -1602 -25642

19 14 37 60 27
52 4 45 -1602 -22630

54 59 36 13 46
21 69 28 -1602 -22263

62 67 44 21 54
29 77 36 -1602 -22006

75 80 57 34 67
42 90 49 -1602 -21959

70 75 52 29 62
37 85 44 -1602 -21042

1602 is optimal. Interpreted in accordance with line 1912 and line 1914, the output through JJJJ=-21042 was produced in three hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

References

Amaral, A. R. S., "On the exact solution of a facility layout problem," European Journal of Operational Research 173, 508-518 (2006).

Simmons, D. M., "One-dimensional space allocation: an ordering algorithm," Operations Research 17, 812-826 (1969).

A Computer Program for Scheduling 90 Activities among Four Facilities

Jsun Yui Wong

The computer programn listed below is concerned with the scheduling problem of Carlson and Nemhauser (1966). As shown in line 101 through line 215 for a case of scheduling 90 activities among four 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 89 and activity 90 are 1, 4, 1, ..., and 5, respectively. These data were not selected randomly or scientifically.

0 DEFINT A-Z
4 DIM X(90),A(90)
7 DIM TM(90,90),HR(90,90)
21 FOR IW=1 TO 89
23 FOR JW=IW+1 TO 90
26 READ HR(IW,JW)
28 NEXT JW
29 NEXT IW
101 DATA 1,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,1
102 DATA 2,3,1,6,6,3,0,1,2,4,4,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,4,3,4
103 DATA 1,9,3,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,5,6,3,4,2,7,4,2,3,4,3,2
104 DATA 4,3,1,7,7,1,0,4,2,3,7,4,3,0,6,3,2,2,3,2,3,5,0,6,5,3,5,4,2,9,2,7,9,3,7
105 DATA 3,4,5,7,3,5,0,1,2,5,5,2,3,0,6,3,2,2,3,4,0,4,0,2,6,3,5,2,6,8,2,3,4,3,2
106 DATA 9,3,1,7,3,4,0,1,2,5,5,4,3,0,6,3,2,2,8,4,0,1,0,6,2,3,5,2,7,1,2,7,8,3,2
107 DATA 7,4,1,0,3,5,0,1,2,4,5,4,3,0,6,3,2,2,3,4,1,1,0,6,5,5,8,2,7,9,2,7,8,3,6
108 DATA 2,2,3,7,3,5,3,3,2,5,5,4,3,3,6,3,2,2,3,4,0,3,0,2,6,3,5,2,3,8,2,7,8,3,4
109 DATA 5,4,1,6,5,7,0,1,2,5,5,4,3,0,6,3,2,2,3,4,2,1,2,6,6,3,5,2,7,8,2,7,2,3,5
110 DATA 2,4,1,7,3,5,1,1,2,4,2,4,3,0,5,3,2,2,3,4,0,1,2,6,6,4,5,9,7,9,2,7,9,3,2
111 DATA 7,3,4,4,3,5,5,1,2,5,5,4,3,0,6,3,2,2,3,4,5,1,0,6,6,3,5,2,4,4,2,4,4,3,1
112 DATA 2,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,2
113 DATA 3,4,6,7,3,5,1,1,2,5,5,4,3,4,6,3,2,2,3,4,3,3,1,6,6,3,5,2,7,9,2,7,9,3,8
114 DATA 4,4,1,7,4,5,0,1,2,5,5,4,3,1,6,3,2,2,3,4,0,1,1,4,6,4,6,2,7,9,2,7,9,3,1
115 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,2
116 DATA 2,5,1,3,6,2,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,6,2,7,9,3,2
117 DATA 9,3,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,5,4,5,2,7,2,2,4,4,3,7
118 DATA 3,4,1,7,4,5,3,1,2,5,3,4,3,0,6,3,2,2,3,4,5,1,4,6,4,3,5,2,3,4,2,7,4,3,1
119 DATA 6,4,1,7,3,5,0,1,2,5,5,4,3,6,6,3,2,2,3,4,0,1,6,6,6,3,5,2,7,0,2,7,9,3,7
120 DATA 4,2,1,2,7,0,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,3,6,6,3,2,2,3,2,2,4,4,3
121 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,3
122 DATA 3,4,2,7,3,0,0,1,2,4,6,4,3,0,6,3,2,2,3,4,0,2,0,5,6,3,5,2,7,2,2,7,2,3,2
123 DATA 8,4,1,7,3,5,0,1,2,4,7,4,3,0,6,3,2,2,3,4,0,1,0,7,6,3,5,2,7,0,2,7,9,3,8
124 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,7,3,2,2,3,4,0,1,0,4,2,3,5,2,7,8,2,7,0,3,1
125 DATA 9,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,3,2,3,4,0,1,0,6,2,3,5,2,7,9,2,7,0,3,7
126 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,7,3,2,2,3,4,0,1,0,6,6,3,5,2,7,8,2,7,6,3,2
127 DATA 1,3,1,6,3,5,0,1,2,5,6,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,3
128 DATA 7,4,1,7,7,8,0,1,2,5,7,4,3,0,6,3,2,2,3,4,0,1,0,7,6,3,5,2,7,3,2,7,9,3,1
129 DATA 5,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,2,6,3,5,2,7,9,2,7,9,3,3
130 DATA 3,4,2,8,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,3,6,8,3,5,2,7,8,2,8,0,3,4
131 DATA 6,4,1,7,8,9,0,1,2,5,4,4,3,0,6,3,2,2,3,4,0,1,0,3,6,3,5,2,7,9,2,7,8,3,5
132 DATA 3,4,1,7,3,5,0,1,2,1,2,4,3,0,6,3,2,2,3,4,0,1,0,6,4,3,5,2,7,9,2,7,9,3,9
133 DATA 5,4,1,7,3,5,0,1,2,5,5,4,3,1,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,2,3,3
134 DATA 1,4,1,7,5,2,3,1,2,5,5,4,3,1,6,3,2,2,3,4,2,1,0,6,6,3,5,2,7,9,2,7,9,3,1
135 DATA 1,4,1,7,3,5,5,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,6,6,6,3,5,2,2,6,2,7,9,3,1
136 DATA 2,4,1,7,3,5,2,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,4,9,2,7,6,3,1
137 DATA 7,4,4,5,6,5,0,1,2,5,5,4,3,2,6,3,2,2,3,4,0,1,5,6,7,3,5,2,7,1,2,4,6,3,2
138 DATA 5,4,1,7,3,5,0,5,2,5,5,4,3,0,6,3,2,2,3,4,0,4,0,6,6,3,5,2,7,1,2,7,4,3,2
139 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,3,6,6,3,5,2,7,2,2,7,9,3,2
140 DATA 4,4,1,7,8,5,3,1,2,5,5,4,3,0,5,3,2,2,3,4,0,1,0,6,5,3,5,2,7,9,2,7,2,3,2
141 DATA 2,4,1,7,4,5,0,1,2,5,2,4,3,0,6,3,2,2,3,2,0,1,0,5,6,3,5,2,4,9,2,7,4,3,4
142 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,5,0,1,0,4,6,3,5,2,7,3,2,7,4,3,1
143 DATA 1,4,1,4,3,4,4,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,2
144 DATA 6,4,5,7,3,5,0,1,2,3,5,4,3,3,6,3,2,2,3,4,0,1,0,4,7,3,5,2,7,3,2,7,5,3,3
145 DATA 3,4,1,7,3,5,0,1,2,3,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,7,3,2,7,4,3,2
146 DATA 5,4,1,7,4,6,0,1,2,5,5,4,3,0,5,3,2,2,3,4,0,1,0,5,6,3,5,2,7,9,2,7,9,3,4
147 DATA 3,4,1,7,3,5,0,1,2,5,3,4,3,0,6,3,2,2,3,4,0,1,0,3,6,3,5,2,7,9,2,7,3,3,1
148 DATA 6,4,1,7,3,5,6,1,2,5,5,4,3,0,6,3,2,2,3,4,6,1,0,5,5,3,3,2,7,3,2,7,9,3,3
149 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,7,6,6,3,5,2,7,7,2,7,2,3,2
150 DATA 1,4,1,7,3,5,2,1,2,5,5,4,3,2,6,3,2,2,3,4,2,1,1,6,6,3,5,2,7,1,2,7,9,3,1
151 DATA 3,4,1,7,3,5,3,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,7,9,2,7,2,3,2
152 DATA 7,4,1,7,3,5,7,1,2,5,5,4,3,0,6,3,2,2,3,4,7,1,0,6,6,3,5,2,0,0,2,7,9,3,1
153 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,1
154 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,0
155 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,7,9,2,7,3,3,1
156 DATA 1,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,3
157 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,1,1,3,5,2,7,9,2,7,9,3,2
158 DATA 1,4,1,7,3,5,0,1,2,5,0,4,3,0,6,3,2,2,3,1,0,1,0,6,6,3,5,2,7,9,2,7,9,3,4
159 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,1,2,7,9,3,2
160 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,0,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,7
161 DATA 4,4,1,5,3,5,0,1,2,5,5,4,3,0,5,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,1,3,5
162 DATA 9,4,1,3,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,2,2,7,9,3,8
163 DATA 7,4,1,7,3,5,0,1,2,0,5,4,3,0,0,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,4
164 DATA 3,4,1,7,3,0,0,1,2,0,5,4,3,0,6,3,2,2,3,4,0,1,0,7,6,3,5,2,7,9,2,7,9,3,6
165 DATA 6,2,5,3,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,2,0,2,6,3,5,2,7,2,2,7,2,3,4
166 DATA 3,4,1,7,3,5,0,1,2,3,5,4,3,0,6,3,3,2,3,4,0,1,0,6,6,3,5,2,7,3,2,7,9,3,7
167 DATA 1,2,1,7,3,5,0,1,2,5,5,4,3,0,5,3,2,2,3,4,0,1,0,4,6,3,5,2,7,9,2,7,4,3,3
168 DATA 3,4,1,7,3,5,0,3,2,5,3,4,3,0,6,3,2,2,3,4,0,2,0,6,6,3,5,2,7,3,2,7,9,3,2
169 DATA 3,4,1,7,3,5,0,1,2,5,0,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,3
170 DATA 5,0,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,3
171 DATA 5,4,3,7,5,5,2,5,2,5,5,4,3,0,6,3,2,2,3,4,3,4,4,6,3,3,5,2,7,9,2,7,6,3,4
172 DATA 3,4,1,7,3,5,7,1,2,5,5,4,3,3,6,3,2,2,3,4,0,1,0,1,2,3,5,2,7,9,2,7,5,3,3
173 DATA 5,4,1,7,2,4,0,1,2,5,5,4,3,0,2,3,2,2,3,4,0,1,0,6,6,3,5,2,7,5,2,7,9,3,9
174 DATA 3,4,1,0,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,0,6,3,5,2,7,9,2,7,0,3,4
175 DATA 9,4,2,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,2,2,3,3,5,2,7,3,2,7,9,3,7
176 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,2,2,3,5,2,7,3,2,7,9,3,4
177 DATA 4,4,4,7,3,5,0,1,2,2,3,4,3,0,6,3,2,2,3,4,0,5,0,6,1,3,5,2,7,9,2,7,9,3,6
178 DATA 3,4,1,7,3,5,3,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,7,9,2,7,3,3,2
179 DATA 3,4,3,7,3,5,0,1,2,5,5,4,3,2,6,3,2,2,3,4,2,1,0,6,6,3,3,2,7,1,2,7,9,3,4
180 DATA 2,4,1,7,3,5,6,1,2,5,5,4,3,3,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,0,3,2
181 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,1,2,3,5,2,7,3,2,7,9,3,4
182 DATA 6,5,2,2,3,5,2,1,2,5,5,4,3,0,6,3,2,2,3,4,0,3,3,3,6,3,5,2,7,3,2,7,2,3,5
183 DATA 2,4,1,7,3,2,2,1,2,5,5,4,3,0,4,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,6,3,3
184 DATA 3,4,1,7,3,5,0,1,2,4,5,4,3,0,6,3,2,2,3,4,7,1,0,6,4,3,5,2,7,9,2,7,9,3,3
185 DATA 4,4,1,7,3,5,1,1,2,5,5,4,3,3,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,3,3,6
186 DATA 2,8,2,7,3,5,1,1,2,5,5,4,3,3,2,3,2,2,3,4,9,1,0,6,6,3,5,8,7,9,2,2,3,3,9
187 DATA 6,4,1,7,4,5,1,1,2,5,4,4,3,3,6,3,2,2,3,4,6,1,0,6,6,3,5,2,7,6,2,7,3,3,4
188 DATA 7,4,1,7,3,5,6,1,2,5,7,4,6,3,6,3,2,2,3,4,0,4,0,6,2,3,5,2,7,9,2,7,4,3,2
189 DATA 2,9,1,4,3,2,1,1,2,5,5,4,3,3,6,3,5,2,3,4,0,1,0,2,6,3,9,2,7,9,2,4,3,3,4
190 DATA 7,4,1,7,3,2,1,1,2,5,3,4,3,3,6,3,7,2,3,4,0,3,0,6,6,3,5,2,7,7,2,7,3,3,3
191 DATA 4,7,1,1,3,5,1,1,2,5,1,4,7,3,6,3,2,2,3,4,0,1,0,1,6,3,5,2,7,1,2,7,3,3,1
192 DATA 5,4,9,7,3,5,1,1,2,9,5,4,5,3,9,3,2,2,3,4,0,1,0,5,6,3,5,2,7,9,2,7,3,3,9
193 DATA 9,9,1,8,3,5,1,1,2,5,8,4,9,3,6,3,2,2,3,4,9,1,0,6,6,8,5,5,7,9,2,7,3,5,8
194 DATA 8,4,1,7,2,5,8,1,2,5,5,4,3,2,6,3,8,2,3,4,0,1,0,6,8,3,5,2,7,9,2,7,3,3,2
195 DATA 2,4,1,7,3,5,1,1,5,2,5,4,3,5,6,3,2,3,5,4,0,1,0,3,6,3,5,2,7,9,2,7,3,5,3
196 DATA 9,6,1,7,3,5,1,7,2,5,5,4,3,7,7,3,2,2,3,9,0,7,6,9,6,3,6,2,7,9,2,7,6,3,9
197 DATA 7,4,1,7,3,5,8,3,2,5,7,4,3,8,6,3,2,2,3,4,0,1,0,6,8,3,5,2,7,9,2,7,7,3,8
198 DATA 6,4,2,7,3,5,1,2,2,5,5,4,6,3,2,3,2,4,3,4,0,1,0,7,6,3,5,2,4,9,2,7,2,3,7
199 DATA 5,7,1,6,3,5,7,1,2,5,5,4,3,3,6,3,7,2,3,4,9,1,9,6,5,3,5,6,7,9,6,6,9,3,5
200 DATA 3,8,1,7,3,5,1,8,2,3,5,4,3,3,6,3,2,2,3,4,0,3,0,6,6,3,5,8,7,9,2,7,3,3,8
201 DATA 6,4,1,7,3,5,1,1,2,5,6,4,3,3,6,3,2,2,3,4,6,1,6,6,6,3,5,2,7,6,2,7,3,6,7
202 DATA 4,7,1,7,3,5,1,7,2,7,5,4,3,3,6,3,7,2,3,4,0,1,0,7,6,3,5,2,6,9,2,7,3,3,3
203 DATA 4,6,1,7,3,5,1,1,2,5,6,4,6,3,6,3,2,6,3,6,6,1,0,6,6,3,6,6,7,9,2,7,6,3,1
204 DATA 6,4,1,7,3,5,1,1,2,6,5,4,3,6,6,3,2,2,6,4,0,2,0,6,6,3,6,2,7,6,3,7,3,6,2
205 DATA 5,5,1,4,4,4,5,4,2,5,5,4,3,3,6,4,2,2,3,4,5,1,0,6,4,5,5,2,7,5,2,7,3,4,5
206 DATA 5,4,1,7,3,5,1,1,2,2,7,7,3,3,2,3,2,7,3,4,0,1,0,7,6,3,5,2,7,9,2,7,7,3,1
207 DATA 4,3,4,7,4,5,1,1,2,3,5,4,4,3,6,3,2,2,4,3,3,1,0,6,6,3,5,2,7,3,2,7,3,4,6
208 DATA 6,5,5,7,3,5,6,1,2,5,5,4,3,3,4,3,2,2,3,4,0,5,0,4,6,3,5,2,7,9,2,7,5,3,4
209 DATA 8,8,1,7,3,5,1,3,4,5,5,4,3,3,6,3,1,2,3,4,1,1,4,8,6,3,5,2,7,8,2,7,3,3,0
210 DATA 9,4,1,6,3,6,1,1,2,5,9,4,3,3,6,9,9,6,3,4,0,1,0,6,6,2,5,2,7,9,2,7,3,2,2
211 DATA 6,4,6,2,3,5,2,1,2,5,5,6,3,3,6,3,2,7,3,4,6,1,0,6,6,3,7,2,7,9,2,7,7,3,7
212 DATA 5,4,5,7,3,5,1,4,5,2,5,4,2,3,2,3,2,2,2,2,0,3,2,6,5,3,5,2,8,9,2,7,7,3,5
213 DATA 0,5,1,7,3,5,5,1,2,5,6,4,3,5,6,3,2,2,3,4,0,1,6,5,6,3,5,2,7,9,2,7,6,3,5
214 DATA 3,4,1,4,2,0,1,1,2,2,0,4,3,3,6,3,2,2,2,4,0,1,0,6,6,2,2,2,7,9,2,7,6,3,0
215 DATA 3,3,1,7,0,5,1,1,2,5,5,0,3,3,5
1065 FOR JJJJ=-32000 TO 32000
1074 RANDOMIZE JJJJ
1076 M=-32000
1085 FOR I=1 TO 90
1088 A(I)=FIX(RND*4)
1089 NEXT I
1126 IMAR=10+FIX(RND*2000)
1128 FOR I=1 TO IMAR
1129 FOR KK=1 TO 90
1131 X(KK)=A(KK)
1132 NEXT KK
1223 IJL=1+FIX(RND*90)
1234 X(IJL)=FIX(RND*4)
1533 FOR IX=1 TO 89
1534 FOR JX=IX+1 TO 90
1542 IF X(IX)=X(JX) THEN TM(IX,JX)=HR(IX,JX) ELSE TM(IX,JX)=0
1545 NEXT JX
1547 NEXT IX
1611 SUMTL=0
1612 FOR IR1=1 TO 89
1614 FOR IR2=IR1+1 TO 90
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 90
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 1128
1670 NEXT I
1890 IF M>-2400 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)
1923 PRINT A(56),A(57),A(58),A(59),A(60)
1924 PRINT A(61),A(62),A(63),A(64),A(65)
1925 PRINT A(66),A(67),A(68),A(69),A(70)
1926 PRINT A(71),A(72),A(73),A(74),A(75)
1927 PRINT A(76),A(77),A(78),A(79),A(80)
1928 PRINT A(81),A(82),A(83),A(84),A(85)
1929 PRINT A(86),A(87),A(88),A(89),A(90)
1937 PRINT M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, and the best candidate solutions through JJJJ=-31765 are presented below. Only the candidate solution at JJJJ=-31948 is presented in full; each of the other candidate solutions below is briefly presented with its line 1937.

0 1 0 2 3
3 1 0 1 0
2 3 3 2 0
2 0 2 3 3
2 0 2 0 2
3 3 2 0 1
0 1 3 2 1
0 2 0 1 3
3 2 0 1 0
0 3 3 2 0
2 0 0 3 2
2 0 2 0 2
3 2 2 0 1
1 1 3 2 1
1 1 1 1 3
1 1 0 1 3
1 3 3 3 0
1 3 0 3 2
-2357 -31948

-2357 -31898

-2357 -31887

-2357 -31883

-2357 -31840

-2357 -31797

-2357 -31786

-2357 -31765

Interpreted in accordance with line 1912 through line 1937, these candidate solutions were produced in 5.5 hours 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).

A Computer Program for Scheduling 78 Activities among Four Facilities

Jsun Yui Wong

The computer programn listed below is concerned with the scheduling problem of Carlson and Nemhauser (1966). As shown in line 101 through line 186 for a case of scheduling 78 activities among four 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 77 and activity 78 are 1, 4, 1, ..., and 6, respectively. These data were not selected randomly or scientifically.

0 DEFSNG A-Z
3 DEFINT I,J,K
4 DIM X(90),A(90)
7 DIM TM(78,78),HR(78,78)
21 FOR IW=1 TO 77
23 FOR JW=IW+1 TO 78
26 READ HR(IW,JW)
28 NEXT JW
29 NEXT IW
101 DATA 1,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,1
102 DATA 2,3,1,6,6,3,0,1,2,4,4,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,4,3,4
103 DATA 1,9,3,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,5,6,3,4,2,7,4,2,3,4,3,2
104 DATA 4,3,1,7,7,1,0,4,2,3,7,4,3,0,6,3,2,2,3,2,3,5,0,6,5,3,5,4,2,9,2,7,9,3,7
105 DATA 3,4,5,7,3,5,0,1,2,5,5,2,3,0,6,3,2,2,3,4,0,4,0,2,6,3,5,2,6,8,2,3,4,3,2
106 DATA 9,3,1,7,3,4,0,1,2,5,5,4,3,0,6,3,2,2,8,4,0,1,0,6,2,3,5,2,7,1,2,7,8,3,2
107 DATA 7,4,1,0,3,5,0,1,2,4,5,4,3,0,6,3,2,2,3,4,1,1,0,6,5,5,8,2,7,9,2,7,8,3,6
108 DATA 2,2,3,7,3,5,3,3,2,5,5,4,3,3,6,3,2,2,3,4,0,3,0,2,6,3,5,2,3,8,2,7,8,3,4
109 DATA 5,4,1,6,5,7,0,1,2,5,5,4,3,0,6,3,2,2,3,4,2,1,2,6,6,3,5,2,7,8,2,7,2,3,5
110 DATA 2,4,1,7,3,5,1,1,2,4,2,4,3,0,5,3,2,2,3,4,0,1,2,6,6,4,5,9,7,9,2,7,9,3,2
111 DATA 7,3,4,4,3,5,5,1,2,5,5,4,3,0,6,3,2,2,3,4,5,1,0,6,6,3,5,2,4,4,2,4,4,3,1
112 DATA 2,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,2
113 DATA 3,4,6,7,3,5,1,1,2,5,5,4,3,4,6,3,2,2,3,4,3,3,1,6,6,3,5,2,7,9,2,7,9,3,8
114 DATA 4,4,1,7,4,5,0,1,2,5,5,4,3,1,6,3,2,2,3,4,0,1,1,4,6,4,6,2,7,9,2,7,9,3,1
115 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,2
116 DATA 2,5,1,3,6,2,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,6,2,7,9,3,2
117 DATA 9,3,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,5,4,5,2,7,2,2,4,4,3,7
118 DATA 3,4,1,7,4,5,3,1,2,5,3,4,3,0,6,3,2,2,3,4,5,1,4,6,4,3,5,2,3,4,2,7,4,3,1
119 DATA 6,4,1,7,3,5,0,1,2,5,5,4,3,6,6,3,2,2,3,4,0,1,6,6,6,3,5,2,7,0,2,7,9,3,7
120 DATA 4,2,1,2,7,0,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,3,6,6,3,2,2,3,2,2,4,4,3
121 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,3
122 DATA 3,4,2,7,3,0,0,1,2,4,6,4,3,0,6,3,2,2,3,4,0,2,0,5,6,3,5,2,7,2,2,7,2,3,2
123 DATA 8,4,1,7,3,5,0,1,2,4,7,4,3,0,6,3,2,2,3,4,0,1,0,7,6,3,5,2,7,0,2,7,9,3,8
124 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,7,3,2,2,3,4,0,1,0,4,2,3,5,2,7,8,2,7,0,3,1
125 DATA 9,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,3,2,3,4,0,1,0,6,2,3,5,2,7,9,2,7,0,3,7
126 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,7,3,2,2,3,4,0,1,0,6,6,3,5,2,7,8,2,7,6,3,2
127 DATA 1,3,1,6,3,5,0,1,2,5,6,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,3
128 DATA 7,4,1,7,7,8,0,1,2,5,7,4,3,0,6,3,2,2,3,4,0,1,0,7,6,3,5,2,7,3,2,7,9,3,1
129 DATA 5,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,2,6,3,5,2,7,9,2,7,9,3,3
130 DATA 3,4,2,8,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,3,6,8,3,5,2,7,8,2,8,0,3,4
131 DATA 6,4,1,7,8,9,0,1,2,5,4,4,3,0,6,3,2,2,3,4,0,1,0,3,6,3,5,2,7,9,2,7,8,3,5
132 DATA 3,4,1,7,3,5,0,1,2,1,2,4,3,0,6,3,2,2,3,4,0,1,0,6,4,3,5,2,7,9,2,7,9,3,9
133 DATA 5,4,1,7,3,5,0,1,2,5,5,4,3,1,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,2,3,3
134 DATA 1,4,1,7,5,2,3,1,2,5,5,4,3,1,6,3,2,2,3,4,2,1,0,6,6,3,5,2,7,9,2,7,9,3,1
135 DATA 1,4,1,7,3,5,5,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,6,6,6,3,5,2,2,6,2,7,9,3,1
136 DATA 2,4,1,7,3,5,2,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,4,9,2,7,6,3,1
137 DATA 7,4,4,5,6,5,0,1,2,5,5,4,3,2,6,3,2,2,3,4,0,1,5,6,7,3,5,2,7,1,2,4,6,3,2
138 DATA 5,4,1,7,3,5,0,5,2,5,5,4,3,0,6,3,2,2,3,4,0,4,0,6,6,3,5,2,7,1,2,7,4,3,2
139 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,3,6,6,3,5,2,7,2,2,7,9,3,2
140 DATA 4,4,1,7,8,5,3,1,2,5,5,4,3,0,5,3,2,2,3,4,0,1,0,6,5,3,5,2,7,9,2,7,2,3,2
141 DATA 2,4,1,7,4,5,0,1,2,5,2,4,3,0,6,3,2,2,3,2,0,1,0,5,6,3,5,2,4,9,2,7,4,3,4
142 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,5,0,1,0,4,6,3,5,2,7,3,2,7,4,3,1
143 DATA 1,4,1,4,3,4,4,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,2
144 DATA 6,4,5,7,3,5,0,1,2,3,5,4,3,3,6,3,2,2,3,4,0,1,0,4,7,3,5,2,7,3,2,7,5,3,3
145 DATA 3,4,1,7,3,5,0,1,2,3,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,7,3,2,7,4,3,2
146 DATA 5,4,1,7,4,6,0,1,2,5,5,4,3,0,5,3,2,2,3,4,0,1,0,5,6,3,5,2,7,9,2,7,9,3,4
147 DATA 3,4,1,7,3,5,0,1,2,5,3,4,3,0,6,3,2,2,3,4,0,1,0,3,6,3,5,2,7,9,2,7,3,3,1
148 DATA 6,4,1,7,3,5,6,1,2,5,5,4,3,0,6,3,2,2,3,4,6,1,0,5,5,3,3,2,7,3,2,7,9,3,3
149 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,7,6,6,3,5,2,7,7,2,7,2,3,2
150 DATA 1,4,1,7,3,5,2,1,2,5,5,4,3,2,6,3,2,2,3,4,2,1,1,6,6,3,5,2,7,1,2,7,9,3,1
151 DATA 3,4,1,7,3,5,3,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,7,9,2,7,2,3,2
152 DATA 7,4,1,7,3,5,7,1,2,5,5,4,3,0,6,3,2,2,3,4,7,1,0,6,6,3,5,2,0,0,2,7,9,3,1
153 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,1
154 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,0
155 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,7,9,2,7,3,3,1
156 DATA 1,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,3
157 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,1,1,3,5,2,7,9,2,7,9,3,2
158 DATA 1,4,1,7,3,5,0,1,2,5,0,4,3,0,6,3,2,2,3,1,0,1,0,6,6,3,5,2,7,9,2,7,9,3,4
159 DATA 0,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,1,2,7,9,3,2
160 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,0,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,7
161 DATA 4,4,1,5,3,5,0,1,2,5,5,4,3,0,5,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,1,3,5
162 DATA 9,4,1,3,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,2,2,7,9,3,8
163 DATA 7,4,1,7,3,5,0,1,2,0,5,4,3,0,0,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,9,3,4
164 DATA 3,4,1,7,3,0,0,1,2,0,5,4,3,0,6,3,2,2,3,4,0,1,0,7,6,3,5,2,7,9,2,7,9,3,6
165 DATA 6,2,5,3,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,2,0,2,6,3,5,2,7,2,2,7,2,3,4
166 DATA 3,4,1,7,3,5,0,1,2,3,5,4,3,0,6,3,3,2,3,4,0,1,0,6,6,3,5,2,7,3,2,7,9,3,7
167 DATA 1,2,1,7,3,5,0,1,2,5,5,4,3,0,5,3,2,2,3,4,0,1,0,4,6,3,5,2,7,9,2,7,4,3,3
168 DATA 3,4,1,7,3,5,0,3,2,5,3,4,3,0,6,3,2,2,3,4,0,2,0,6,6,3,5,2,7,3,2,7,9,3,2
169 DATA 3,4,1,7,3,5,0,1,2,5,0,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,3
170 DATA 5,0,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,0,2,7,9,3,3
171 DATA 5,4,3,7,5,5,2,5,2,5,5,4,3,0,6,3,2,2,3,4,3,4,4,6,3,3,5,2,7,9,2,7,6,3,4
172 DATA 3,4,1,7,3,5,7,1,2,5,5,4,3,3,6,3,2,2,3,4,0,1,0,1,2,3,5,2,7,9,2,7,5,3,3
173 DATA 5,4,1,7,2,4,0,1,2,5,5,4,3,0,2,3,2,2,3,4,0,1,0,6,6,3,5,2,7,5,2,7,9,3,9
174 DATA 3,4,1,0,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,0,6,3,5,2,7,9,2,7,0,3,4
175 DATA 9,4,2,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,2,2,3,3,5,2,7,3,2,7,9,3,7
176 DATA 7,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,0,1,0,2,2,3,5,2,7,3,2,7,9,3,4
177 DATA 4,4,4,7,3,5,0,1,2,2,3,4,3,0,6,3,2,2,3,4,0,5,0,6,1,3,5,2,7,9,2,7,9,3,6
178 DATA 3,4,1,7,3,5,3,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,6,6,3,5,2,7,9,2,7,3,3,2
179 DATA 3,4,3,7,3,5,0,1,2,5,5,4,3,2,6,3,2,2,3,4,2,1,0,6,6,3,3,2,7,1,2,7,9,3,4
180 DATA 2,4,1,7,3,5,6,1,2,5,5,4,3,3,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,0,3,2
181 DATA 3,4,1,7,3,5,0,1,2,5,5,4,3,0,6,3,2,2,3,4,3,1,0,1,2,3,5,2,7,3,2,7,9,3,4
182 DATA 6,5,2,2,3,5,2,1,2,5,5,4,3,0,6,3,2,2,3,4,0,3,3,3,6,3,5,2,7,3,2,7,2,3,5
183 DATA 2,4,1,7,3,2,2,1,2,5,5,4,3,0,4,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,6,3,3
184 DATA 3,4,1,7,3,5,0,1,2,4,5,4,3,0,6,3,2,2,3,4,7,1,0,6,4,3,5,2,7,9,2,7,9,3,3
185 DATA 4,4,1,7,3,5,1,1,2,5,5,4,3,3,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,9,2,7,3,3,6
186 DATA 3,2,7,5,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2,7,7,2,7,4,3,6
1065 FOR JJJJ=-32000 TO 32000
1074 RANDOMIZE JJJJ
1076 M=-1D+17
1085 FOR I=1 TO 78
1088 A(I)=FIX(RND*4)
1089 NEXT I
1126 IMAR=10+FIX(RND*2000)
1128 FOR I=1 TO IMAR
1129 FOR KK=1 TO 78
1131 X(KK)=A(KK)
1132 NEXT KK
1223 IJL=1+FIX(RND*78)
1234 X(IJL)=FIX(RND*4)
1533 FOR IX=1 TO 77
1534 FOR JX=IX+1 TO 78
1542 IF X(IX)=X(JX) THEN TM(IX,JX)=HR(IX,JX) ELSE TM(IX,JX)=0
1545 NEXT JX
1547 NEXT IX
1611 SUMTL=0
1612 FOR IR1=1 TO 77
1614 FOR IR2=IR1+1 TO 78
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 78
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 1128
1670 NEXT I
1890 IF M>-1700 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)
1923 PRINT A(56),A(57),A(58),A(59),A(60)
1924 PRINT A(61),A(62),A(63),A(64),A(65)
1925 PRINT A(66),A(67),A(68),A(69),A(70)
1926 PRINT A(71),A(72),A(73),A(74),A(75)
1927 PRINT A(76),A(77),A(78),M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, and the best candidate solutions produced during the first twenty hours of running are presented below. Only the candidate solution at JJJJ=-31961 is presented in full; each of the other candidate solutions below is briefly presented with its line
1927.

2 3 3 0 0
3 2 2 1 0
0 3 3 2 2
3 3 2 1 0
2 2 3 1 1
1 3 2 2 0
1 2 3 1 2
2 3 3 3 0
0 1 2 3 0
0 3 3 2 2
3 0 3 1 0
3 2 2 1 1
0 1 1 2 0
1 0 1 1 0
2 1 3 3 0
0 1 2 -1677 -31961

2 0 3 -1677 -31682

3 1 0 -1677 -31567

0 3 1 -1677 -31505

0 1 2 -1677 -31482

0 1 3 -1677 -31395

0 1 2 -1677 -31153

1 3 0 -1677 -31068

1 0 3 -1677 -30981

0 3 2 -1677 -30946

1 2 0 -1677 -30908

Interpreted in accordance with line 1912 through line 1927, these candidate solutions were produced during the first twenty hours 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).

ERRATA in "An Integer-Programming Computer Program Applied to a One-Dimensional Space Allocation Problem"

Jsun Yui Wong

Line 364 and line 366 of the September 7 post of the present blog should read
as follows:

364 IF ABS(X(K)-X(J)) less than TBM(K,J) THEN TZ(K,J)=99999! ELSE TZ(K,J)=0
366 NEXT J

The "less than" above should be replaced by <.

Moreover, the reported throughput time should be 1.5 hours instead of one hour.

A Shorter Integer-Programming Computer Program Applied to a One-Dimensional Space Allocation Problem

Jsun Yui Wong

Partly because of line 21 through line 32 and line 1631 through line 1639, the computer program listed below is shorter than the one in the September 7 post "An Integer-Programming Computer Program Applied to a One-Dimensional Space Allocation Problem" of the present blog.

0 DEFSNG A-Z
3 DEFINT I,J,K
4 REM
5 DIM X(466),A(466),L(466),K(466),P(466),B(466),S(466),J(466)
6 DIM T(11,11,5),TZ(11,11),TL(33),HT(33,33),TM(24,24),HR(24,24),HS(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 5,6,7,8,5,9,6,7,8,9,6,10,7,9,10,7,11,8,11,8,12,9,9,13,10,10,7,11
41 FOR IZ=1 TO 7
43 FOR JZ=IZ+1 TO 8
46 READ HS(IZ,JZ)
48 NEXT JZ
49 NEXT IZ
52 DATA 6,4,1,7,3,5,0,1,2,5,2,4,3,0,6,3,2,2,3,4,0,1,0,6,6,3,5,2
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR II=1 TO 8
88 A(II)=FIX(RND*99)
89 NEXT II
126 IMAR=10+FIX(RND*2000)
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*99)
533 FOR IX=1 TO 7
534 FOR JX=IX+1 TO 8
542 IF ABS(X(IX)-X(JX))-HR(IX,JX)<-.0001 THEN TM(IX,JX)=999999! 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
1631 SUMUL=0
1632 FOR IS1=1 TO 7
1634 FOR IS2=IS1+1 TO 8
1636 SUMUL=SUMUL+HS(IS1,IS2)*ABS(X(IS1)-X(IS2))
1637 NEXT IS2
1639 NEXT IS1
1645 P=-SUMUL-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>-1605 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 1.5 hours of running is presented below. What immediately follows is a manual copy from the computer screen.

48 53 30 7 40
15 63 22 -1602 -29841

44 39 62 85 52
77 29 70 -1602 -28965

65 70 47 24 57
32 80 39 -1602 -27466

1602 is optimal. Interpreted in accordance with line 1912 and line 1914, the output through JJJJ=-27466 was produced during the first 1.5 hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

References

Amaral, A. R. S., "On the exact solution of a facility layout problem," European Journal of Operational Research 173, 508-518 (2006).

Simmons, D. M., "One-dimensional space allocation: an ordering algorithm," Operations Research 17, 812-826 (1969).

A Computer Program for Scheduling to Minimize Interaction Cost

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).

A Shorter Computer Program for Relative Location of Three-Dimensional Facilities

Jsun Yui Wong

Because of line 252 through line 286 and line 533 through line 547, the computer programn listed below is shorter than the one in the October 24 post "A Computer Program for Relative Location of Three-Dimensional Facilities, Second Edition" of the present blog. The newer program and its earliest output are as follows:

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 100,120,110,120,170,130,90,120,110,120,170,130,90,130,140,190,150,110,130,180,140,100,190,150,110,200,160,120
41 FOR IW2=9 TO 15
42 FOR JW2=IW2+1 TO 16
43 READ HR(IW2,JW2)
44 NEXT JW2
45 NEXT IW2
46 DATA80,100,80,80,120,60,60,100,80,80,120,60,60,100,100,140,80,80,80,120,60,60,120,60,60,100,100,40
51 FOR IW3=17 TO 23
52 FOR JW3=IW3+1 TO 24
53 READ HR(IW3,JW3)
54 NEXT JW3
55 NEXT IW3
57 DATA 160,160,180,180,180,220,220,160,180,180,180,220,220,180,180,180,220,220,200,200,240,240,200,240,240,240,240,280
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 24
88 A(I)=FIX(RND*1000)
89 NEXT I
126 IMAR=10+FIX(RND*20000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 24
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*24)
234 X(IJL)=FIX(RND*1000)
252 FOR IY=1 TO 23
263 FOR JY=IY+1 TO 24
271 HT(IY,JY)=ABS(X(IY)-X(JY))-HR(IY,JY)
285 NEXT JY
286 NEXT IY
533 FOR IX=1 TO 7
534 FOR JX=IX+1 TO 8
541 IF HT(IX, JX)<-.0001 AND HT(IX+8,JX+8)<-.0001 AND HT(IX+16,JX+16)<-.0001 THEN TM(IX, JX)=999999! ELSE TM(IX,JX)=0
545 NEXT JX
547 NEXT IX
1611 SUMTL=0
1612 FOR IR1=1 TO 7
1613 REM
1614 FOR IR2=IR1+1 TO 8
1615 REM
1616 SUMTL=SUMTL+TM(IR1,IR2)
1617 NEXT IR2
1618 REM
1619 NEXT IR1
1621 PR1=-10*ABS(X(1)-X(2))-15*ABS(X(1)-X(3))-20*ABS(X(1)-X(4))-0*ABS(X(1)-X(5))-17*ABS(X(1)-X(6))-0*ABS(X(1)-X(7))-6*ABS(X(1)-X(8))
1622 PR2=-30*ABS(X(2)-X(3))-35*ABS(X(2)-X(4))-10*ABS(X(2)-X(5))-32*ABS(X(2)-X(6))-10*ABS(X(2)-X(7))-2*ABS(X(2)-X(8))
1631 PR3=-10*ABS(X(3)-X(4))-20*ABS(X(3)-X(5))-26*ABS(X(3)-X(6))-0*ABS(X(3)-X(7))-10*ABS(X(3)-X(8))
1632 PR4=-15*ABS(X(4)-X(5))-13*ABS(X(4)-X(6))-10*ABS(X(4)-X(7))-10*ABS(X(4)-X(8))
1633 PR5=-19*ABS(X(5)-X(6))-4*ABS(X(5)-X(7))-10*ABS(X(5)-X(8))-20*ABS(X(6)-X(7))-0*ABS(X(6)-X(8))-0*ABS(X(7)-X(8))
1636 REM
1643 PR8=-10*ABS(X(9)-X(10))-15*ABS(X(9)-X(11))-20*ABS(X(9)-X(12))-0*ABS(X(9)-X(13))-17*ABS(X(9)-X(14))-0*ABS(X(9)-X(15))-6*ABS(X(9)-X(16))
1644 PR9=-30*ABS(X(10)-X(11))-35*ABS(X(10)-X(12))-10*ABS(X(10)-X(13))-32*ABS(X(10)-X(14))-10*ABS(X(10)-X(15))-2*ABS(X(10)-X(16))
1645 PR10=-10*ABS(X(11)-X(12))-20*ABS(X(11)-X(13))-26*ABS(X(11)-X(14))-0*ABS(X(11)-X(15))-10*ABS(X(11)-X(16))
1646 PR11=-15*ABS(X(12)-X(13))-13*ABS(X(12)-X(14))-10*ABS(X(12)-X(15))-10*ABS(X(12)-X(16))
1647 PR12=-19*ABS(X(13)-X(14))-4*ABS(X(13)-X(15))-10*ABS(X(13)-X(16))-20*ABS(X(14)-X(15))-0*ABS(X(14)-X(16))-0*ABS(X(15)-X(16))
1650 PR13=-10*ABS(X(17)-X(18))-15*ABS(X(17)-X(19))-20*ABS(X(17)-X(20))-0*ABS(X(17)-X(21))-17*ABS(X(17)-X(22))-0*ABS(X(17)-X(23))-6*ABS(X(17)-X(24))
1651 PR14=-30*ABS(X(18)-X(19))-35*ABS(X(18)-X(20))-18*ABS(X(18)-X(21))-32*ABS(X(18)-X(22))-10*ABS(X(18)-X(23))-2*ABS(X(18)-X(24))
1652 PR15=-10*ABS(X(19)-X(20))-20*ABS(X(19)-X(21))-26*ABS(X(19)-X(22))-0*ABS(X(19)-X(23))-10*ABS(X(19)-X(24))
1653 PR16=-15*ABS(X(20)-X(21))-13*ABS(X(20)-X(22))-10*ABS(X(20)-X(23))-10*ABS(X(20)-X(24))
1654 PR17=-19*ABS(X(21)-X(22))-4*ABS(X(21)-X(23))-10*ABS(X(21)-X(24))-20*ABS(X(22)-X(23))-0*ABS(X(22)-X(24))-0*ABS(X(23)-X(24))
1655 P=PR1+PR2+PR3+PR4+PR5+PR8+PR9+PR10+PR11+PR12+PR13+PR14+PR15+PR16+PR17-999*SUMTL
1656 IF P<=M THEN 1670
1657 FOR KEW=1 TO 24
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1662 MM=PR1+PR2+PR3+PR4+PR5+PR8+PR9+PR10+PR11+PR12+PR13+PR14+PR15+PR16+PR17
1666 GOTO 128
1670 NEXT I
1890 IF M>-67450! THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),A(9),A(10)
1915 PRINT A(11),A(12),A(13),A(14),A(15)
1916 PRINT A(16),A(17),A(18),A(19),A(20)
1917 PRINT A(21),A(22),A(23),A(24)
1919 PRINT MM,M,JJJJ
1999 NEXT JJJJ

503 603 603 713 744
603 853 713 371 371
271 371 234 491 372
294 691 691 690 691
690 690 690 691
-67446 -67446 -32000

References

G. C. Armour and E. S. Buffa, "A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities," Management Science 9, 294-309 (1963).

S. S. Heragu. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.

A. R. S. Amaral, "An Exact Approach to the One-Dimensional Facility Layout Problem," Operations Research 56, 1026-1033 (2008).

A Shorter Computer Program for Relative Location of Spherical Facilities, Second Edition

Jsun Yui Wong

Because of line 333 through line 477 and line 522 through line 566, the computer programn listed below is shorter than the one in the post "A Computer Program for Relative Location of Spherical Facilities" of the present blog. The newer program and its earliest output are as follows:

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),HR(9,9)
6 DIM T(11,11,5),TZ(11,11),TL(33),HT(11,22)
21 FOR IW=1 TO 4
23 FOR JW=IW+1 TO 5
26 READ HR(IW,JW)
28 NEXT JW
29 NEXT IW
33 DATA 25.2312,30.8974,26.4353,27.5426,30.8974
38 DATA 26.4353,27.5426,32.1015,33.2088,28.7467
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 15
88 A(I)=RND*1000
89 NEXT I
126 IMAR=10+FIX(RND*20000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 15
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*15)
234 X(IJL)=RND*1000
333 FOR IX=1 TO 4
344 FOR JX=IX+1 TO 5
401 HT(IX,JX)=((X(IX)-X(JX))^2+(X(IX+5)-X(JX+5))^2+(X(IX+10)-X(JX+10))^2)^.5
455 NEXT JX
477 NEXT IX
522 FOR IY=1 TO 4
533 FOR JY=IY+1 TO 5
551 IF HT(IY,JY)-HR(IY,JY)<-.00001 THEN HT(IY,JY)=999999!
555 NEXT JY
566 NEXT IY
1621 PR1=-10*HT(1,2)-15*HT(1,3)-20*HT(1,4)-.01*HT(1,5)
1622 PR2=-30*HT(2,3)-35*HT(2,4)-10*HT(2,5)
1631 PR3=-10*HT(3,4)-20*HT(3,5)
1632 PR4=-15*HT(4,5)
1655 P=PR1+PR2+PR3+PR4
1656 IF P<=M THEN 1670
1657 FOR KEW=1 TO 15
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-4900 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),A(9),A(10)
1915 PRINT A(11),A(12),A(13),A(14),A(15)
1916 REM
1917 REM
1919 PRINT M,JJJJ
1999 NEXT JJJJ

660.8163 671.9393 664.7956 645.4153 656.898
754.6052 750.77 780.2496 751.776 763.7252
130.8193 154.4491 148.1102 152.1257 175.8217
-4859.761 -30413

One notes that the flow of .01 in line 1621 above is an artificial flow.

References

Drezner, Z. "DISCON: A New Method for the Layout Problem," Operations Research 28, 1375-1384 (1980).

Heragu, S. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.

A Shorter Computer Program for Relative Location of Spherical Facilities

Jsun Yui Wong

Because of line 333 through line 477, the computer programn listed below is shorter than the one in the preceding post of the present blog. The newer program and its earliest output are as follows:

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(11,22)
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 15
88 A(I)=RND*1000
89 NEXT I
126 IMAR=10+FIX(RND*20000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 15
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*15)
234 X(IJL)=RND*1000
333 FOR IX=1 TO 4
344 FOR JX=IX+1 TO 5
401 HT(IX,JX)=((X(IX)-X(JX))^2+(X(IX+5)-X(JX+5))^2+(X(IX+10)-X(JX+10))^2)^.5
455 NEXT JX
477 NEXT IX
651 IF HT(1,2)-25.2312<-.00001 THEN HT(1,2)=999999!
653 IF HT(1,3)-30.8974<-.00001 THEN HT(1,3)=999999!
654 IF HT(1,4)-26.4353<-.00001 THEN HT(1,4)=999999!
655 IF HT(1,5)-27.5426<-.00001 THEN HT(1,5)=999999!
665 IF HT(2,3)-30.8974<-.00001 THEN HT(2,3)=999999!
668 IF HT(2,4)-26.4353<-.00001 THEN HT(2,4)=999999!
669 IF HT(2,5)-27.5426<-.00001 THEN HT(2,5)=999999!
684 IF HT(3,4)-32.1015<-.00001 THEN HT(3,4)=999999!
685 IF HT(3,5)-33.2088<-.00001 THEN HT(3,5)=999999!
689 IF HT(4,5)-28.7467<-.00001 THEN HT(4,5)=999999!
1621 PR1=-10*HT(1,2)-15*HT(1,3)-20*HT(1,4)-.01*HT(1,5)
1622 PR2=-30*HT(2,3)-35*HT(2,4)-10*HT(2,5)
1631 PR3=-10*HT(3,4)-20*HT(3,5)
1632 PR4=-15*HT(4,5)
1655 P=PR1+PR2+PR3+PR4
1656 IF P<=M THEN 1670
1657 FOR KEW=1 TO 15
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-4900 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),A(9),A(10)
1915 PRINT A(11),A(12),A(13),A(14),A(15)
1916 REM
1917 REM
1919 PRINT M,JJJJ
1999 NEXT JJJJ

660.8163 671.9393 664.7956 645.4153 656.898
754.6052 750.77 780.2496 751.776 763.7252
130.8193 154.4491 148.1102 152.1257 175.8217
-4859.761 -30413

One notes that the flow of .01 in line 1621 above is an artificial flow.

References

Drezner, Z. "DISCON: A New Method for the Layout Problem," Operations Research 28, 1375-1384 (1980).

Heragu, S. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.

A Computer Program for Relative Location of Spherical Facilities

Jsun Yui Wong

The computer programn listed below is concerned with an extension of the assumption that "facilities have circular shapes, and that the distance between facilities is measured from center to center," Drezner (1980, p. 1375). In this paper the facilities are spheres of different sizes. For the following program for five facilities, the facility radii are 12.6156, 12.6156, 18.2818, 13.8197, and 14.9270. These radii are based on the rectangles of Heragu (2008, p. 220). Sums of pairs of radii are used in line 551 through line 589; from Heragu (2008), the flows are shown in line 1621 through line 1632 of the following program.

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)
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 15
88 A(I)=RND*1000
89 NEXT I
126 IMAR=10+FIX(RND*20000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 15
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*15)
234 X(IJL)=RND*1000
291 HS(1)=((X(1)-X(2))^2+(X(6)-X(7))^2+(X(11)-X(12))^2)^.5
292 HS(2)=((X(1)-X(3))^2+(X(6)-X(8))^2+(X(11)-X(13))^2)^.5
293 HS(3)=((X(1)-X(4))^2+(X(6)-X(9))^2+(X(11)-X(14))^2)^.5
294 HS(4)=((X(1)-X(5))^2+(X(6)-X(10))^2+(X(11)-X(15))^2)^.5
295 HS(5)=((X(2)-X(3))^2+(X(7)-X(8))^2+(X(12)-X(13))^2)^.5
296 HS(6)=((X(2)-X(4))^2+(X(7)-X(9))^2+(X(12)-X(14))^2)^.5
297 HS(7)=((X(2)-X(5))^2+(X(7)-X(10))^2+(X(12)-X(15))^2)^.5
298 HS(8)=((X(3)-X(4))^2+(X(8)-X(9))^2+(X(13)-X(14))^2)^.5
299 HS(9)=((X(3)-X(5))^2+(X(8)-X(10))^2+(X(13)-X(15))^2)^.5
300 HS(10)=((X(4)-X(5))^2+(X(9)-X(10))^2+(X(14)-X(15))^2)^.5
551 IF HS(1)-25.2312<-.00001 THEN HS(1)=999999!
553 IF HS(2)-30.8974<-.00001 THEN HS(2)=999999!
554 IF HS(3)-26.4353<-.00001 THEN HS(3)=999999!
555 IF HS(4)-27.5426<-.00001 THEN HS(4)=999999!
565 IF HS(5)-30.8974<-.00001 THEN HS(5)=999999!
568 IF HS(6)-26.4353<-.00001 THEN HS(6)=999999!
569 IF HS(7)-27.5426<-.00001 THEN HS(7)=999999!
584 IF HS(8)-32.1015<-.00001 THEN HS(8)=999999!
585 IF HS(9)-33.2088<-.00001 THEN HS(9)=999999!
589 IF HS(10)-28.7467<-.00001 THEN HS(10)=999999!
1621 PR1=-10*HS(1)-15*HS(2)-20*HS(3)-.01*HS(4)
1622 PR2=-30*HS(5)-35*HS(6)-10*HS(7)
1631 PR3=-10*HS(8)-20*HS(9)
1632 PR4=-15*HS(10)
1655 P=PR1+PR2+PR3+PR4
1656 IF P<=M THEN 1670
1657 FOR KEW=1 TO 15
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-4900 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),A(9),A(10)
1915 PRINT A(11),A(12),A(13),A(14),A(15)
1916 REM
1917 REM
1919 PRINT M,JJJJ
1999 NEXT JJJJ

One notes that the flow of .01 in line 1621 above is an artificial flow.

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, and the best candidate solutions produced during the first ten hours of running are presented below. What immediately follows is a manual copy from the computer screen.

660.8163 671.9393 664.7956 645.4153 656.898
754.6052 750.77 780.2496 751.776 763.7252
130.8193 154.4491 148.1102 152.1257 175.8217
-4859.761 -30413

307.2313 324.6127 336.2557 325.9749 350.9761
887.4272 870.5788 898.0033 872.8292 867.5846
762.154 747.3267 755.9315 773.7556 760.2586
-4880.799 -29546

Interpreted in accordance with line 1912 through line 1919, the candidate solutions above were produced during the first ten hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter, which is not a compiler.

References

Z. Drezner, "DISCON: A New Method for the Layout Problem," Operations Research 28, 1375-1384 (1980).

S. S. Heragu. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.

A Computer Program for Relative Location of Circular Facilities

Jsun Yui Wong

The computer programn listed below assumes that "facilities have circular shapes, and that the distance between facilities is measured from center to center," Drezner (1980, p. 1375). For the following program for five facilities, the facility radii are 12.6156, 12.6156, 18.2818, 13.8197, and 14.9270. These radii are based on the rectangles of Heragu (2008, p. 220). Sums of pairs of radii are used in line 551 through line 589; from Heragu (2008), the flows are shown in line 1621 through line 1632 of the following program.

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)
65 FOR JJJJ=-32000 TO 32000
74 RANDOMIZE JJJJ
76 M=-1D+17
85 FOR I=1 TO 10
88 A(I)=RND*1000
89 NEXT I
126 IMAR=10+FIX(RND*20000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 10
131 X(KK)=A(KK)
132 NEXT KK
223 IJL=1+FIX(RND*10)
234 X(IJL)=RND*1000
291 HS(1)=((X(1)-X(2))^2+(X(6)-X(7))^2)^.5
292 HS(2)=((X(1)-X(3))^2+(X(6)-X(8))^2)^.5
293 HS(3)=((X(1)-X(4))^2+(X(6)-X(9))^2)^.5
294 HS(4)=((X(1)-X(5))^2+(X(6)-X(10))^2)^.5
295 HS(5)=((X(2)-X(3))^2+(X(7)-X(8))^2)^.5
296 HS(6)=((X(2)-X(4))^2+(X(7)-X(9))^2)^.5
297 HS(7)=((X(2)-X(5))^2+(X(7)-X(10))^2)^.5
298 HS(8)=((X(3)-X(4))^2+(X(8)-X(9))^2)^.5
299 HS(9)=((X(3)-X(5))^2+(X(8)-X(10))^2)^.5
300 HS(10)=((X(4)-X(5))^2+(X(9)-X(10))^2)^.5
551 IF HS(1)-25.2312<-.00001 THEN HS(1)=999999!
553 IF HS(2)-30.8974<-.00001 THEN HS(2)=999999!
554 IF HS(3)-26.4353<-.00001 THEN HS(3)=999999!
555 IF HS(4)-27.5426<-.00001 THEN HS(4)=999999!
565 IF HS(5)-30.8974<-.00001 THEN HS(5)=999999!
568 IF HS(6)-26.4353<-.00001 THEN HS(6)=999999!
569 IF HS(7)-27.5426<-.00001 THEN HS(7)=999999!
584 IF HS(8)-32.1015<-.00001 THEN HS(8)=999999!
585 IF HS(9)-33.2088<-.00001 THEN HS(9)=999999!
589 IF HS(10)-28.7467<-.00001 THEN HS(10)=999999!
1621 PR1=-10*HS(1)-15*HS(2)-20*HS(3)-.01*HS(4)
1622 PR2=-30*HS(5)-35*HS(6)-10*HS(7)
1631 PR3=-10*HS(8)-20*HS(9)
1632 PR4=-15*HS(10)
1655 P=PR1+PR2+PR3+PR4
1656 IF P<=M THEN 1670
1657 FOR KEW=1 TO 10
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-5400 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1914 PRINT A(6),A(7),A(8),A(9),A(10)
1915 REM
1916 REM
1917 REM
1919 PRINT M,JJJJ
1999 NEXT JJJJ

One notes that the flow of .01 in line 1621 above is an artificial flow.

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter, and the best candidate solutions produced during the first ten hours of running are presented below. What immediately follows is a manual copy from the computer screen.

556.7183 534.6341 505.9124 533.788 509.3705
644.7668 658.6841 649.2176 631.5781 616.2713
-5369.511 -31610

138.7942 134.8886 155.6561 159.9009 184.9188
872.151 897.4762 920.3549 888.4004 904.4385
-5353.261 -30343

Interpreted in accordance with line 1912 through line 1919, the candidate solutions above were produced during the first ten hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter, which is not a compiler.

References

Z. Drezner, "DISCON: A New Method for the Layout Problem," Operations Research 28, 1375-1384 (1980).

S. S. Heragu. Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.