A Differential Evolution Algorithm for U – Shaped Assembly Line Balancing to Optimize Cycle Time When Number of Workstations Known

Abstract

This research presents a Differential Evolution (DE) algorithm for solving U-shaped assembly line balancing type 2 problems. The minimum cycle time in a just-in-time production line for producing a single product with a certain number of workstations was investigated by developing solution methods and testing with 15 problem sets (101 instances). The problems were divided into 10 medium-scale problem sets with 21-58 tasks (50 instances) and 5 large-scale problem sets with 70-297 tasks (51 instances). The results were compared with those obtained from the rules-based heuristic; two rules and three rules. In medium-scale problems, the DE algorithm generated better cycle time than two rules and three rules for 39 instances (78%) and 14 instances (28%), respectively. The average computational time (CPU) was between 0.02-0.40 second/instance. For the large-scale problems, the DE algorithm provided 38 better solutions (76%) compared with two rules and 3 better solutions (6%) compared with three rules. The average computational time was between 0.39-40 second/instance. Therefore, the DE algorithm is a potential and effective approach to solve the U-shape assembly line balancing type 2 problems.

งานวิจัยนี้นำเสนอวิธีการวิวัฒนาการโดยใช้ผลต่าง (Differential Evolution Algorithm: DE) สำหรับการแก้ปัญหาการจัดสมดุลสายการประกอบแบบตัวยูประเภทที่ 2 (U-Shaped assembly line balancing type 2: UALBP-2) ที่มีความสำคัญต่อการผลิตแบบทันเวลา (Just In Time Production) เพื่อหารอบเวลาการผลิต (cycle time) ที่ต่ำที่สุด สำหรับการผลิตสินค้าชนิดเดียว กรณีทราบจำนวนสถานีงานที่แน่นอน โดยในการศึกษาได้พัฒนาวิธีการค้นหาคำตอบและทำการทดสอบกับปัญหาการจัดสมดุลสายการประกอบจำนวน 15 ชุดปัญหา (101 ตัวอย่าง) แบ่งเป็นปัญหาขนาดกลางที่มีจำนวนงาน 21-58 งาน จำนวน 10 ชุดปัญหา (50 ตัวอย่าง) และปัญหาขนาดใหญ่ ที่มีจำนวนงาน 70-297 งาน จำนวน 5 ชุดปัญหา (51 ตัวอย่าง) จากนั้นทำการเปรียบเทียบผลกับวิธี Two Rules และวิธี Three Rules ของ Rules-based heuristic พบว่า ในปัญหาขนาดกลางวิธีการวิวัฒนาการโดยใช้ผลต่างสามารถหาคำตอบได้รอบเวลาการผลิตที่ดีกว่าวิธี Two Rules 39 ปัญหา (ร้อยละ 78) และดีกว่าวิธี Three Rules 14 ปัญหา (ร้อยละ 28) โดยใช้เวลาเฉลี่ยในการคำนวณอยู่ระหว่าง 0.02-0.40 วินาที/ปัญหา ส่วนในปัญหาขนาดใหญ่วิธีการวิวัฒนาการโดยใช้ผลต่างสามารถหาคำตอบได้รอบเวลาการผลิตที่ดีกว่าวิธี Two Rules 38 ปัญหา (ร้อยละ 76) และวิธี Three Rules 3 ปัญหา (ร้อยละ 6) โดยใช้เวลาเฉลี่ยในการคำนวณอยู่ระหว่าง 0.39-40 นาที/ปัญหา ดังนั้นวิธีวิวัฒนาการโดยใช้ผลต่างจึงเป็นวิธีที่สามารถใช้ในการแก้ปัญหาการจัดสมดุลสายการประกอบแบบตัวยูประเภทที่ 2 ได้อย่างมีประสิทธิภาพ