NDLI: On the performance of Scatter Search for post-enrolment course timetabling problems

Content Provider	Springer Nature Link
Author	Jaradat, Ghaith Ayob, Masri Ahmad, Zulkifli
Copyright Year	2012
Abstract	This study presents an investigation of enhancing the capability of the Scatter Search (SS) metaheuristic in guiding the search effectively toward elite solutions. Generally, SS generates a population of random initial solutions and systematically selects a set of diverse and elite solutions as a reference set for guiding the search. The work focuses on three strategies that may have an impact on the performance of SS. These are: explicit solutions combination, dynamic memory update, and systematic search re-initialization. First, the original SS is applied. Second, we propose two versions of the SS (V1 and V2) with different strategies. In contrast to the original SS, SSV1 and SSV2 use the quality and diversity of solutions to create and update the memory, to perform solutions combinations, and to update the search. The differences between SSV1 and SSV2 is that SSV1 employs the hill climbing routine twice whilst SSV2 employs hill climbing and iterated local search method. In addition, SSV1 combines all pairs (of quality and diverse solutions) from the RefSet whilst SSV2 combines only one pair. Both SSV1 and SSV2 update the RefSet dynamically rather than static (as in the original SS), where, whenever a better quality or more diverse solution is found, the worst solution in RefSet is replaced by the new solution. SSV1 and SSV2 employ diversification generation method twice to re-initialize the search. The performance of the SS is tested on three benchmark post-enrolment course timetabling problems. The results had shown that SSV2 performs better than the original SS and SSV1 (in terms of solution’s quality and computational time). It clearly demonstrates the effectiveness of using dynamic memory update, systematic search re-initialization, and combining only one pair of elite solutions. Apart from that, SSV1 and SSV2 can produce good quality solutions (comparable with other approaches), and outperforms some approaches reported in the literature (on some instances with regards to the tested datasets). Moreover, the study shows that by combining (simple crossover) only one pair of elite solutions in each RefSet update, and updating the memory dynamically, the computational time is reduced.
Starting Page	417
Ending Page	439
Page Count	23
File Format	PDF
ISSN	13826905
Journal	Journal of Combinatorial Optimization
Volume Number	27
Issue Number	3
e-ISSN	15732886
Language	English
Publisher	Springer US
Publisher Date	2012-07-07
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Scatter Search metaheuristic Explicit solutions combination Dynamic memory update Systematic search re-initialization Post-enrolment course timetabling problem Combinatorics Convex and Discrete Geometry Mathematical Modeling and Industrial Mathematics Theory of Computation Optimization Operations Research/Decision Theory
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Control and Optimization Discrete Mathematics and Combinatorics Computational Theory and Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A time-dependent metaheuristic algorithm for post enrolment-based course timetabling

Solving the post enrolment course timetabling problem by ant colony optimization

A harmony search algorithm for university course timetabling

Local search and constraint programming for the post enrolment-based course timetabling problem

A hybrid genetic algorithm and tabu search approach for post enrolment course timetabling

A Time-Dependent Metaheuristic Algorithm for Post Enrolment-based Course Timetabling (2011)

An IP-based heuristic for the post enrolment course timetabling problem of the ITC2007

Scatter search for solving the course timetabling problem

A study of search algorithms’ optimization speed

On the performance of Scatter Search for post-enrolment course timetabling problems

Similar Documents

A time-dependent metaheuristic algorithm for post enrolment-based course timetabling

Solving the post enrolment course timetabling problem by ant colony optimization

A harmony search algorithm for university course timetabling

Local search and constraint programming for the post enrolment-based course timetabling problem

A hybrid genetic algorithm and tabu search approach for post enrolment course timetabling

A Time-Dependent Metaheuristic Algorithm for Post Enrolment-based Course Timetabling (2011)

An IP-based heuristic for the post enrolment course timetabling problem of the ITC2007

Scatter search for solving the course timetabling problem

A study of search algorithms’ optimization speed

On the performance of Scatter Search for post-enrolment course timetabling problems