A hybrid multi-objective genetic-based discrete particle swarm optimization algorithm with a local search for solving the post enrolment based course timetabling problem

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

Name: Thanawat Unprasertporn

keyword: Particle swarm optimization

LCSH: Combinatorial optimization

; Multi-objective optimization

LCSH: Metaheuristics

; Local search algorithm

LCSH: Schedules, School

Abstract: The Post Enrolment Based Course Timetabling Problem (PECTP) is a part of university course timetabling problem (UCTP), which is the problem that occurs continuously in all universities. It is about the allocation of subjects, so called events, into time slots and suitable rooms according to students’ enrolment. In addition, arranging the optimal and effective timetable is a quite hard task due to the complexity of the problem itself. The solution of this problem must satisfy all hard constraints and meets the soft constraints as much as possible. This problem is therefore classified as a combinatorial optimization problem, with the difficult level of NP-Complete problem resulting in the highly time-consuming of solving the problem. Moreover, the timetabling problem in real world situation was considered as the multiple objective problem more than a single objective problem. Continuously, in this research, we have improved the representation of a solution of genetic-based particle swarm optimization (GDPSO) for better results because the standard particle swarm optimization (PSO) was designed to work with the continuous nonlinear functions more than a discrete function. We also have developed a multi-objective GDPSO combined with local search approaches for solving the PECTP, and it will be tested with Metaheuristics Network (MN) instances. Last, the experimental results of the proposed hybrid approach will be compared with other algorithms from the literature in terms of the quality of the solutions rather than the computing time of getting the solutions.

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

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

Address: BANGKOK

Email: library@kmutnb.ac.th

Name: Dome Lohpetch

Role: thesis advisors

Email : dome.l@sci.kmutnb.ac.th

Created: 2019

Modified: 2025-07-08

Issued: 2021-05-20

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

application/pdf

eng

DegreeName: Master of science

Level: Master's Degree

Descipline: Mathematics with Computer Science

Grantor: King Mongkut's University of Technology North Bangkok

©copyrights King Mongkut's University of Technology North Bangkok

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	B17508381.pdf	2.32 MB

ใช้เวลา

0.028253 วินาที