Jsun Yui Wong
The difference between the original Carlson and Nemhauser problem [1] and the problem of Davis, Devine, and Lutz [2] is "that their problem did not consider conflicting facilities," Davis, Devine, and Lutz [2, p. 225]. For the newer problem, "a cost is incurred if two activities are assigned to the same facility, or to two facilities whose operation is in conflict," Davis et al. [2, p. 224]. Dealing with an instance of the newer problem, the computer program below attempts to find the lowest cost of scheduling twenty-five courses in four time periods which are 8 a.m. to 11 a.m., 10 a.m. to 1 p.m., noon to 3 p.m., and 2 p.m. to 5 p.m. The conflicts are specified in line 6 through line 9 of the following computer program.
The costs used in line 1001 through line 1300 of the computer program below come from Hillier [3] and Nugent, Vollmann, and Ruml [4, pp. 168-170].
In this paper, A(1)=1, A(2)=1, A(3)=1,..., and A(25)=1 stand for course 1 in period 1, course 2 in period 1, course 3 in period 1,..., and course 25 in period 1, respectively.
The computer program below is modelled after the computer program of the March 7 post "Assigning Activities to Conflicting Facilities To Minimize Conflict Cost" of the present blog.
2 DEFINT A-Z
4 DEFDBL M,T,P
5 DIM N(9),B(9),A(199),H(99),X(199),P(450),L(99),U(99),Q(977),R(444),T(999),Q1(222)
6 TBM(1,1)=1:TBM(1,2)=1
7 TBM(2,1)=1:TBM(2,2)=1:TBM(2,3)=1
8 TBM(3,2)=1:TBM(3,3)=1:TBM(3,4)=1
9 TBM(4,3)=1:TBM(4,4)=1
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
91 FOR IAP0=1 TO 25
92 A(IAP0)=1+FIX(RND*4)
93 NEXT IAP0
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 25
131 X(K)=A(K)
132 NEXT K
241 IAP1=1+FIX(RND*25)
243 X(IAP1)=1+FIX(RND*4)
1001 T(1)=5*100000!*(1/(100000!*(1-TBM(X(1),X(2)))+1))
1002 T(2)=2*100000!*(1/(100000!*(1-TBM(X(1),X(3)))+1))
1003 T(3)=4*100000!*(1/(100000!*(1-TBM(X(1),X(4)))+1))
1004 T(4)=1*100000!*(1/(100000!*(1-TBM(X(1),X(5)))+1))
1005 T(5)=0*100000!*(1/(100000!*(1-TBM(X(1),X(6)))+1))
1006 T(6)=0*100000!*(1/(100000!*(1-TBM(X(1),X(7)))+1))
1007 T(7)=6*100000!*(1/(100000!*(1-TBM(X(1),X(8)))+1))
1008 T(8)=2*100000!*(1/(100000!*(1-TBM(X(1),X(9)))+1))
1009 T(9)=1*100000!*(1/(100000!*(1-TBM(X(1),X(10)))+1))
1010 T(10)=1*100000!*(1/(100000!*(1-TBM(X(1),X(11)))+1))
1011 T(11)=1*100000!*(1/(100000!*(1-TBM(X(1),X(12)))+1))
1012 T(12)=3*100000!*(1/(100000!*(1-TBM(X(2),X(3)))+1))
1013 T(13)=0*100000!*(1/(100000!*(1-TBM(X(2),X(4)))+1))
1014 T(14)=2*100000!*(1/(100000!*(1-TBM(X(2),X(5)))+1))
1015 T(15)=2*100000!*(1/(100000!*(1-TBM(X(2),X(6)))+1))
1016 T(16)=2*100000!*(1/(100000!*(1-TBM(X(2),X(7)))+1))
1017 T(17)=0*100000!*(1/(100000!*(1-TBM(X(2),X(8)))+1))
1018 T(18)=4*100000!*(1/(100000!*(1-TBM(X(2),X(9)))+1))
1019 T(19)=5*100000!*(1/(100000!*(1-TBM(X(2),X(10)))+1))
1020 T(20)=0*100000!*(1/(100000!*(1-TBM(X(2),X(11)))+1))
1021 T(21)=0*100000!*(1/(100000!*(1-TBM(X(2),X(12)))+1))
1022 T(22)=0*100000!*(1/(100000!*(1-TBM(X(3),X(4)))+1))
1023 T(23)=0*100000!*(1/(100000!*(1-TBM(X(3),X(5)))+1))
1024 T(24)=0*100000!*(1/(100000!*(1-TBM(X(3),X(6)))+1))
1025 T(25)=0*100000!*(1/(100000!*(1-TBM(X(3),X(7)))+1))
1026 T(26)=5*100000!*(1/(100000!*(1-TBM(X(3),X(8)))+1))
1027 T(27)=5*100000!*(1/(100000!*(1-TBM(X(3),X(9)))+1))
1028 T(28)=2*100000!*(1/(100000!*(1-TBM(X(3),X(10)))+1))
1029 T(29)=2*100000!*(1/(100000!*(1-TBM(X(3),X(11)))+1))
1030 T(30)=2*100000!*(1/(100000!*(1-TBM(X(3),X(12)))+1))
1031 T(31)=5*100000!*(1/(100000!*(1-TBM(X(4),X(5)))+1))
1032 T(32)=2*100000!*(1/(100000!*(1-TBM(X(4),X(6)))+1))
1033 T(33)=2*100000!*(1/(100000!*(1-TBM(X(4),X(7)))+1))
1034 T(34)=10*100000!*(1/(100000!*(1-TBM(X(4),X(8)))+1))
1035 T(35)=0*100000!*(1/(100000!*(1-TBM(X(4),X(9)))+1))
1036 T(36)=0*100000!*(1/(100000!*(1-TBM(X(4),X(10)))+1))
1037 T(37)=5*100000!*(1/(100000!*(1-TBM(X(4),X(11)))+1))
1038 T(38)=5*100000!*(1/(100000!*(1-TBM(X(4),X(12)))+1))
1039 T(39)=10*100000!*(1/(100000!*(1-TBM(X(5),X(6)))+1))
1040 T(40)=0*100000!*(1/(100000!*(1-TBM(X(5),X(7)))+1))
1041 T(41)=0*100000!*(1/(100000!*(1-TBM(X(5),X(8)))+1))
1042 T(42)=0*100000!*(1/(100000!*(1-TBM(X(5),X(9)))+1))
1043 T(43)=5*100000!*(1/(100000!*(1-TBM(X(5),X(10)))+1))
1044 T(44)=1*100000!*(1/(100000!*(1-TBM(X(5),X(11)))+1))
1045 T(45)=1*100000!*(1/(100000!*(1-TBM(X(5),X(12)))+1))
1046 T(46)=5*100000!*(1/(100000!*(1-TBM(X(6),X(7)))+1))
1047 T(47)=1*100000!*(1/(100000!*(1-TBM(X(6),X(8)))+1))
1048 T(48)=1*100000!*(1/(100000!*(1-TBM(X(6),X(9)))+1))
1049 T(49)=5*100000!*(1/(100000!*(1-TBM(X(6),X(10)))+1))
1050 T(50)=4*100000!*(1/(100000!*(1-TBM(X(6),X(11)))+1))
1051 T(51)=0*100000!*(1/(100000!*(1-TBM(X(6),X(12)))+1))
1052 T(52)=10*100000!*(1/(100000!*(1-TBM(X(7),X(8)))+1))
1053 T(53)=5*100000!*(1/(100000!*(1-TBM(X(7),X(9)))+1))
1054 T(54)=2*100000!*(1/(100000!*(1-TBM(X(7),X(10)))+1))
1055 T(55)=3*100000!*(1/(100000!*(1-TBM(X(7),X(11)))+1))
1056 T(56)=3*100000!*(1/(100000!*(1-TBM(X(7),X(12)))+1))
1057 T(57)=0*100000!*(1/(100000!*(1-TBM(X(8),X(9)))+1))
1058 T(58)=0*100000!*(1/(100000!*(1-TBM(X(8),X(10)))+1))
1059 T(59)=5*100000!*(1/(100000!*(1-TBM(X(8),X(11)))+1))
1060 T(60)=0*100000!*(1/(100000!*(1-TBM(X(8),X(12)))+1))
1061 T(61)=0*100000!*(1/(100000!*(1-TBM(X(9),X(10)))+1))
1062 T(62)=10*100000!*(1/(100000!*(1-TBM(X(9),X(11)))+1))
1063 T(63)=10*100000!*(1/(100000!*(1-TBM(X(9),X(12)))+1))
1064 T(64)=5*100000!*(1/(100000!*(1-TBM(X(10),X(11)))+1))
1065 T(65)=0*100000!*(1/(100000!*(1-TBM(X(10),X(12)))+1))
1066 T(66)=2*100000!*(1/(100000!*(1-TBM(X(11),X(12)))+1))
1067 T(67)=4*100000!*(1/(100000!*(1-TBM(X(13),X(1)))+1))
1068 T(68)=10*100000!*(1/(100000!*(1-TBM(X(13),X(2)))+1))
1069 T(69)=5*100000!*(1/(100000!*(1-TBM(X(13),X(3)))+1))
1070 T(70)=2*100000!*(1/(100000!*(1-TBM(X(13),X(4)))+1))
1071 T(71)=0*100000!*(1/(100000!*(1-TBM(X(13),X(5)))+1))
1072 T(72)=2*100000!*(1/(100000!*(1-TBM(X(13),X(6)))+1))
1073 T(73)=5*100000!*(1/(100000!*(1-TBM(X(13),X(7)))+1))
1074 T(74)=5*100000!*(1/(100000!*(1-TBM(X(13),X(8)))+1))
1075 T(75)=10*100000!*(1/(100000!*(1-TBM(X(13),X(9)))+1))
1076 T(76)=0*100000!*(1/(100000!*(1-TBM(X(13),X(10)))+1))
1077 T(77)=0*100000!*(1/(100000!*(1-TBM(X(13),X(11)))+1))
1078 T(78)=3*100000!*(1/(100000!*(1-TBM(X(13),X(12)))+1))
1079 T(79)=0*100000!*(1/(100000!*(1-TBM(X(14),X(1)))+1))
1080 T(80)=5*100000!*(1/(100000!*(1-TBM(X(14),X(2)))+1))
1081 T(81)=5*100000!*(1/(100000!*(1-TBM(X(14),X(3)))+1))
1082 T(82)=5*100000!*(1/(100000!*(1-TBM(X(14),X(4)))+1))
1083 T(83)=5*100000!*(1/(100000!*(1-TBM(X(14),X(5)))+1))
1084 T(84)=5*100000!*(1/(100000!*(1-TBM(X(14),X(6)))+1))
1085 T(85)=1*100000!*(1/(100000!*(1-TBM(X(14),X(7)))+1))
1086 T(86)=0*100000!*(1/(100000!*(1-TBM(X(14),X(8)))+1))
1087 T(87)=0*100000!*(1/(100000!*(1-TBM(X(14),X(9)))+1))
1088 T(88)=0*100000!*(1/(100000!*(1-TBM(X(14),X(10)))+1))
1089 T(89)=5*100000!*(1/(100000!*(1-TBM(X(14),X(11)))+1))
1090 T(90)=3*100000!*(1/(100000!*(1-TBM(X(14),X(12)))+1))
1091 T(91)=10*100000!*(1/(100000!*(1-TBM(X(14),X(13)))+1))
1092 T(92)=0*100000!*(1/(100000!*(1-TBM(X(15),X(1)))+1))
1093 T(93)=0*100000!*(1/(100000!*(1-TBM(X(15),X(2)))+1))
1094 T(94)=5*100000!*(1/(100000!*(1-TBM(X(15),X(3)))+1))
1095 T(95)=0*100000!*(1/(100000!*(1-TBM(X(15),X(4)))+1))
1096 T(96)=5*100000!*(1/(100000!*(1-TBM(X(15),X(5)))+1))
1097 T(97)=10*100000!*(1/(100000!*(1-TBM(X(15),X(6)))+1))
1098 T(98)=0*100000!*(1/(100000!*(1-TBM(X(15),X(7)))+1))
1099 T(99)=0*100000!*(1/(100000!*(1-TBM(X(15),X(8)))+1))
1100 T(100)=2*100000!*(1/(100000!*(1-TBM(X(15),X(9)))+1))
1101 T(101)=5*100000!*(1/(100000!*(1-TBM(X(15),X(10)))+1))
1102 T(102)=0*100000!*(1/(100000!*(1-TBM(X(15),X(11)))+1))
1103 T(103)=0*100000!*(1/(100000!*(1-TBM(X(15),X(12)))+1))
1104 T(104)=2*100000!*(1/(100000!*(1-TBM(X(15),X(13)))+1))
1105 T(105)=4*100000!*(1/(100000!*(1-TBM(X(15),X(14)))+1))
1106 T(106)=0*100000!*(1/(100000!*(1-TBM(X(16),X(1)))+1))
1107 T(107)=0*100000!*(1/(100000!*(1-TBM(X(16),X(2)))+1))
1108 T(108)=4*100000!*(1/(100000!*(1-TBM(X(16),X(3)))+1))
1109 T(109)=5*100000!*(1/(100000!*(1-TBM(X(16),X(4)))+1))
1110 T(110)=0*100000!*(1/(100000!*(1-TBM(X(16),X(5)))+1))
1111 T(111)=5*100000!*(1/(100000!*(1-TBM(X(16),X(6)))+1))
1112 T(112)=10*100000!*(1/(100000!*(1-TBM(X(16),X(7)))+1))
1113 T(113)=4*100000!*(1/(100000!*(1-TBM(X(16),X(8)))+1))
1114 T(114)=3*100000!*(1/(100000!*(1-TBM(X(16),X(9)))+1))
1115 T(115)=5*100000!*(1/(100000!*(1-TBM(X(16),X(10)))+1))
1116 T(116)=1*100000!*(1/(100000!*(1-TBM(X(16),X(11)))+1))
1117 T(117)=0*100000!*(1/(100000!*(1-TBM(X(16),X(12)))+1))
1118 T(118)=4*100000!*(1/(100000!*(1-TBM(X(16),X(13)))+1))
1119 T(119)=1*100000!*(1/(100000!*(1-TBM(X(16),X(14)))+1))
1120 T(120)=4*100000!*(1/(100000!*(1-TBM(X(16),X(15)))+1))
1121 T(121)=5*100000!*(1/(100000!*(1-TBM(X(17),X(1)))+1))
1122 T(122)=0*100000!*(1/(100000!*(1-TBM(X(17),X(2)))+1))
1123 T(123)=0*100000!*(1/(100000!*(1-TBM(X(17),X(3)))+1))
1124 T(124)=1*100000!*(1/(100000!*(1-TBM(X(17),X(4)))+1))
1125 T(125)=2*100000!*(1/(100000!*(1-TBM(X(17),X(5)))+1))
1126 T(126)=0*100000!*(1/(100000!*(1-TBM(X(17),X(6)))+1))
1127 T(127)=2*100000!*(1/(100000!*(1-TBM(X(17),X(7)))+1))
1128 T(128)=5*100000!*(1/(100000!*(1-TBM(X(17),X(8)))+1))
1129 T(129)=0*100000!*(1/(100000!*(1-TBM(X(17),X(9)))+1))
1130 T(130)=5*100000!*(1/(100000!*(1-TBM(X(17),X(10)))+1))
1131 T(131)=0*100000!*(1/(100000!*(1-TBM(X(17),X(11)))+1))
1132 T(132)=0*100000!*(1/(100000!*(1-TBM(X(17),X(12)))+1))
1133 T(133)=2*100000!*(1/(100000!*(1-TBM(X(17),X(13)))+1))
1134 T(134)=0*100000!*(1/(100000!*(1-TBM(X(17),X(14)))+1))
1135 T(135)=5*100000!*(1/(100000!*(1-TBM(X(17),X(15)))+1))
1136 T(136)=0*100000!*(1/(100000!*(1-TBM(X(17),X(16)))+1))
1137 T(137)=6*100000!*(1/(100000!*(1-TBM(X(18),X(1)))+1))
1138 T(138)=2*100000!*(1/(100000!*(1-TBM(X(18),X(2)))+1))
1139 T(139)=6*100000!*(1/(100000!*(1-TBM(X(18),X(3)))+1))
1140 T(140)=1*100000!*(1/(100000!*(1-TBM(X(18),X(4)))+1))
1141 T(141)=1*100000!*(1/(100000!*(1-TBM(X(18),X(5)))+1))
1142 T(142)=5*100000!*(1/(100000!*(1-TBM(X(18),X(6)))+1))
1143 T(143)=1*100000!*(1/(100000!*(1-TBM(X(18),X(7)))+1))
1144 T(144)=2*100000!*(1/(100000!*(1-TBM(X(18),X(8)))+1))
1145 T(145)=2*100000!*(1/(100000!*(1-TBM(X(18),X(9)))+1))
1146 T(146)=0*100000!*(1/(100000!*(1-TBM(X(18),X(10)))+1))
1147 T(147)=2*100000!*(1/(100000!*(1-TBM(X(18),X(11)))+1))
1148 T(148)=0*100000!*(1/(100000!*(1-TBM(X(18),X(12)))+1))
1149 T(149)=2*100000!*(1/(100000!*(1-TBM(X(18),X(13)))+1))
1150 T(150)=5*100000!*(1/(100000!*(1-TBM(X(18),X(14)))+1))
1151 T(151)=1*100000!*(1/(100000!*(1-TBM(X(18),X(15)))+1))
1152 T(152)=3*100000!*(1/(100000!*(1-TBM(X(18),X(16)))+1))
1153 T(153)=2*100000!*(1/(100000!*(1-TBM(X(18),X(17)))+1))
1154 T(154)=3*100000!*(1/(100000!*(1-TBM(X(19),X(1)))+1))
1155 T(155)=0*100000!*(1/(100000!*(1-TBM(X(19),X(2)))+1))
1156 T(156)=3*100000!*(1/(100000!*(1-TBM(X(19),X(3)))+1))
1157 T(157)=1*100000!*(1/(100000!*(1-TBM(X(19),X(4)))+1))
1158 T(158)=0*100000!*(1/(100000!*(1-TBM(X(19),X(5)))+1))
1159 T(159)=0*100000!*(1/(100000!*(1-TBM(X(19),X(6)))+1))
1160 T(160)=10*100000!*(1/(100000!*(1-TBM(X(19),X(7)))+1))
1161 T(161)=10*100000!*(1/(100000!*(1-TBM(X(19),X(8)))+1))
1162 T(162)=0*100000!*(1/(100000!*(1-TBM(X(19),X(9)))+1))
1163 T(163)=5*100000!*(1/(100000!*(1-TBM(X(19),X(10)))+1))
1164 T(164)=0*100000!*(1/(100000!*(1-TBM(X(19),X(11)))+1))
1165 T(165)=0*100000!*(1/(100000!*(1-TBM(X(19),X(12)))+1))
1166 T(166)=1*100000!*(1/(100000!*(1-TBM(X(19),X(13)))+1))
1167 T(167)=3*100000!*(1/(100000!*(1-TBM(X(19),X(14)))+1))
1168 T(168)=0*100000!*(1/(100000!*(1-TBM(X(19),X(15)))+1))
1169 T(169)=0*100000!*(1/(100000!*(1-TBM(X(19),X(16)))+1))
1170 T(170)=2*100000!*(1/(100000!*(1-TBM(X(19),X(17)))+1))
1171 T(171)=5*100000!*(1/(100000!*(1-TBM(X(19),X(18)))+1))
1172 T(172)=0*100000!*(1/(100000!*(1-TBM(X(20),X(1)))+1))
1173 T(173)=1*100000!*(1/(100000!*(1-TBM(X(20),X(2)))+1))
1174 T(174)=2*100000!*(1/(100000!*(1-TBM(X(20),X(3)))+1))
1175 T(175)=1*100000!*(1/(100000!*(1-TBM(X(20),X(4)))+1))
1176 T(176)=0*100000!*(1/(100000!*(1-TBM(X(20),X(5)))+1))
1177 T(177)=0*100000!*(1/(100000!*(1-TBM(X(20),X(6)))+1))
1178 T(178)=1*100000!*(1/(100000!*(1-TBM(X(20),X(7)))+1))
1179 T(179)=6*100000!*(1/(100000!*(1-TBM(X(20),X(8)))+1))
1180 T(180)=0*100000!*(1/(100000!*(1-TBM(X(20),X(9)))+1))
1181 T(181)=2*100000!*(1/(100000!*(1-TBM(X(20),X(10)))+1))
1182 T(182)=0*100000!*(1/(100000!*(1-TBM(X(20),X(11)))+1))
1183 T(183)=2*100000!*(1/(100000!*(1-TBM(X(20),X(12)))+1))
1184 T(184)=0*100000!*(1/(100000!*(1-TBM(X(20),X(13)))+1))
1185 T(185)=10*100000!*(1/(100000!*(1-TBM(X(20),X(14)))+1))
1186 T(186)=1*100000!*(1/(100000!*(1-TBM(X(20),X(15)))+1))
1187 T(187)=2*100000!*(1/(100000!*(1-TBM(X(20),X(16)))+1))
1188 T(188)=0*100000!*(1/(100000!*(1-TBM(X(20),X(17)))+1))
1189 T(189)=1*100000!*(1/(100000!*(1-TBM(X(20),X(18)))+1))
1190 T(190)=0*100000!*(1/(100000!*(1-TBM(X(20),X(19)))+1))
1191 T(191)=1*100000!*(1/(100000!*(1-TBM(X(21),X(1)))+1))
1192 T(192)=6*100000!*(1/(100000!*(1-TBM(X(21),X(2)))+1))
1193 T(193)=5*100000!*(1/(100000!*(1-TBM(X(21),X(3)))+1))
1194 T(194)=2*100000!*(1/(100000!*(1-TBM(X(21),X(4)))+1))
1195 T(195)=2*100000!*(1/(100000!*(1-TBM(X(21),X(5)))+1))
1196 T(196)=0*100000!*(1/(100000!*(1-TBM(X(21),X(6)))+1))
1197 T(197)=5*100000!*(1/(100000!*(1-TBM(X(21),X(7)))+1))
1198 T(198)=0*100000!*(1/(100000!*(1-TBM(X(21),X(8)))+1))
1199 T(199)=4*100000!*(1/(100000!*(1-TBM(X(21),X(9)))+1))
1200 T(200)=3*100000!*(1/(100000!*(1-TBM(X(21),X(10)))+1))
1201 T(201)=0*100000!*(1/(100000!*(1-TBM(X(21),X(11)))+1))
1202 T(202)=0*100000!*(1/(100000!*(1-TBM(X(21),X(12)))+1))
1203 T(203)=6*100000!*(1/(100000!*(1-TBM(X(21),X(13)))+1))
1204 T(204)=0*100000!*(1/(100000!*(1-TBM(X(21),X(14)))+1))
1205 T(205)=0*100000!*(1/(100000!*(1-TBM(X(21),X(15)))+1))
1206 T(206)=2*100000!*(1/(100000!*(1-TBM(X(21),X(16)))+1))
1207 T(207)=0*100000!*(1/(100000!*(1-TBM(X(21),X(17)))+1))
1208 T(208)=2*100000!*(1/(100000!*(1-TBM(X(21),X(18)))+1))
1209 T(209)=5*100000!*(1/(100000!*(1-TBM(X(21),X(19)))+1))
1210 T(210)=5*100000!*(1/(100000!*(1-TBM(X(21),X(20)))+1))
1211 T(211)=10*100000!*(1/(100000!*(1-TBM(X(22),X(1)))+1))
1212 T(212)=1*100000!*(1/(100000!*(1-TBM(X(22),X(2)))+1))
1213 T(213)=5*100000!*(1/(100000!*(1-TBM(X(22),X(3)))+1))
1214 T(214)=2*100000!*(1/(100000!*(1-TBM(X(22),X(4)))+1))
1215 T(215)=0*100000!*(1/(100000!*(1-TBM(X(22),X(5)))+1))
1216 T(216)=10*100000!*(1/(100000!*(1-TBM(X(22),X(6)))+1))
1217 T(217)=5*100000!*(1/(100000!*(1-TBM(X(22),X(7)))+1))
1218 T(218)=5*100000!*(1/(100000!*(1-TBM(X(22),X(8)))+1))
1219 T(219)=0*100000!*(1/(100000!*(1-TBM(X(22),X(9)))+1))
1220 T(220)=5*100000!*(1/(100000!*(1-TBM(X(22),X(10)))+1))
1221 T(221)=6*100000!*(1/(100000!*(1-TBM(X(22),X(11)))+1))
1222 T(222)=4*100000!*(1/(100000!*(1-TBM(X(22),X(12)))+1))
1223 T(223)=2*100000!*(1/(100000!*(1-TBM(X(22),X(13)))+1))
1224 T(224)=0*100000!*(1/(100000!*(1-TBM(X(22),X(14)))+1))
1225 T(225)=5*100000!*(1/(100000!*(1-TBM(X(22),X(15)))+1))
1226 T(226)=0*100000!*(1/(100000!*(1-TBM(X(22),X(16)))+1))
1227 T(227)=0*100000!*(1/(100000!*(1-TBM(X(22),X(17)))+1))
1228 T(228)=10*100000!*(1/(100000!*(1-TBM(X(22),X(18)))+1))
1229 T(229)=5*100000!*(1/(100000!*(1-TBM(X(22),X(19)))+1))
1230 T(230)=2*100000!*(1/(100000!*(1-TBM(X(22),X(20)))+1))
1231 T(231)=4*100000!*(1/(100000!*(1-TBM(X(22),X(21)))+1))
1232 T(232)=0*100000!*(1/(100000!*(1-TBM(X(23),X(1)))+1))
1233 T(233)=0*100000!*(1/(100000!*(1-TBM(X(23),X(2)))+1))
1234 T(234)=2*100000!*(1/(100000!*(1-TBM(X(23),X(3)))+1))
1235 T(235)=4*100000!*(1/(100000!*(1-TBM(X(23),X(4)))+1))
1236 T(236)=5*100000!*(1/(100000!*(1-TBM(X(23),X(5)))+1))
1237 T(237)=0*100000!*(1/(100000!*(1-TBM(X(23),X(6)))+1))
1238 T(238)=2*100000!*(1/(100000!*(1-TBM(X(23),X(7)))+1))
1239 T(239)=5*100000!*(1/(100000!*(1-TBM(X(23),X(8)))+1))
1240 T(240)=5*100000!*(1/(100000!*(1-TBM(X(23),X(9)))+1))
1241 T(241)=0*100000!*(1/(100000!*(1-TBM(X(23),X(10)))+1))
1242 T(242)=6*100000!*(1/(100000!*(1-TBM(X(23),X(11)))+1))
1243 T(243)=5*100000!*(1/(100000!*(1-TBM(X(23),X(12)))+1))
1244 T(244)=1*100000!*(1/(100000!*(1-TBM(X(23),X(13)))+1))
1245 T(245)=4*100000!*(1/(100000!*(1-TBM(X(23),X(14)))+1))
1246 T(246)=0*100000!*(1/(100000!*(1-TBM(X(23),X(15)))+1))
1247 T(247)=2*100000!*(1/(100000!*(1-TBM(X(23),X(16)))+1))
1248 T(248)=6*100000!*(1/(100000!*(1-TBM(X(23),X(17)))+1))
1249 T(249)=10*100000!*(1/(100000!*(1-TBM(X(23),X(18)))+1))
1250 T(250)=1*100000!*(1/(100000!*(1-TBM(X(23),X(19)))+1))
1251 T(251)=1*100000!*(1/(100000!*(1-TBM(X(23),X(20)))+1))
1252 T(252)=0*100000!*(1/(100000!*(1-TBM(X(23),X(21)))+1))
1253 T(253)=5*100000!*(1/(100000!*(1-TBM(X(23),X(22)))+1))
1254 T(254)=10*100000!*(1/(100000!*(1-TBM(X(24),X(1)))+1))
1255 T(255)=1*100000!*(1/(100000!*(1-TBM(X(24),X(2)))+1))
1256 T(256)=1*100000!*(1/(100000!*(1-TBM(X(24),X(3)))+1))
1257 T(257)=0*100000!*(1/(100000!*(1-TBM(X(24),X(4)))+1))
1258 T(258)=1*100000!*(1/(100000!*(1-TBM(X(24),X(5)))+1))
1259 T(259)=0*100000!*(1/(100000!*(1-TBM(X(24),X(6)))+1))
1260 T(260)=3*100000!*(1/(100000!*(1-TBM(X(24),X(7)))+1))
1261 T(261)=2*100000!*(1/(100000!*(1-TBM(X(24),X(8)))+1))
1262 T(262)=2*100000!*(1/(100000!*(1-TBM(X(24),X(9)))+1))
1263 T(263)=5*100000!*(1/(100000!*(1-TBM(X(24),X(10)))+1))
1264 T(264)=0*100000!*(1/(100000!*(1-TBM(X(24),X(11)))+1))
1265 T(265)=10*100000!*(1/(100000!*(1-TBM(X(24),X(12)))+1))
1266 T(266)=5*100000!*(1/(100000!*(1-TBM(X(24),X(13)))+1))
1267 T(267)=2*100000!*(1/(100000!*(1-TBM(X(24),X(14)))+1))
1268 T(268)=2*100000!*(1/(100000!*(1-TBM(X(24),X(15)))+1))
1269 T(269)=0*100000!*(1/(100000!*(1-TBM(X(24),X(16)))+1))
1270 T(270)=5*100000!*(1/(100000!*(1-TBM(X(24),X(17)))+1))
1271 T(271)=4*100000!*(1/(100000!*(1-TBM(X(24),X(18)))+1))
1272 T(272)=0*100000!*(1/(100000!*(1-TBM(X(24),X(19)))+1))
1273 T(273)=3*100000!*(1/(100000!*(1-TBM(X(24),X(20)))+1))
1274 T(274)=1*100000!*(1/(100000!*(1-TBM(X(24),X(21)))+1))
1275 T(275)=0*100000!*(1/(100000!*(1-TBM(X(24),X(22)))+1))
1276 T(276)=0*100000!*(1/(100000!*(1-TBM(X(24),X(23)))+1))
1277 T(277)=2*100000!*(1/(100000!*(1-TBM(X(25),X(1)))+1))
1278 T(278)=2*100000!*(1/(100000!*(1-TBM(X(25),X(2)))+1))
1279 T(279)=0*100000!*(1/(100000!*(1-TBM(X(25),X(3)))+1))
1280 T(280)=2*100000!*(1/(100000!*(1-TBM(X(25),X(4)))+1))
1281 T(281)=0*100000!*(1/(100000!*(1-TBM(X(25),X(5)))+1))
1282 T(282)=0*100000!*(1/(100000!*(1-TBM(X(25),X(6)))+1))
1283 T(283)=5*100000!*(1/(100000!*(1-TBM(X(25),X(7)))+1))
1284 T(284)=5*100000!*(1/(100000!*(1-TBM(X(25),X(8)))+1))
1285 T(285)=0*100000!*(1/(100000!*(1-TBM(X(25),X(9)))+1))
1286 T(286)=2*100000!*(1/(100000!*(1-TBM(X(25),X(10)))+1))
1287 T(287)=4*100000!*(1/(100000!*(1-TBM(X(25),X(11)))+1))
1288 T(288)=1*100000!*(1/(100000!*(1-TBM(X(25),X(12)))+1))
1289 T(289)=5*100000!*(1/(100000!*(1-TBM(X(25),X(13)))+1))
1290 T(290)=0*100000!*(1/(100000!*(1-TBM(X(25),X(14)))+1))
1291 T(291)=0*100000!*(1/(100000!*(1-TBM(X(25),X(15)))+1))
1292 T(292)=5*100000!*(1/(100000!*(1-TBM(X(25),X(16)))+1))
1293 T(293)=3*100000!*(1/(100000!*(1-TBM(X(25),X(17)))+1))
1294 T(294)=0*100000!*(1/(100000!*(1-TBM(X(25),X(18)))+1))
1295 T(295)=5*100000!*(1/(100000!*(1-TBM(X(25),X(19)))+1))
1296 T(296)=1*100000!*(1/(100000!*(1-TBM(X(25),X(20)))+1))
1297 T(297)=0*100000!*(1/(100000!*(1-TBM(X(25),X(21)))+1))
1298 T(298)=4*100000!*(1/(100000!*(1-TBM(X(25),X(22)))+1))
1299 T(299)=4*100000!*(1/(100000!*(1-TBM(X(25),X(23)))+1))
1300 T(300)=5*100000!*(1/(100000!*(1-TBM(X(25),X(24)))+1))
2151 P1NEW=0
2152 FOR KAU7=1 TO 300
2153 P1NEW=P1NEW+T(KAU7)
2154 NEXT KAU7
2450 P=-P1NEW
2451 IF P<=M THEN 2670
2657 FOR KEW=1 TO 25
2658 A(KEW)=X(KEW)
2659 NEXT KEW
2661 M=P
2666 GOTO 128
2670 NEXT I
2890 IF M>-27111111# THEN 2911 ELSE 2999
2911 PRINT A(1),A(2),A(3)
2912 PRINT A(4),A(5),A(6)
2913 PRINT A(7),A(8),A(9)
2914 PRINT A(10),A(11),A(12)
2915 PRINT A(13),A(14),A(15)
2916 PRINT A(16),A(17),A(18)
2917 PRINT A(19),A(20),A(21)
2918 PRINT A(22),A(23),A(24)
2925 PRINT A(25),JJJJ,M
2999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and its computational results, interpreted in accordance with line 2911 through line 2925, through JJJJ=-31764 are presented below.
4 1 1
1 4 1
4 4 3
4 1 4
1 4 3
1 1 4
2 1 4
1 1 1
4 -31951 -27000517.99482006
1 4 4
4 1 4
2 1 1
1 4 1
4 1 1
4 4 1
4 4 1
4 4 4
1 -31849 -27000517.99482006
4 2 1
1 4 2
4 4 4
4 1 4
1 4 4
1 1 4
1 2 4
2 1 1
4 -31848 -27000517.99482006
1 4 4
4 1 4
1 1 1
1 4 1
4 1 1
3 4 1
4 3 1
3 4 4
1 -31827 -27000517.99482006
1 3 3
4 1 4
1 1 1
1 4 1
4 1 1
3 4 1
4 4 1
4 3 4
1 -31824 -27000517.99482006
4 2 1
2 4 2
4 4 4
4 2 4
1 4 4
1 2 4
2 1 4
1 2 1
4 -31764 -27000517.99482006
The candidate solution above at JJJJ=-31951 reveals the assignment of courses 2, 3, 4, 6, 11, 13, 16, 17, 20, 22, 23, and 24 to period 1, course 19 to period 2, courses 9 and 15 to period 3, and courses 1, 5, 7, 8, 10, 12, 14, 18, 21, and 25 to period 4 for the total cost of 270.
These solutions were produced in 7 minutes on a personal computer with an Intel 2.66 GHz. chip and the IBM interpreter, which is slower than the corresponding compiler.
References
[1] R. C. Carlson, G. L. Nemhauser, Scheduling to minimize interaction cost, Operations Research 14 (1966) 52-58.
[2] F. E. Davis, M. D. Devine, R. P. Lutz, Scheduling activities among conflicting facilities to minimize conflict, Mathematical Programming 6 (1974) 224-228.
[3] F. S. Hillier, Quantitative tools for plant layout analysis, J. Indust. Eng. 14 (1963) 33-40.
[4] C. E. Nugent, T. E. Vollmann, J. Ruml, An experimental comparison of techniques for the assignment of facilities to locations, Operations Research 16 (1968) 150-173.
