Chulalongkorn University Theses and Dissertations (Chula ETD)

การพัฒนาโปรแกรมจัดตารางสอนโดยใช้ขั้นตอนวิธีเชิงพันธุกรรม

Other Title (Parallel Title in Other Language of ETD)

Development of an automated lecture timetabling program using genetic algorithms

Year (A.D.)

2005

Document Type

Thesis

First Advisor

เศรษฐา ปานงาม

Second Advisor

ตะวัน ปภาพจน์

Faculty/College

Faculty of Engineering (คณะวิศวกรรมศาสตร์)

Degree Name

วิทยาศาสตรมหาบัณฑิต

Degree Level

ปริญญาโท

Degree Discipline

วิทยาศาสตร์คอมพิวเตอร์

DOI

10.58837/CHULA.THE.2005.1229

Abstract

สำหรับสถาบันการศึกษามีงานต้องทำอยู่เสมอ คือการจัดตารางสอนที่ใช้เวลานานในการจัดด้วยมือแต่ละครั้ง มีงานวิจัยอยู่จำนวนมากที่พยายามแก้ปัญหานี้ แต่งานวิจัยเหล่านี้มุ่งจะที่จะแก้ปัญหาการจัดตารางสอน ที่มีลักษณะเฉพาะของสถาบันการศึกษาหนึ่งเท่านั้น ลักษณะเฉพาะเช่นคาบเวลาสอนไม่เท่ากัน เวลาสอน เวลาหยุดพัก จัดตอนเรียน และอื่นๆ ขั้นตอนวิธีเชิงพันธุกรรมเป็นวิธีหาคำตอบค่าเหมาะสมที่สุด (Optimal solution) ที่มีความง่ายในการปรับให้เข้ากับปัญหา ในงานวิจัยนี้จึงจัดทำโปรแกรมประยุกต์สำหรับจัดตารางสอน โดยนำขั้นตอนวิธีเชิงพันธุกรรมมาปรังปรุงการเข้ารหัส การไขว้เปลี่ยน การคัดเลือกความหลากหลาย เพื่อให้สอดคล้องกับสภาพของปัญหา โดยใช้ข้อมูลการจัดตารางสอนของคณะเศรษฐศาสตร์ เป็นต้นเแบบ โปรแกรมประยุกต์นี้สามารถจัดตารางสอนได้โดยอัตโนมัติ มีส่วนต่อประสานกับผู้ใช้ (User interface) เป็นแบบกราฟิก ทำงานบนเครื่องคอมพิวเตอร์ส่วนบุคคลเพียงเครื่องเดียว จัดตารางสอนได้โดยไม่มีข้อขัดแย้งกับเงื่อนไขหลักและเงื่อนไขรอง ในการทดลองจัดด้วยจำนวนห้อง 20 ห้อง 400 ชั้นเรียน โปรแกรมสามารถจัดเสร็จได้ในจำนวนรุ่นที่น้อยและเวลาที่น้อย เมื่อเทียบกับการจัดด้วยมือ

Other Abstract (Other language abstract of ETD)

The timetatbling problem comes up every year in educational institutions, which has often been solved by human. There have been a lot of research to solve this problem. The problem usually varies significantly from institution to institution in terms of specific requirements and constraints such as time-slot period, teaching time, break time, sections etc. Many current university timetabling systems are often applied only in the institutions where they were designed. Genetic algorithm is optimization method that is easy to implement, and to optimization problem. This work adopted and modified chromosome representation, crossover and selection of genetic algorithm to develop an automated timetabling program, with information of the Faculty of Economic, Chulalongkorn University, as a prototype. The application is able to work on a stand alone computer, and run on Windows with graphic user interface. It can produce the timetables under hard and soft constraints. The program produces satisfied results within acceptable time and number of generations for 20 rooms and 400 classes problem

Link to Full Text

Share

COinS