A Genetic Algorithm for Hybrid Flow Shop Scheduling

Abstract

The objective of this research is to apply a genetic algorithm for a hybrid flow shop scheduling problem in a steel plate production company. The manufacturing orders from customers are different in the characters of sizes and quantities. Besides, there are 3 main processes; slitter process, shear process, and squared shear process. Moreover, processes have unequal number of machines and production rates. The conditions are the products must go thru all processes sequentially and can select any machines in the process. The author applied a genetic algorithm with two objective functions; maximize makespan (Cmax) and minimized mean flowtime. The algorithm was tested with the problem size of 5, 10, 15, and 20 orders in order to be compared with the current method of the company. The results showed that the genetic algorithm could decreased the average makespan by 12.99% and decreased the average mean flowtime by 26.48%. Moreover, it found that the production planning was decreased by 58.74% when compared with the current method. In conclusion, the genetic algorithm could reduce makespan, mean flowtime, and production planning time significantly.

งานวิจัยนี้มีวัตถุประสงค์เพื่อพัฒนาขั้นตอนวิธีเชิงพันธุกรรมที่ช่วยในการจัดตารางการผลิตให้กับระบบการผลิตแบบไหลเลื่อนผสมของบริษัทจำหน่ายเหล็กแผ่น แต่ละคำสั่งซื้อจะต่างกันในเรื่องของขนาดและปริมาณตามความต้องการของลูกค้า ซึ่งมีกระบวนการผลิต 3 กระบวนการหลัก ได้แก่ กระบวนการตัดซอย กระบวนการตัดเฉือน กระบวนการตัดแผ่น โดยแต่ละกระบวนการมีจำนวนเครื่องจักร และเวลาในการผลิตที่ไม่เท่ากัน ภายใต้เงื่อนไขการผลิตที่ว่า ทุก ๆ คำสั่งซื้อ ต้องผ่านกระบวนการผลิตตามลำดับ แต่สามารถเลือกทำงานบนเครื่องจักรใดก็ได้ ในกระบวนเดียวกัน ดังนั้นผู้วิจัยจึงทำการประยุกต์ใช้ขั้นตอนวิธีเชิงพันธุกรรม (Genetic Algorithm: GA) โดยมีวัตถุประสงค์เพื่อหาเวลาในการดำเนินการผลิต (Makespan:Cmax ) และเวลาการไหลของงานโดยเฉลี่ย (Average Flow Time) ต่ำที่สุด โดยทดลองนำขั้นตอนวิธีเชิงพันธุกรรมไปใช้ในการจัดตารางการผลิตให้กับคำสั่งซื้อตัวอย่างจำนวน 5, 10 ,15 และ 20 คำสั่งซื้อ เพื่อเปรียบเทียบกับวิธีที่ใช้อยู่ในปัจจุบัน และวิธีการหาค่าแม่นยำ ผลการทดลองพบว่าขั้นตอนวิธีเชิงพันธุกรรมมีประสิทธิภาพดีที่สุด เมื่อทำการเปรียบเทียบกับวิธีที่ใช้อยู่ในปัจจุบัน ได้เวลาในการดำเนินการผลิตโดยเฉลี่ยลดลง 12.99% เวลาการไหลของงานเฉลี่ยโดยเฉลี่ยลดลง 26.48% และเวลาในการวางแผนการผลิตลดลง 58.74% สรุปแล้วขั้นตอนวิธีเชิงพันธุกรรมช่วยลดเวลาในการดำเนินการผลิต เวลาการไหลของงานโดยเฉลี่ย เวลาในการวางแผนการผลิต ได้อย่างมีนัยสำคัญ