International Journal of Mathematical Sciences and Computing (IJMSC)
IJMSC Vol. 6, No. 5, 8 Oct. 2020
Cover page and Table of Contents: PDF (size: 1981KB)
A Multi-Objective Optimization Approach for Solving AUST Classtimetable Problem Considering Hard and Soft Constraints
Full Text (PDF, 1981KB), PP.1-14
Views: 0 Downloads: 0
Author(s)
Md Shahriar Mahbub
1
Shihab Shahriar Ahmed
2
Kazi Irtiza Ali
3
Md. Taief Imam
4
Index Terms
Class timetable problem, Smart initialization, Multi-objective evolutionary algorithm, hard constraint, soft constraint.
Abstract
Preparing a class timetable or routine is a difficult task because it requires an iterative trial and error method to handle all the constraints. Moreover, it has to be beneficial both for the students and teachers. Therefore, the problem becomes a multi-objective optimization problem with a good number of constraints. There are two types of constraints: hard and soft constraint. As the problem is an NP-hard problem, population based multi-objective optimization algorithms (multi-objective evolutionary algorithm) is a good choice for solving the problem. There are well established hard constraints handling techniques for multi-objective evolutionary algorithms, however, the technique is not enough to solve the problem efficiently. In the paper, a smart initialization technique is proposed to generate fewer constraints violated solutions in the initial phase of the algorithm so that it can find feasible solutions quickly. An experimental analysis supports the assumption. Moreover, there are no well-known techniques available for handling soft constraints. A new soft constraints handing technique is proposed. Experimental results show a significant improvement can be achieved. Finally, proposed combined approach integrates smart initialization and soft constraints handling techniques. Better results are reported when comparing with a standard algorithm.
Cite This Paper
Md Shahriar Mahbub, Shihab Shahriar Ahmed, Kazi Irtiza Ali, Md. Taief Imam. " A Multi-Objective Optimization Approach for Solving AUST Classtimetable Problem Considering Hard and Soft Constraints ", International Journal of Mathematical Sciences and Computing (IJMSC), Vol.6, No.5, pp.1-14, 2020. DOI: 10.5815/IJMSC.2020.05.01
Reference
[1]mez (2009). Constraint-handling in evolutionary optimization. Number volume 198 in Studies in computational intelligence. Springer, Berlin, 2009. ISBN 978-3-642-00618-0.
[2]Ahmad and Shaari (2016). A. Ahmad and F. Shaari. Solving university/polytechnics exam timetable problem using particle swarm optimization. In Proceedings of the 10th International Conference on Ubiquitous Information Management and Communication, page 46. ACM, 2016.
[3]Al-Jarrah et al. (2017) Al-Jarrah, Al-Sawalqah, and Al-Hamdan. M. A. Al-Jarrah, A. A. Al-Sawalqah, and S. F. Al-Hamdan. Developing a course timetable system for academic departments using genetic algorithm. Jordanian Journal of Computers and Information Technology (JJCIT), 3(1), 2017.
[4]Asrar (2012). C. Asrar. Closed and open credits in undergraduate programmes in Bangladesh. The Daily Star, 2012. URL https://www.thedailystar.net/campus/2012/11/04/post.htm.
[5]Carrasco and Pato (2000). M. P. Carrasco and M. V. Pato. A multiobjective genetic algorithm for the class/teacher timetabling problem. In International Conference on the Practice and Theory of Automated Timetabling, pages 3–17. Springer, 2000.
[6]Chaudhuri and De (2010). A. Chaudhuri and K. De. Fuzzy genetic heuristic for university course timetable problem. Int. J. Advance. Soft Comput. Appl, 2(1):100–123, 2010.
[7]Cicirello and Cernera (2013). V. A. Cicirello and R. Cernera. Profiling the distance characteristics of mutation operators for permutation-based genetic algorithms. In the Twenty-Sixth International FLAIRS Conference, 2013.
[8]Cooper and Kingston (1995). T. B. Cooper and J. H. Kingston. The complexity of timetable construction problems. Technical report, University of Sydney, 1995.
[9]Datta et al. (2006) Datta, Deb, and Fonseca. D. Datta, K. Deb, and C. M. Fonseca. Solving class timetabling problem of iit kanpur using multi-objective evolutionary algorithm. KanGAL, Report, 2006006:1–10, 2006.
[10]Deb (2001). K. Deb. Multi-objective optimization using evolutionary algorithms, volume 16. John Wiley & Sons, 2001.
[11]Deb et al. (2002) Deb, Pratap, Agarwal, and Meyarivan. K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2):182–197, 2002.
[12]Durillo and Nebro (2011). J. J. Durillo and A. J. Nebro. jMetal: A Java framework for multi-objective optimization. Advances in Engineering Software, 42:760–771, 2011. ISSN 0965-9978.
[13]Fonseca and Fleming (1998). C. Fonseca and P. Fleming. Multiobjective optimization and multiple constraint handling with evolutionary algorithms. II. Application example. IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans, 28(1):38 –47, Jan. 1998. ISSN 1083-4427. doi: 10.1109/3468.650320.
[14]Jin et al. (2009) Jin, Tsang, and Li. N. Jin, E. Tsang, and J. Li. A constraint-guided method with evolutionary algorithms for economic problems. Applied Soft Computing, 9(3):924 – 935, 2009. ISSN 1568-4946. doi: https://doi.org/10.1016/j.asoc.2008.11.006. URL http://www.sciencedirect.com/science/article/pii/S1568494608001695.
[15]Kazarlis et al. (2005) Kazarlis, Petridis, and Fragkou. S. Kazarlis, V. Petridis, and P. Fragkou. Solving university timetabling problems using advanced genetic algorithms. GAs, 2(7):8–12, 2005.
[16]Kerrigan and Maciejowski (2000). E. C. Kerrigan and J. M. Maciejowski. Soft constraints and exact penalty functions in model predictive control. 2000.
[17]Kristiansen and Stidsen (2013). S. Kristiansen and T. R. Stidsen. A comprehensive study of educational timetabling-a survey. Technical report, Department of Management Engineering, Technical University of Denmark, 2013.
[18]Lovelace (2010). A. L. Lovelace. On the complexity of scheduling university courses. Master’s thesis, California Polytechnic State University, San Luis Obispo, 2010.
[19]Lukas et al. (2009) Lukas, Aribowo, and Muchri. S. Lukas, A. Aribowo, and M. Muchri. Genetic algorithm and heuristic search for solving timetable problem case study: Universitas pelita harapan timetable. In 2009 Second International Conference on the Applications of Digital Information and Web Technologies, pages 629–633, Aug 2009. doi: 10.1109/ICADIWT.2009.5273979.
[20]Magalhaes-Mendes (2013). J. Magalhaes-Mendes. A comparative study of crossover operators for genetic algorithms to solve the job shop scheduling problem. WSEAS transactions on computers, 12(4):164–173, 2013.
[21]Mann and Whitney (1947). H. B. Mann and D. R. Whitney. On a test of whether one of two random variables are stochastically larger than the other. The annals of mathematical statistics, pages 50–60, 1947.
[22]McCollum (2006). B. McCollum. University timetabling: Bridging the gap between research and practice. In in Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling, pages 15–35. Springer, 2006.
[23]Michalewicz and Schoenauer (1996). Z. Michalewicz and M. Schoenauer. Evolutionary algorithms for constrained parameter optimization problems. Evol. Comput., 4(1):1–32, Mar. 1996. ISSN 1063-6560. doi: 10.1162/evco.1996.4.1.1. URL http://dx.doi.org/10.1162/evco.1996.4.1.1.
[24]Singh et al. (2014) Singh, Asafuddoula, and Ray. H. K. Singh, M. Asafuddoula, and T. Ray. Solving problems with a mix of hard and soft constraints using modified infeasibility driven evolutionary algorithm (idea-m). In2014 IEEE Congress on Evolutionary Computation (CEC), pages 983–990, July 2014. doi: 10.1109/CEC.2014.6900239.
[25]Tsang and Jin (2006). E. Tsang and N. Jin. Incentive method to handle constraints in evolutionary algorithms with a case study. In Proceedings of the 9th European Conference on Genetic Programming, EuroGP’06, pages 133–144, Berlin, Heidelberg,2006. Springer-Verlag. ISBN 3-540-33143-3,978-3-540-33143-8.doi:10.1007/1172997612. URL http://dx.doi.org/10.1007/11729976_12.
[26]Woldesenbet et al. (2009) Woldesenbet, Yen, and Tessema. Y. Woldesenbet, G. Yen, and B. Tessema. Constraint Handling in Multiobjective Evolutionary Optimization. IEEE Transactions on Evolutionary Computation, 13(3):514–525, 2009. ISSN1089-778X. doi: 10.1109/TEVC.2008.2009032.
[27]Zitzler and Thiele (1999). E. Zitzler and L. Thiele. Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. IEEE Transactions on Evolutionary Computation, 3(4):257–271, 1999.
[28]Zitzler et al. (2001) Zitzler, Laumanns, and Thiele. E. Zitzler, M. Laumanns, and L. Thiele. SPEA2: Improving the strength pareto evolutionary algorithm. Technical Report TIK-Report No. 103, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH), Zurich, 2001.
[29]Zitzler et al. (2003) Zitzler, Thiele, Laumanns, Fonseca, and Da Fonseca. E. Zitzler, L. Thiele, M. Laumanns, C. M. Fonseca, and V. G. Da Fonseca. Performance assessment of multiobjective optimizers: An analysis and review. IEEE Transactions on Evolutionary Computation, 7(2):117–132, 2003.