A hybrid multi-objective evolutionary algorithm with a local search approach for solving the post enrolment based course timetabling problem

ขั้นตอนวิธีเชิงวิวัฒนาการแบบหลายวัตถุประสงค์ผสมผสานด้วยแนวทางการค้นหาแบบเฉพาะที่เพื่อแก้ปัญหาการจัดตารางสอนที่อ้างอิงตามการลงทะเบียน

Name: Sawaphat Jaengchuea

keyword: Multi-objective optimization.

ThaSH: Schedules, School -- Management

; Evolutionary Algorithm.

Abstract: The post enrolment based course timetabling problem (PECTP) is one type of university course timetabling problem, which a set of events has to be assigned into time slots and suitable rooms according to students’ enrolment data. The PECTP is a real world problem and it commonly occurs in every educational institution in every semester. This problem is classified as a combinatorial optimization problem and it is very hard to solve the problem efficiently because solving the problem is to find an optimal timetable which it must satisfy all hard constraints and should satisfy soft constraints as much as possible. As a result, this problem is technically complicated and highly time-consuming and it is known to be in the NP-complete class. In addition, the nature of this problem also naturally leads to multiple objective functions as there is usually more than one objective that needs to be simultaneously optimized. In this research we develop a multi-objective evolutionary algorithm hybridized with local search approaches for solving the PECTP. The algorithm takes advantage of the exploitation ability from local search technique and tabu search heuristic to improve the results obtained in the exploration phase of the evolutionary algorithm. The algorithm was tested on a set of problem instances from Metaheuristic Network, a standard benchmark for evaluating the proposed hybrid algorithm. The experimental results of proposed hybrid approach comparing with other methods from the literature have shown that the proposed hybrid approach is able to find promising solutions for solving the PECTP

Abstract: ปัญหาการจัดตารางสอนที่อ้างอิงตามการลงทะเบียน เป็นประเภทหนึ่งของปัญหาการจัดตารางสอนในระดับมหาวิทยาลัย ซึ่งจะจัดสรรเซตของเหตุการณ์ลงในห้องเรียนและช่วงเวลา ที่เหมาะสมตามข้อมูลการลงทะเบียนของนักศึกษา ปัญหาการจัดตารางสอนที่อ้างอิงตาม การลงทะเบียนเป็นปัญหาที่เกิดขึ้นในโลกแห่งความเป็นจริง และเกิดขึ้นเป็นประจำกับทุกสถาบันการศึกษาในทุก ๆ เทอม ปัญหานี้ถูกจัดเป็นปัญหาการหาค่าเหมาะสมที่สุดเชิงการจัด และเป็นเรื่องยากมากที่จะแก้ปัญหานี้ได้อย่างมีประสิทธิภาพ เพราะการแก้ปัญหานี้คือการหาตาราง ที่เหมาะสมที่สุด ซึ่งมันต้องสอดคล้องกับเงื่อนไขบังคับหลักทุกข้อ และควรสอดคล้องกับเงื่อนไขบังคับรองมากที่สุดเท่าที่จะเป็นไปได้ ส่งผลให้ปัญหานี้เป็นปัญหาที่ค่อนข้างมีความซับซ้อนทางเทคนิคสูงและใช้เวลานานในการแก้ปัญหา และเป็นที่รู้กันว่าปัญหานี้ถูกจัดอยู่ในปัญหาประเภทเอ็นพีบริบูรณ์ นอกจากนี้ธรรมชาติของปัญหานี้ยังเป็นแบบหลายฟังก์ชันวัตถุประสงค์ ซึ่งมีมากกว่าหนึ่งวัตถุประสงค์ที่เราต้องพิจารณาพร้อม ๆ กันเพื่อหาค่าเหมาะสมที่สุด ในงานวิจัยนี้ เราพัฒนาขั้นตอนวิธีเชิงวิวัฒนาการแบบหลายวัตถุประสงค์ผสมผสานกับแนวทางการค้นหาแบบเฉพาะที่ เพื่อนำมาใช้แก้ปัญหาการจัดตารางสอนที่อ้างอิงตามการลงทะเบียน ขั้นตอนวิธีนี้ใช้ประโยชน์จากความสามารถในการค้นหาแบบเจาะจงจากเทคนิคการค้นหาแบบเฉพาะที่และการค้นหาแบบทาบูเพื่อปรับปรุงผลลัพธ์ที่ได้มาจากขั้นตอนการค้นหาแบบวงกว้างของขั้นตอนวิธีเชิงวิวัฒนาการ ขั้นตอนวิธีนี้ถูกทดสอบโดยใช้เซตของตัวอย่างปัญหาจากเครือข่ายเมตาฮิวริสติกเป็นเกณฑ์มาตรฐานสำหรับการประเมินผลขั้นตอนวิธีแบบผสมผสานที่นำเสนอในงานวิจัยนี้ ผลการทดลองของแนวทางแบบผสมผสานที่นำเสนอเปรียบเทียบกับวิธีการอื่นๆ ที่ได้จากการทบทวนวรรณกรรมแสดงให้เห็นว่า แนวทางแบบผสมผสานที่นำเสนอนั้นสามารถให้ผลลัพธ์ซึ่งมีแนวโน้มที่ดีในการแก้ปัญหาการจัดตารางสอนที่อ้างอิงตามการลงทะเบียน

King Mongkut's University of Technology North Bangkok. Central Library

Address: Bangkok

Email: library@kmutnb.ac.th

Name: Dome Lohpetch

Role: Thesis advisors

Email : dlp@kmutnb.ac.th

Created: 2014

Modified: 2025-07-08

Issued: 2015-09-08

วิทยานิพนธ์/Thesis

application/pdf

CallNumber: E-THESIS

eng

DegreeName: Master of science

Level: Master's Degree

Descipline: Applied Mathematics

Grantor: King Mongkut's University of Technology North Bangkok

©copyrights King Mongkut's University of Technology North Bangkok

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	B15912504.pdf	3.67 MB	64	2024-04-06 17:31:10

ใช้เวลา

0.042118 วินาที