Integer programming based cooperative search for solving curriculum course timetabling problems
The research focuses on the problem of Curriculum-based University Course Timetabling (CB-UCT) problem and we discuss how sequential Integer Programming (IP) search methodology can be incorporated into agent-based Multi-Agent Systems (MAS) in order to conduct the parallel search for real-world CB-UC...
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English English |
| Published: |
2018
|
| Subjects: | |
| Online Access: | https://eprints.ums.edu.my/id/eprint/42198/1/24%20PAGES.pdf https://eprints.ums.edu.my/id/eprint/42198/2/FULLTEXT.pdf |
| _version_ | 1825715995784773632 |
|---|---|
| author | Mansour Hassani Abdalla |
| author_facet | Mansour Hassani Abdalla |
| author_sort | Mansour Hassani Abdalla |
| collection | UMS |
| description | The research focuses on the problem of Curriculum-based University Course Timetabling (CB-UCT) problem and we discuss how sequential Integer Programming (IP) search methodology can be incorporated into agent-based Multi-Agent Systems (MAS) in order to conduct the parallel search for real-world CB-UCT. In curriculum-based course timetabling, lectures have to be assigned to periods and rooms, while avoiding overlaps between courses of the same curriculum. The current solutions in Universiti Malaysia Sabah, Labuan International Campus (UMSLIC), do not generate a practical timetable hence burden to the academic department as they have to fix the arising problems manually in each and every semester. The research work presented in this thesis approaches this problem in two phases. For the first phase, the construction of solutions or timetables using sequential IP, we propose sequential pure 0-1 IP search methodology to generate initial feasible solutions and further improve the solution using simple local search. Then, in the second phase of the timetable process, we explore how to incorporate IP into agent-based system approaches where several agents work together to improve the global solutions. We investigate communication protocol such as FIPA-ACL which was adopted in this research for the agent to communicate with one another. In the experiments throughout this thesis, we use set of real-world instances from UMSLIC to assess the performance of the approaches proposed in this thesis. Detailed analyses of the proposed search methodology are presented and their relative benefits discussed. The results demonstrate both sequential and parallel implementation search methodologies are able to generate and improve the solutions impressively, however, parallel IP perform better than its sequential counterparts in UMSLIC instances. Finally, we give our suggestions as to how the proposed framework might be modified in order to deal with a wide range of problem domains. We also discuss the drawbacks of our search methodology in the final section of this thesis. |
| first_indexed | 2025-03-05T01:34:14Z |
| format | Thesis |
| id | ums.eprints-42198 |
| institution | Universiti Malaysia Sabah |
| language | English English |
| last_indexed | 2025-03-05T01:34:14Z |
| publishDate | 2018 |
| record_format | dspace |
| spelling | ums.eprints-421982024-12-16T04:07:43Z https://eprints.ums.edu.my/id/eprint/42198/ Integer programming based cooperative search for solving curriculum course timetabling problems Mansour Hassani Abdalla T57.6-57.97 Operations research. Systems analysis The research focuses on the problem of Curriculum-based University Course Timetabling (CB-UCT) problem and we discuss how sequential Integer Programming (IP) search methodology can be incorporated into agent-based Multi-Agent Systems (MAS) in order to conduct the parallel search for real-world CB-UCT. In curriculum-based course timetabling, lectures have to be assigned to periods and rooms, while avoiding overlaps between courses of the same curriculum. The current solutions in Universiti Malaysia Sabah, Labuan International Campus (UMSLIC), do not generate a practical timetable hence burden to the academic department as they have to fix the arising problems manually in each and every semester. The research work presented in this thesis approaches this problem in two phases. For the first phase, the construction of solutions or timetables using sequential IP, we propose sequential pure 0-1 IP search methodology to generate initial feasible solutions and further improve the solution using simple local search. Then, in the second phase of the timetable process, we explore how to incorporate IP into agent-based system approaches where several agents work together to improve the global solutions. We investigate communication protocol such as FIPA-ACL which was adopted in this research for the agent to communicate with one another. In the experiments throughout this thesis, we use set of real-world instances from UMSLIC to assess the performance of the approaches proposed in this thesis. Detailed analyses of the proposed search methodology are presented and their relative benefits discussed. The results demonstrate both sequential and parallel implementation search methodologies are able to generate and improve the solutions impressively, however, parallel IP perform better than its sequential counterparts in UMSLIC instances. Finally, we give our suggestions as to how the proposed framework might be modified in order to deal with a wide range of problem domains. We also discuss the drawbacks of our search methodology in the final section of this thesis. 2018 Thesis NonPeerReviewed text en https://eprints.ums.edu.my/id/eprint/42198/1/24%20PAGES.pdf text en https://eprints.ums.edu.my/id/eprint/42198/2/FULLTEXT.pdf Mansour Hassani Abdalla (2018) Integer programming based cooperative search for solving curriculum course timetabling problems. Masters thesis, Universiti Malaysia Sabah. |
| spellingShingle | T57.6-57.97 Operations research. Systems analysis Mansour Hassani Abdalla Integer programming based cooperative search for solving curriculum course timetabling problems |
| title | Integer programming based cooperative search for solving curriculum course timetabling problems |
| title_full | Integer programming based cooperative search for solving curriculum course timetabling problems |
| title_fullStr | Integer programming based cooperative search for solving curriculum course timetabling problems |
| title_full_unstemmed | Integer programming based cooperative search for solving curriculum course timetabling problems |
| title_short | Integer programming based cooperative search for solving curriculum course timetabling problems |
| title_sort | integer programming based cooperative search for solving curriculum course timetabling problems |
| topic | T57.6-57.97 Operations research. Systems analysis |
| url | https://eprints.ums.edu.my/id/eprint/42198/1/24%20PAGES.pdf https://eprints.ums.edu.my/id/eprint/42198/2/FULLTEXT.pdf |
| work_keys_str_mv | AT mansourhassaniabdalla integerprogrammingbasedcooperativesearchforsolvingcurriculumcoursetimetablingproblems |