1 /* 2 File generate.h 3 */ 4 5 /*************************************************************************** 6 generate.h - description 7 ------------------- 8 begin : 2002 9 copyright : (C) 2002 by Lalescu Liviu 10 email : Please see https://lalescu.ro/liviu/ for details about contacting Liviu Lalescu (in particular, you can find here the e-mail address) 11 ***************************************************************************/ 12 13 /*************************************************************************** 14 * * 15 * This program is free software: you can redistribute it and/or modify * 16 * it under the terms of the GNU Affero General Public License as * 17 * published by the Free Software Foundation, either version 3 of the * 18 * License, or (at your option) any later version. * 19 * * 20 ***************************************************************************/ 21 22 #ifndef GENERATE_H 23 #define GENERATE_H 24 25 #include "timetable_defs.h" 26 #include "solution.h" 27 #include "matrix.h" 28 29 #include <QObject> 30 31 #include <QTextStream> 32 33 #include <QList> 34 #include <QSet> 35 36 //#include <QMutex> 37 #include <QSemaphore> 38 #include <mutex> 39 //#include <semaphore> 40 //#include <condition_variable> 41 42 class Activity; 43 44 class QWidget; 45 46 /** 47 This class incorporates the routines for time and space allocation of activities 48 */ 49 class Generate: public QObject{ 50 Q_OBJECT 51 52 public: 53 //QMutex myMutex; 54 std::mutex myMutex; 55 56 int nThread; //for multiple generation, otherwise it is 0. 57 58 QSemaphore semaphorePlacedActivity; 59 //std::binary_semaphore semaphorePlacedActivity; 60 //std::condition_variable cvForPlacedActivity; 61 bool placedActivityProcessed; 62 63 private: 64 bool foundGoodSwap; 65 Matrix1D<int> permutation; 66 // 67 //The following variables are here to accelerate the generation (so that they are not allocated more times during the generation). 68 Matrix1D<int> buildings; 69 Matrix1D<int> activities; 70 Matrix1D<int> rooms; 71 Matrix1D<int> activitiesx2; 72 Matrix1D<int> roomsx2; 73 Matrix2D<int> weekBuildings; 74 Matrix2D<int> weekActivities; 75 Matrix2D<int> weekRooms; 76 Matrix1D<int> aminoCnt; 77 Matrix1D<int> aminsCnt; 78 Matrix1D<bool> possibleToEmptySlot; 79 // 80 Matrix1D<bool> occupiedDay; 81 Matrix1D<bool> canEmptyDay; 82 Matrix1D<int> _nConflActivities; 83 Matrix1D<QList<int>> _activitiesForDay; 84 Matrix1D<int> _minWrong; 85 Matrix1D<int> _nWrong; 86 Matrix1D<int> _minIndexAct; 87 Matrix1D<bool> occupiedIntervalDay; 88 Matrix1D<bool> canEmptyIntervalDay; 89 Matrix1D<QList<int>> _activitiesForIntervalDay; 90 Matrix1D<int> sbgDayNHoursWithTag; 91 Matrix1D<bool> possibleToEmptyDay; 92 Matrix1D<int> tchDayNHoursWithTag; 93 // 94 Matrix1D<bool> canEmptyTerm; 95 Matrix1D<QList<int>> termActivities; 96 // 97 Matrix1D<bool> swappedActivities; 98 Matrix1D<int> restoreActIndex; 99 Matrix1D<int> restoreTime; 100 Matrix1D<int> restoreRoom; 101 Matrix1D<QList<int>> restoreRealRoomsList; 102 Matrix1D<int> invPermutation; 103 // 104 Matrix2D<double> nMinDaysBrokenL; 105 Matrix2D<int> selectedRoomL; 106 Matrix2D<int> permL; 107 Matrix2D<QList<int>> conflActivitiesL; 108 Matrix2D<int> nConflActivitiesL; 109 Matrix2D<int> roomSlotsL; 110 Matrix2D<QList<int>> realRoomsListL; 111 // 112 Matrix1D<int> slotActivity; 113 // 114 int currentLevel; 115 // 116 QSet<int> conflActivitiesSet; 117 // 118 int nRestore; 119 int limitcallsrandomswap; 120 int level_limit; 121 int ncallsrandomswap; 122 // 123 //if level==0, choose best position with the lowest number of conflicting activities 124 QList<int> conflActivitiesTimeSlot; 125 int timeSlot; 126 int roomSlot; 127 QList<int> realRoomsSlot; 128 // 129 Matrix2D<int> triedRemovals; 130 // 131 bool impossibleActivity; 132 // 133 ////////tabu list of tried removals (circular) 134 int tabu_size; 135 int crt_tabu_index; 136 Matrix1D<int> tabu_activities; 137 Matrix1D<int> tabu_times; 138 //////////// 139 Matrix3D<int> teachersTimetable; 140 Matrix3D<int> subgroupsTimetable; 141 Matrix3D<int> roomsTimetable; 142 // 143 Matrix3D<int> newTeachersTimetable; 144 Matrix3D<int> newSubgroupsTimetable; 145 Matrix2D<int> newTeachersDayNHours; 146 Matrix2D<int> newTeachersDayNGaps; 147 Matrix2D<int> newSubgroupsDayNHours; 148 Matrix2D<int> newSubgroupsDayNGaps; 149 Matrix2D<int> newSubgroupsDayNFirstGaps; 150 151 Matrix2D<int> newTeachersDayNFirstGaps; 152 Matrix2D<int> newTeachersRealDayNHours; 153 Matrix2D<int> newTeachersRealDayNGaps; 154 Matrix2D<int> newSubgroupsRealDayNHours; 155 Matrix2D<int> newSubgroupsRealDayNGaps; 156 Matrix2D<int> newSubgroupsRealDayNFirstGaps; 157 158 // 159 Matrix3D<int> oldTeachersTimetable; 160 Matrix3D<int> oldSubgroupsTimetable; 161 Matrix2D<int> oldTeachersDayNHours; 162 Matrix2D<int> oldTeachersDayNGaps; 163 Matrix2D<int> oldSubgroupsDayNHours; 164 Matrix2D<int> oldSubgroupsDayNGaps; 165 Matrix2D<int> oldSubgroupsDayNFirstGaps; 166 167 Matrix2D<int> oldTeachersDayNFirstGaps; 168 Matrix2D<int> oldTeachersRealDayNHours; 169 Matrix2D<int> oldTeachersRealDayNGaps; 170 Matrix2D<int> oldSubgroupsRealDayNHours; 171 Matrix2D<int> oldSubgroupsRealDayNGaps; 172 Matrix2D<int> oldSubgroupsRealDayNFirstGaps; 173 174 // 175 Matrix2D<int> tchTimetable; 176 Matrix1D<int> tchDayNHours; 177 Matrix1D<int> tchDayNGaps; 178 179 Matrix2D<int> sbgTimetable; 180 Matrix1D<int> sbgDayNHours; 181 Matrix1D<int> sbgDayNGaps; 182 Matrix1D<int> sbgDayNFirstGaps; 183 184 Matrix1D<int> tchDayNFirstGaps; 185 Matrix1D<int> tchRealDayNHours; 186 Matrix1D<int> tchRealDayNGaps; 187 Matrix1D<int> sbgRealDayNHours; 188 Matrix1D<int> sbgRealDayNGaps; 189 Matrix1D<int> sbgRealDayNFirstGaps; 190 191 // 192 Matrix2D<QList<int>> teacherActivitiesOfTheDay; 193 Matrix2D<QList<int>> subgroupActivitiesOfTheDay; 194 195 //used at level 0 196 Matrix1D<int> l0nWrong; 197 Matrix1D<int> l0minWrong; 198 Matrix1D<int> l0minIndexAct; 199 200 //2011-09-25 201 Matrix1D<QSet<int>> slotSetOfActivities; 202 Matrix1D<bool> slotCanEmpty; 203 204 Matrix1D<QSet<int>> activitiesAtTime; 205 //////////// 206 207 int nRealRooms; 208 int nSets; 209 int NIL_NODE; 210 211 Matrix1D<QList<int>> adj; 212 //static Matrix1D<int> dist; 213 Matrix1D<bool> visited; 214 Matrix1D<int> semiRandomPermutation; //the semi-random permutation of U (the points on the left, the real rooms) 215 Matrix1D<int> pairNode; 216 Matrix1D<int> nConflictingActivitiesBipartiteMatching; 217 Matrix1D<QSet<int>> conflictingActivitiesBipartiteMatching; //only used at level 0 218 219 Solution* tmpGlobalSolutionCompareLevel0; 220 221 bool compareConflictsIncreasing(int a, int b); 222 bool compareConflictsIncreasingAtLevel0(int a, int b); 223 224 //2019-09-15 - for virtual rooms, choosing randomly the real rooms. 225 /*bool breadthFirstSearch(); 226 bool depthFirstSearch(int u); 227 int hopcroftKarp();*/ 228 229 bool depthFirstSearch(int u); 230 int maximumBipartiteMatching(); 231 232 //a probabilistic function to say if we can skip a constraint based on its percentage weight 233 bool skipRandom(double weightPercentage); 234 235 //for sorting slots in ascending order of potential conflicts 236 bool compareFunctionGenerate(int i, int j); 237 238 public: 239 MRG32k3a rng; 240 241 bool isRunning; 242 243 int maxActivitiesPlaced; 244 Solution highestStageSolution; 245 246 Generate(); 247 ~Generate(); 248 249 inline void addAiToNewTimetable(int ai, const Activity* act, int d, int h); 250 inline void removeAiFromNewTimetable(int ai, const Activity* act, int d, int h); 251 252 inline void getTchTimetable(int tch, const QList<int>& conflActivities); 253 inline void getSbgTimetable(int sbg, const QList<int>& conflActivities); 254 255 inline void removeAi2FromTchTimetable(int ai2); 256 inline void removeAi2FromSbgTimetable(int ai2); 257 258 inline void updateTeachersNHoursGaps(int ai, int d); 259 inline void updateSubgroupsNHoursGaps(int ai, int d); 260 261 inline void updateTeachersNHoursGapsRealDay(int ai, int real_d); 262 inline void updateSubgroupsNHoursGapsRealDay(int ai, int real_d); 263 264 inline void updateTchNHoursGaps(int tch, int d); 265 inline void updateSbgNHoursGaps(int sbg, int d); 266 267 inline void updateTchNHoursGapsRealDay(int tch, int real_d); 268 inline void updateSbgNHoursGapsRealDay(int sbg, int real_d); 269 270 inline void tchGetNHoursGaps(int tch); 271 inline void tchGetNHoursGapsRealDays(int tch); 272 inline void teacherGetNHoursGaps(int tch); 273 inline bool teacherRemoveAnActivityFromBeginOrEnd(int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 274 inline bool teacherRemoveAnActivityFromEnd(int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 275 inline bool teacherRemoveAnActivityFromAnywhere(int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 276 inline bool teacherRemoveAnActivityFromBeginOrEndCertainDay(int d2, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 277 inline bool teacherRemoveAnActivityFromAnywhereCertainDay(int d2, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 278 279 inline bool teacherRemoveAnActivityFromAnywhereCertainDayCertainActivityTag(int d2, int actTag, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 280 inline bool teacherRemoveAnActivityFromAnywhereCertainDayDayPairCertainActivityTag(int d2, int dpair2, int actTag, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 281 282 inline bool teacherRemoveAnActivityFromBeginOrEndCertainTwoDays(int d2, int d4, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 283 inline bool teacherRemoveAnActivityFromAnywhereCertainTwoDays(int d2, int d4, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 284 285 //constraints teachers max gaps per real day 286 inline bool teacherRemoveAnActivityFromBeginMorningOrEndAfternoon(int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 287 inline bool teacherRemoveAnActivityFromBeginOrEndCertainRealDay(int d2, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 288 289 inline void sbgGetNHoursGaps(int sbg); 290 inline void sbgGetNHoursGapsRealDays(int sbg); 291 inline void subgroupGetNHoursGaps(int sbg); 292 inline bool subgroupRemoveAnActivityFromBegin(int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 293 inline bool subgroupRemoveAnActivityFromEnd(int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 294 inline bool subgroupRemoveAnActivityFromBeginOrEnd(int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 295 inline bool subgroupRemoveAnActivityFromAnywhere(int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 296 inline bool subgroupRemoveAnActivityFromBeginCertainDay(int d2, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 297 inline bool subgroupRemoveAnActivityFromEndCertainDay(int d2, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 298 inline bool subgroupRemoveAnActivityFromAnywhereCertainDay(int d2, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 299 300 //2017-02-07 301 //used only in students max span per day 302 inline bool subgroupRemoveAnActivityFromBeginOrEndCertainDay(int d2, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 303 304 inline bool subgroupRemoveAnActivityFromAnywhereCertainDayCertainActivityTag(int d2, int actTag, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 305 306 //constraints students max gaps per real day 307 inline bool subgroupRemoveAnActivityFromBeginMorning(int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 308 inline bool subgroupRemoveAnActivityFromEndAfternoon(int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 309 inline bool subgroupRemoveAnActivityFromBeginMorningOrEndAfternoon(int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 310 311 inline bool subgroupRemoveAnActivityFromBeginOrEndCertainRealDay(int d2, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 312 inline bool subgroupRemoveAnActivityFromEndCertainRealDay(int d2, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 313 314 inline bool subgroupRemoveAnActivityFromAnywhereCertainDayDayPairCertainActivityTag(int d2, int dpair2, int actTag, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 315 316 inline bool subgroupRemoveAnActivityFromBeginCertainTwoDays(int d2, int d4, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 317 inline bool subgroupRemoveAnActivityFromEndCertainTwoDays(int d2, int d4, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 318 inline bool subgroupRemoveAnActivityFromAnywhereCertainTwoDays(int d2, int d4, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity); 319 320 inline bool checkActivitiesOccupyMaxDifferentRooms(const QList<int>& globalConflActivities, int rm, int level, int ai, QList<int>& tmp_list); 321 inline bool checkActivitiesSameRoomIfConsecutive(const QList<int>& globalConflActivities, int rm, int ai, int d, int h, QList<int>& tmp_list); 322 323 //only one out of sbg and tch is >=0, the other one is -1 324 inline bool checkBuildingChanges(int sbg, int tch, const QList<int>& globalConflActivities, int rm, int level, const Activity* act, int ai, int d, int h, QList<int>& tmp_list); 325 inline bool checkRoomChanges(int sbg, int tch, const QList<int>& globalConflActivities, int rm, int level, const Activity* act, int ai, int d, int h, QList<int>& tmp_list); 326 327 inline bool checkRoomChangesPerRealDay(int sbg, int tch, const QList<int>& globalConflActivities, int rm, int level, const Activity* act, int ai, int d, int h, QList<int>& tmp_list); 328 329 inline bool chooseRoom(const QList<int>& listOfRooms, const QList<int>& globalConflActivities, int level, const Activity* act, int ai, int d, int h, int& roomSlot, int& selectedSlot, QList<int>& localConflActivities, QList<int>& realRoomsList); 330 inline bool getHomeRoom(const QList<int>& globalConflActivities, int level, const Activity* act, int ai, int d, int h, int& roomSlot, int& selectedSlot, QList<int>& localConflActivities, QList<int>& realRoomsList); 331 inline bool getPreferredRoom(const QList<int>& globalConflActivities, int level, const Activity* act, int ai, int d, int h, int& roomSlot, int& selectedSlot, QList<int>& localConflActivities, bool& canBeUnspecifiedPreferredRoom, QList<int>& realRoomsList); 332 inline bool getRoom(int level, const Activity* act, int ai, int d, int h, int& roomSlot, int& selectedSlot, QList<int>& conflActivities, int& nConflActivities, QList<int>& realRoomsList); 333 334 Solution c; 335 336 int nPlacedActivities; 337 338 //difficult activities 339 int nDifficultActivities; 340 Matrix1D<int> difficultActivities; 341 342 int searchTime; //seconds 343 344 int timeToHighestStage; //seconds 345 346 bool abortOptimization; 347 348 bool precompute(QWidget* parent, QTextStream* maxPlacedActivityStream=nullptr); 349 350 void generate(int maxSeconds, bool& impossible, bool& timeExceeded, bool threaded, QTextStream* maxPlacedActivityStream=nullptr); 351 352 void moveActivity(int ai, int fromslot, int toslot, int fromroom, int toroom, const QList<int>& fromRealRoomsList, const QList<int>& toRealRoomsList); 353 354 void randomSwap(int ai, int level); 355 356 signals: 357 void activityPlaced(int, int); 358 359 void simulationFinished(); 360 361 void impossibleToSolve(); 362 363 private: 364 bool isThreaded; 365 }; 366 367 #endif 368