ไอเดีย #39: ระบบจัดตารางสอนอัตโนมัติ

ทุกต้นปีการศึกษา จะมีครูฝ่ายวิชาการคนหนึ่งที่นั่งจัดตารางสอนจนดึกเป็นสัปดาห์ ครูคนนี้สอนได้แค่บางคาบเพราะเป็นหัวหน้างาน ห้องวิทยาศาสตร์มีห้องเดียว วิชาพละต้องไม่อยู่หลังพักกลางวัน แก้ช่องหนึ่งแล้วอีกสามช่องชนกันทันที นี่คือปัญหาคลาสสิกทางคอมพิวเตอร์ที่เรียกว่า constraint satisfaction และเป็นโปรเจกต์ที่ทำให้ได้ใช้อัลกอริทึมกับงานจริง ไม่ใช่แค่ในห้องเรียน

ใครจะใช้

• ฝ่ายวิชาการ — กรอกข้อมูล ตั้งเงื่อนไข สั่งจัดตารางและปรับแก้
• ครู — แจ้งช่วงเวลาที่สอนไม่ได้ และดูตารางสอนของตัวเอง
• นักเรียนและผู้ปกครอง — ดูตารางเรียนของห้อง

ฟีเจอร์ขั้นต่ำ (MVP)

• ข้อมูลตั้งต้น: ห้องเรียน ครู วิชา จำนวนคาบต่อสัปดาห์ของแต่ละวิชาในแต่ละห้อง และห้องพิเศษ เช่น ห้องคอมพิวเตอร์ ห้องแล็บ
• เงื่อนไขบังคับ (hard constraint): ครูหนึ่งคนสอนได้ทีละห้อง ห้องพิเศษใช้ได้ทีละกลุ่ม ครูไม่ถูกจัดในเวลาที่แจ้งว่าไม่ว่าง
• เงื่อนไขที่อยากได้ (soft constraint): ไม่สอนวิชาเดียวกันติดกันเกินสองคาบ กระจายคาบให้ทั่วสัปดาห์ ครูไม่มีช่องว่างมากเกินไป
• กดจัดอัตโนมัติ แล้วแสดงคะแนนคุณภาพของตารางและรายการเงื่อนไขที่ยังไม่ผ่าน
• ปรับแก้ด้วยมือแบบลากวาง โดยระบบเตือนทันทีถ้าชนเงื่อนไขบังคับ
• พิมพ์ตารางรายห้อง รายครู และรายห้องพิเศษ

ต่อยอดได้อีก

• ล็อกบางคาบไว้ก่อน เช่น คาบชุมนุมหรือกิจกรรมทั้งโรงเรียน แล้วให้ระบบจัดส่วนที่เหลือ
• ระบบหาครูสอนแทนเมื่อมีครูลา โดยดูจากครูที่ว่างในคาบนั้น
• เปรียบเทียบหลายตารางที่ได้จากการรันหลายรอบ แล้วเลือกตารางที่ดีที่สุด
• สรุปภาระงานสอนรายครูต่อสัปดาห์

โครงข้อมูลตั้งต้น

• teachers — id, name, max_periods_per_day
• teacher_unavailable — id, teacher_id, day_of_week, period_no
• rooms — id, name, room_type, capacity
• course_loads — id, classroom_id, subject_id, teacher_id, periods_per_week, required_room_type
• timetable_slots — id, run_id, course_load_id, day_of_week, period_no, room_id, is_locked

ระดับความยาก และสิ่งที่จะได้เรียนรู้

ระดับ ท้าทาย ส่วนเว็บจัดการข้อมูลทำด้วย Yii2 หรือ Laravel + PostgreSQL/MySQL ส่วนตัวจัดตารางแยกเป็น worker ด้วยภาษาที่ถนัด เช่น PHP หรือ Python สิ่งที่จะได้ฝึก:

• อัลกอริทึม backtracking สำหรับเงื่อนไขบังคับ และ heuristic อย่าง simulated annealing หรือ genetic algorithm สำหรับปรับคุณภาพ
• การออกแบบฟังก์ชันให้คะแนน (cost function) ที่ฝ่ายวิชาการปรับน้ำหนักได้
• การรันงานหนักเบื้องหลังผ่าน queue แล้วแจ้งผลเมื่อเสร็จ
• การทำหน้าตารางแบบลากวางด้วย JavaScript

ข้อควรระวัง

• บางชุดข้อมูลไม่มีคำตอบเลย เช่น ครูคนเดียวถูกกำหนดคาบเกินเวลาที่ว่าง ระบบควรตรวจและบอกสาเหตุก่อนเริ่มรัน ไม่ใช่รันวนจนหมดเวลา
• ตั้ง time limit ให้การคำนวณเสมอ และเก็บผลดีที่สุดที่หาได้ไว้
• ถ้าฝ่ายวิชาการสองคนแก้ตารางเดียวกันพร้อมกัน อาจเขียนทับกัน ควรมีการล็อกหรือเวอร์ชันของตาราง

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