Chulalongkorn University Theses and Dissertations (Chula ETD)

การประยุกต์ใช้เมมเมติกอัลกอริทึมสำหรับปัญหาการจัดสมดุลที่มีหลายวัตถุประสงค์บนสายการประกอบผลิตภัณฑ์ผสมแบบลักษณะตัวยูในระบบผลิตแบบทันเวลาพอดี

Other Title (Parallel Title in Other Language of ETD)

Application of memetic algorithms for multi-objective balancing problem on mixed-model u-shaped assembly line in jit production systems

Year (A.D.)

2008

Document Type

Thesis

First Advisor

ปารเมศ ชุติมา

Faculty/College

Faculty of Engineering (คณะวิศวกรรมศาสตร์)

Degree Name

วิศวกรรมศาสตรมหาบัณฑิต

Degree Level

ปริญญาโท

Degree Discipline

วิศวกรรมอุตสาหการ

DOI

10.58837/CHULA.THE.2008.1518

Abstract

งานวิจัยนี้ทำการศึกษาหาวิธีการอัลกอริทึมแบบใหม่ที่เรียกว่า วิธี Combinatorial Optimization with Coincidence Algorithm (COIN) หรือวิธีอัลกอริทึมการบรรจวบ และทำการพัฒนาวิธีอัลกอริทึมการบรรจวบรวมกับเมมเมติกอัลกอริทึม เพื่อนำมาประยุกต์ใช้ในการหาคำตอบที่มีหลายวัตถุประสงค์ สำหรับจัดสมดุลสายการประกอบแบบผลิตภัณฑ์ผสมที่มีลักษณะของสายการผลิตแบบตัวยู ในระบบผลิตแบบทันเวลาพอดี จะพิจารณาฟังก์ชันวัตถุประสงค์ทั้งหมด 3 วัตถุประสงค์พร้อมกันคือ จำนวนสถานีงานมีจำนวนน้อยที่สุด งานมีผลต่างความสัมพันธ์ในสถานีงานมีค่าน้อยที่สุดและความผันแปรของเวลาในสถานีงานทั้งหมดมีค่าน้อยที่สุด ซึ่งจะทำการเปรียบเทียบประสิทธิภาพในขนาดปัญหาทดลอง 19 36 61 และ 111 ขั้นงาน กับอัลกอริทึมที่เป็นที่นิยมและได้คำตอบที่ดีในปัจจุบันคือวิธีเจนเนติกอัลกอริทึมแบบ NSGA-II (NSGA-II) และวิธีเมมเมติกอัลกอริทึมแบบ NSGA-II (M-NSGA-II) จากการเปรียบเทียบคำตอบจากตัวชี้วัดสมรรถนะ 4 ด้าน คือในด้านคำตอบที่มีการลู่เข้าใกล้กลุ่มคำตอบที่ดีที่สุดที่แท้จริง ด้านการกระจายของกลุ่มคำตอบที่หาได้ ด้านอัตราส่วนของจำนวนกลุ่มคำตอบที่หาได้เทียบเท่ากับกลุ่มคำตอบที่แท้จริง และด้านเวลาในการประมวลผลพบว่าในขนาดปัญหาเล็ก 19 และ 36 ขั้นงานวิธีวเมมเมติกอัลกอริทึมแบบ NSGA-II (M-NSGA-II) จะได้คำตอบที่ดีที่สุด ในส่วนปัญหาขนาดใหญ่ 61 และ 111 วิธีอัลกอริทึมการบรรจวบรวมกับเมมเมติกอัลกอริทึมจะเป็นวิธีที่มีประสิทธิภาพมากที่สุด โดยเฉพาะปัญหาขนาด 111 ขั้นงานสามารถหาค่าจำนวนสถานีงานน้อยสุดเท่ากับ 14 สถานีงาน ซึ่งเป็นค่าที่เหมาะสมที่สุด (Optimal Solution)

Other Abstract (Other language abstract of ETD)

This research studies a new algorithm called Combinatorial Optimization with Coincidence Algorithm (COIN) which is developed with a Memetic algorithm. The objective is to find a solution for multi-objective balancing problem on mixed-model u-shaped assembly lines in JIT production systems. We consider three objectives including minimum number workstations, minimum work relatedness and minimum workload smoothness. We compare efficiency of COIN with two popular and effective algorithms, a Genetic Algorithm (NSGA-II) and Memetic Algorithm (M-NSGA-II) in problems that contain 19, 36, 61, and 111 tasks. Four key performance indicators are selected for assessing results, Convergence to the Pareto-optimal set, Spread to the Pareto-optimal set, Ratio of Non-Dominated Solution, and algorithm's processing time. We find that in small sized problems, 19 and 36 tasks, Memetic algorithm (M-NSGA-II) gives the best results. However, in case of large sized problems, 61 and 111 tasks, applying COIN with Memetic algorithm gives us the best solutions. Especially, in a problem with 111 tasks, this leads us to the optimal solution which uses only 14 workstation.

Link to Full Text

Share

COinS