Home

Welcome to the ubiquitous-eureka wiki!

A Parallel Distributed Genetic Algorithm for Class Scheduling Problem using Apache Spark

Generate the time-table which tells that teacher X is taking class Y on time Z . Consider a typical high-school, here class receives five hours of lessons, six days a week. Teachers may teach one or more subjects, usually in two or more classes.Each teacher has 18hr per week. Typically every school has these constraints . Some of them are hard constraints and some are soft constraints. Some of the Hard constraints -

• Teacher can only be in one class at any given time
• Classrooms need to be big enough to host the class
• Classrooms can only host one class at any given time Some of the Soft constraints -
• Room capacity should be suitable for the class size
• Preferred classroom of the professor
• Preferred class time of the professor

Sometimes multiple soft constraints may conflict and a tradeoff will need to be found between them. For example, a class might only have 10 students so a soft constraint may reward assigning a suitable classroom, which has a capacity of around 10; however, the professor taking the class may prefer a larger classroom, which can hold 30 students. If professor preferences are accounted for as soft constraints, one of these configurations will be preferred and hopefully found by the class scheduler [7] .

• [1] Yoshiki Sugawara, Nobukazu Takai , Masato Kato , Hiroaki Seki,Kento Suzuki ,Haruo Kobayashi - “ Automatic design of doubly-terminated RC polyphase filters by using distributed genetic algorithm ”- ASIC (ASICON), 2015 IEEE 11th International Conference on
• [2] Alberto Colorni , Marco Dorigo , Vittorio Maniezzo - “ A Genetic Algorithm To Solve The Timetable Problem (1993) ”
• [3] Mingjie Wang , Jesse S. Jin , Gelin Wu, Wei Tong , Yu Peng - DISTRIBUTED GENETIC ALGORITHM BASED ON RESTFUL FRAMEWORK
• [4] Mauro Castelli , Luca Manzoni , Leonardo Vanneschi - “ The effect of selection from old populations in genetic algorithms ”
• [5] Francisco Rojas, Federico Meza- “ A Parallel Distributed Genetic Algorithm for the Prize Collecting Steiner Tree Problem ”
• [6] List of genetic algorithm applications
• [7] Genetic Algorithms in Java Basics By Lee Jacobson , Burak Kanber
• [8] Genetic Algorithms tutorial
• [9] Cuda - http://www.nvidia.com/object/cuda_home_new.html
• [10] MPICH - https://www.mpich.org/
• [11] Apache Spark - http://spark.apache.org/
• [12] Apache spark use cases - https://www.qubole.com/blog/big-data/apache-spark-use-cases/
• [13] gpu-application - http://www.nvidia.com/object/gpu-applications.html
• [14] A Genetic Algorithm for Resource-Constrained Scheduling - MIT