วิธีการแก้ปัญหาของการจัดตารางงานโดยใช้วิธีการผสมผสาน เจเนติกอัลกอริทึมกับโลคอลเสิร์ช

Abstract

งานวิจัยนี้มีเป้าประสงค์เพื่อประยุกต์ใช้วิธีการที่อยู่ในกลุ่มของปัญญาประดิษฐ์ (Artificial Intelligence : AI) โดยนำวิธีการเจเนติกอัลกอริทึม (Genetic Algorithm : GA) และวิธีการ ผสมผสาน (Hybrid) โลคอลเสิร์ช (Local search) ในการจัดตารางการทำงานให้กับเครื่องจักรในโรงงาน ผลิตชิ้นส่วนเครื่องจักรกล ซึ่งวิธีของเจเนติกอัลกอริทึมเป็นวิธีแก้ปัญหาชนิดหนึ่งที่อาศัยหลักการเชิง พันธุกรรม เพื่อนำมาแก้ไขการจัดตารางการทำงาน และยังนำวิธีการผสมผสานโลคอลเสิร์ชมาใช้ เพื่อเพิ่มศักยภาพของวิธีการเจเนติกอัลกอริทึมให้ดีขึ้น ซึ่งถือว่าเป็นการผสมผสานเพื่อการจัดตาราง การทำงานให้ได้ค่าเมคสแปน (Makespan) ที่ต่ำสุด การศึกษานี้ได้นำปัญหาของการจัดตารางการ ผลิต (Scheduling Problems) ของโรงงานผลิตชิ้นส่วนเครื่องจักรกลมาเป็นตัวแบบในการพัฒนา โปรแกรมและประมวลผลเพื่อเปรียบเทียบทำงานของวิธีเจเนติกอัลกอริทึมอย่างเดียว กับวิธี ผสมผสานเจเนติกอัลกอริทึมกับโลคอลเสิร์ชกับปัญหาแบบขนาดเลงกและปัญหาขนาดใหญ่ โดยการศึกษาเพื่อหาข้อสรุปเกี่ยวกับการหาค่าขอบเขตต่ำสุด (Lower bound) และเวลาการทำงาน ของโปรแกรมที่พัฒนาขึ้น จากการวิจัยพบว่า วิธีผสมผสานเจเนติกอัลกอริทึมกับโลคอลเสิร์ชค้นหา คำตอบพบได้ดีกว่าวิธีเจเนติกอัลกอริทึม และการหาค่าคำตอบเมื่อเทียบกับค่าขอบเขตต่ำสุดได้ ใกล้เคียงกว่า ทั้งปัญหาขนาดเล็กและปัญหาขนาดใหญ่ ซึ่งโปรแกรมที่พัฒนาสามารถจัดตารางงาน เพื่อให้ได้ค่าเมคสแปนต่ำสุดในการผลิตได้

Solving Sequence of Job Scheduling Problem by Genetic Algorithm with Local Search

This research presents algorithms for solving a scheduling problem for a machinery part manufacturer. An artificial intelligence-based genetic algorithm (GA) and a hybrid GA/local search were developed. The objective of the project is to minimize makespan. Experiments for evaluating the performance of the solutions, carried out in terms of quality and computational time, of both algorithms were conducted on problems of various sizes. The results showed that the hybrid approach outperformed GA in most of the cases.