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

Job Shop Scheduling Optimisation Using Harmony Search Algorithm

Abstract

ปัญหาการจัดตารางการผลิตแบบทำตามสั่งเป็นปัญหาที่เป็นที่รู้จักกันอย่างแพร่หลาย ปัญหานี้ถูกจัดให้อยู่ในกลุ่มเอ็นพี แบบยาก (NP-hard) ซึ่งไม่สามารถหาค่าคำตอบที่ดีที่สุดได้ในเวลาโพลิโนเมียล ดังนั้นวิธีการในกลุ่มเมต้าฮิวริสติกที่ชื่อว่า วิธีฮาร์โมนี่เสริจน์ (HSA) ซึ่งเลียนแบบการหาเมโลดี้ทมีี่ความไพเราะในการประสานเสียงของเครอื่ งดนตรี จึงถูกนำเสนอในการหาคา่ คำตอบทดีี่ทสีุ่ดของปัญหาทดสอบการจัดตารางการผลิตแบบทำตามสั่งจำนวน 5 ปัญหา คือ FT06 (6 x 6), LA01 (10 x 5), LA06 (10 x 10), LA11 (15 x 5) และ LA16 (20 x 5) (เครื่องจักร x งาน) ตามลำดับ ในการศึกษาครั้งนี้ได้แบ่งการทดลองออกเป็นสองส่วน คือ การทดลองที่หนึ่งเพื่อหาค่าปัจจัยที่ดีที่สุดของวิธีฮาร์โมนี่เสริจน์ โดยใช้การออกแบบการทดลองแบบ 2 k แฟกทอเรียล และการทดลองที่สอง ทำการ
เปรียบเทียบค่าคำตอบที่ดีที่สุดที่ได้จากการทดลองกับค่าคำตอบที่ดีที่สุดของปัญหาทดสอบแต่ละปัญหา และเปรียบเทียบกับค่าคำตอบที่ได้จากวิธีGA และ SA จากผลการทดลองพบว่าปัญหาทดสอบ FT06 LA01 LA06 และ LA11 วิธีฮาร์โมนี่เสริจน์สามารถหาค่าคำตอบที่ดีที่สุดยกเว้นปัญหาทดสอบ LA16 ซึ่งเป็นปัญหาขนาดใหญ่ไม่สามารถหาค่าคำตอบที่ดีที่สุด แต่สามารถหาค่าคำตอบที่ใกล้เคียงพบในขณะที่เมื่อเปรียบเทียบกับวิธีGA (Genetic Algorithm) และ SA (Simulated Annealing) พบว่า วิธีHSA สามารถหาค่าคำตอบได้ดีกว่าวิธีการทั้งสอง

Job shop scheduling problem (JSSP) is one of the most famous scheduling, most of which are categorized into non-deterministic
polynomial-hard (NP-hard) and cannot be solved in polynomial time. In this study, therefore, a metaheuristic called Harmony Search
Algorithm (HSA), which is based on the melody fine tuning conducted by musician for optimising the synchronisation of the music,
was proposed for finding optimal solution to five benchmarking job shop scheduling problems including problem FT06 (6 x 6), LA01
(10 x 5), LA06 (10 x 10), LA11 (15 x 5) and LA16 (20 x 5) (machine x job), respectively. In this research, Experiments were separated be two parts. The first experiment was used to systematically identify the best parameters of HSA by using 2 k factorial design and the second experiment was used to compare its performance with Genetic Algorithm (GA), Simulated Annealing (SA) and optimal solution of each problem. From the result of experiments, it was found that HAS can find the optimal solution for most problems, FT06, LA01, LA06 and LA11, except LA16, but it can find near optimal solution. For comparing with GA and SA, it can be seen that HSA outperformed both GA and SA.