A bi-criteria hybrid genetic algorithm with robustness objective for the course timetabling problem. (English) Zbl 1391.90235
Summary: Traditional methods of generating timetables may yield high-quality solutions, but they may not yield robust solutions that may easily be adapted to changing inputs. Incorporating late changes by making minimum modifications on the final timetable is an important need in many practical applications of timetabling. In this study, we focus on a subset of course timetabling problems, the curriculum-based timetabling problem. We first define a robustness measure for the problem, and then try to find a set of good solutions in terms of both penalty and robustness values. We model the problem as a bi-criteria optimization problem and solve it by a hybrid multi-objective genetic algorithm, which makes use of hill climbing and simulated annealing algorithms in addition to the standard genetic algorithm approach. The algorithm is tested on the well known ITC-2007 instances and shown to identify high quality Pareto fronts.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C29 | Multi-objective and goal programming |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Software:
NSGA-IIReferences:
| [1] | Abdullah, S.; Turabieh, H., On the use of multineighbourhood structures within a tabu-based memetic approach to university timetabling problems, Inf. Sci., 191, 146-168, (2012) |
| [2] | Akkan, C.; Erdem Külünk, M.; Koçaş, C., Finding robust timetables for project presentations of student teams, Eur. J. Oper. Res., 249, 2, 560-576, (2016) · Zbl 1346.90321 |
| [3] | Bäck, T., Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms, (1996), Oxford University Press · Zbl 0877.68060 |
| [4] | Bellio, R.; Ceschia, S.; Di Gaspero, L.; Schaerf, A.; Urli, T., Feature-based tuning of simulated annealing applied to the curriculum-based course timetabling problem, Comput. Oper. Res., 65, 83-92, (2016) · Zbl 1349.90316 |
| [5] | Bellio, R.; Di Gaspero, L.; Schaerf, A., Design and statistical analysis of a hybrid local search algorithm for course timetabling, J. Scheduling, 15, 1, 49-61, (2012) |
| [6] | Birattari, M.; Yuan, Z.; Balaprakash, P.; Stützle, T., F-race and iterated F-race: an overview, 311-336, (2010), Springer Berlin Heidelberg Berlin, Heidelberg, Chapter 13 · Zbl 1204.68280 |
| [7] | Brailsford, S. C.; Potts, C. N.; Smith, B. M., Constraint satisfaction problems: algorithms and applications, Eur. J. Oper. Res., 119, 3, 557-581, (1999) · Zbl 0938.90055 |
| [8] | Burke, E.; Eckersley, A.; McCollum, B.; Petrovic, S.; Qu, R., Hybrid variable neighbourhood approaches to university exam timetabling, Technical Report NOTTCS-TR-2006-2, (2006), University of Nottingham, School of CSiT · Zbl 1188.90090 |
| [9] | Burke, E. K.; Newall, J. P.; Weare, R. F., Initialization strategies and diversity in evolutionary timetabling., Evol. Comput., 6, 1, 81, (1998) |
| [10] | Carrasco, M.; Pato, M. V., A multiobjective genetic algorithm for the class/teacher timetabling problem, Lecture Notes in Computer Science, vol. 2079, 1-17, (2001), Springer · Zbl 0982.68523 |
| [11] | Cheong, C. Y.; Tan, K. C.; Veeravalli, B., A multi-objective evolutionary algorithm for examination timetabling, J. Scheduling, 12, 2, 121-146, (2009) · Zbl 1179.90133 |
| [12] | Coello, C. A., An updated survey of GA-based multiobjective optimization techniques, ACM Comput. Surv., 32, 2, 109-143, (2000) |
| [13] | Conover., W. J., Practical nonparametric statistics, (1999), John Wiley & Sons New York, NY, USA |
| [14] | Datta, D.; Deb, K.; Fonseca, C. M., Multi-objective evolutionary algorithm for university class timetabling problem, Studies in Computational Intelligence, vol. 49, 197-236, (2007), Springer · Zbl 1200.90070 |
| [15] | Deb, K., Multi-objective optimization using evolutionary algorithms, (2001), Wiley · Zbl 0970.90091 |
| [16] | Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans. Evol. Comput., 6, 2, 182-197, (2002) |
| [17] | DeJong, K., An Analysis of the Behavior of a Class of Genetic Adaptive Systems. Ph. D. thesis, (1975), University of Michigan |
| [18] | Di Gaspero, L.; McCollum, B.; Schaerf, A., The second international timetabling competition (ITC-2007): curriculum-based course timetabling (track 3), Technical Report QUB/IEEE/Tech/ITC2007/CurriculumCTT/v1. 0, (2007), Queen’s University, Belfast, United Kingdom |
| [19] | Eiben, A. E.; Smit, S. K., Evolutionary algorithm parameters and methods to tune them, 15-36, (2012), Springer Berlin Heidelberg, Chapter 2 |
| [20] | Fonseca, C. M.; Fleming, P. J., Multiobjective genetic algorithms, IEEE Colloquium on Genetic Algorithms for Control Systems Engineering, 1-6, (1993) |
| [21] | Glover, F., Tabu search - part I, ORSA J. Comput., 1, 3, 190-206, (1989) · Zbl 0753.90054 |
| [22] | Glover, F., Tabu search - part II, ORSA J. Comput., 2, 1, 4-32, (1990) · Zbl 0771.90084 |
| [23] | Golberg, D. E., Genetic algorithms in search, optimization, and machine learning, (1989), Addison-Wesley Boston, MA, USA · Zbl 0721.68056 |
| [24] | Goldberg, D. E.; Lingle, R., Alleles, loci, and the traveling salesman problem, Proceedings of the First International Conference on Genetic Algorithms and their Applications, 154, 154-159, (1985) · Zbl 0674.90095 |
| [25] | Grefenstette, J. J., Optimization of control parameters for genetic algorithms, IEEE Trans. Syst. Man Cybern., 16, 1, 122-128, (1986) |
| [26] | Herroelen, W.; Leus, R., Robust and reactive project scheduling: a review and classification of procedures, Int. J. Prod. Res., 42, 8, 1599-1620, (2004) |
| [27] | Holland, J. H., Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence., (1975), University of Michigan Press, Ann Arbor, MI, USA · Zbl 0317.68006 |
| [28] | Jensen, M. T., Generating robust and flexible job shop schedules using genetic algorithms, IEEE Trans. Evol. Comput., 7, 3, 275-288, (2003) |
| [29] | Kingston, J. H., Educational timetabling, (Uyar, S. A.; Ozcan, E.; Urquhart, N., Studies in Computational Intelligence, 505, (2013), Springer Berlin Heidelberg), 91-108 |
| [30] | Kirkpatrick, S., Optimization by simulated annealing: quantitative studies, J. Stat. Phys., 34, 5-6, 975-986, (1984) |
| [31] | Konak, A.; Coit, D. W.; Smith, A. E., Multiobjective optimization using genetic algorithms: a tutorial, Reliab. Eng. Syst. Saf., 91, 9, 992-1007, (2006) |
| [32] | Lewis, R., A survey of metaheuristic-based techniques for university timetabling problems, OR Spectr., 30, 1, 167-190, (2008) · Zbl 1133.90341 |
| [33] | Liebchen, C.; Lübbecke, M.; Möhring, R.; Stiller, S., The concept of recoverable robustness, linear programming recovery, and railway applications, (Ahuja, R. K.; Möhring, R. H.; Zaroliagis, C. D., Lecture Notes in Computer Science, vol. 5868, (2009), Springer), 1-27 · Zbl 1266.90044 |
| [34] | Lü, Z.; Hao, J.-K., Adaptive tabu search for course timetabling, Eur. J. Oper. Res., 200, 1, 235-244, (2010) · Zbl 1190.90166 |
| [35] | Mühlenthaler, M.; Wanka, R., Fairness in Academic course timetabling, Ann. Oper. Res., 239, 1, 171-188, (2016) · Zbl 1336.90078 |
| [36] | Müller, T., ITC2007 solver description: a hybrid approach, Ann. Oper. Res., 172, 1, 429-446, (2009) · Zbl 1184.90143 |
| [37] | Ouelhadj, D.; Petrovic, S., A survey of dynamic scheduling in manufacturing systems, J. Scheduling, 12, 4, 417-431, (2009) · Zbl 1185.90089 |
| [38] | Phillips, A. E.; Walker, C. G.; Ehrgott, M.; Ryan, D. M., Integer programming for minimal perturbation problems in university course timetabling, 10th International Conference of the Practice and Theory of Automated Timetabling PATAT 2014, 366-379, (2014) |
| [39] | Pillay, N., A survey of school timetabling research, Ann. Oper. Res., 218, 261-293, (2014) · Zbl 1301.90040 |
| [40] | Schaerf, A., A survey of automated timetabling, Artif. Intell. Rev., 13, 2, 87-127, (1999) |
| [41] | Schott, J. R., Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization. PhD thesis, (1995), Massachusetts Institute of Technology |
| [42] | Srinivas, N.; Deb, K., Multiobjective optimization using nondominated sorting in genetic algorithms, Evol. Comput., 2, 3, 221-248, (1994) |
| [43] | Van Veldhuizen, D. A., Multiobjective Evolutionary Algorithms: Classifications, Analyses, and New Innovations. PhD thesis, (1999), Air Force Institute of Technology, Wright Patterson AFB, OH, USA |
| [44] | Wong, T.; Côté, P.; Sabourin, R., A hybrid moea for the capacitated exam proximity problem, 2004 Congress on Evolutionary Computation (CEC 2004), vol. 2(1), 1495-1501, (2004) |
| [45] | Yu, E.; Sung, K.-S., A genetic algorithm for a university weekly courses timetabling problem., Int. Trans. Oper. Res., 9, 6, 703-717, (2002) · Zbl 1044.90066 |
| [46] | Zitzler, E., Evolutionary Algorithms for Multiobjective Optimization : Methods and Applications. PhD thesis, (1999), Swiss Federal Institute of Technology (ETH) Zurich, Switzerland |
| [47] | Zitzler, E.; Deb, K.; Thiele, L., Comparison of multiobjective evolutionary algorithms: empirical results, Evol. Comput., 8, 2, 173-195, (2000) |
| [48] | Zitzler, E.; Thiele, L.; Laumanns, M.; Fonseca, C. M.; Da Fonseca, V. G., Performance assessment of multiobjective optimizers: an analysis and review, IEEE Trans. Evol. Comput., 7, 2, 117-132, (2003) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
