Chulalongkorn University Theses and Dissertations (Chula ETD)

MINIMIZING MAKESPAN USING NODE-BASED COINCIDENCE ALGORITHM IN THE PERMUTATION FLOWSHOP SCHEDULING PROBLEM

Other Title (Parallel Title in Other Language of ETD)

การแก้ปัญหาการจัดตารางการผลิตในระบบไหลเลื่อนโดยใช้เวลาในการดำเนินงานน้อยที่สุดด้วยอัลกอริทึมการบรรจวบ

Year (A.D.)

2014

Document Type

Thesis

First Advisor

Prabhas Chongstitvatana

Faculty/College

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

Degree Name

Master of Engineering

Degree Level

Master's Degree

Degree Discipline

Computer Engineering

DOI

10.58837/CHULA.THE.2014.1454

Abstract

Scheduling problem has always been an important problem in the industrial sectors since it creates huge impact on the overall performance of the manufacturing. Good scheduling can reduce overall production time which then leads to lower cost and good resource management. The permutation flowshop scheduling (PFSP) is the classic scheduling problems that attracts both business and research area for almost half a century. On research side, a variety of complex algorithms have been introduced to solve the problems and provide high quality of solutions. Nevertheless, these algorithms will be useless if they fail to implement in practice where computational time and complexity of algorithm become an important issue of concern. This research proposes a Node-Based Coincidence Algorithm (NB-COIN) for the permutation flowshop scheduling problems (PFSP) aimed at Makespan minimization. NB-COIN is proved to be an effective algorithm that can provide good quality solutions using small amount of time and resources. The results generated by NB-COIN are also better than other well-known algorithms in consideration. Based on the bench-mark data sets of Taillard, 10% of the solutions provided by the presented algorithm are optimal solutions. Moreover, the solutions found by NB-COIN are also achieve 0.96% gap from upper bound in average. More importantly, those solutions are found within a short time.

Other Abstract (Other language abstract of ETD)

การจัดตารางการผลิตเป็นสื่งที่สำคัญซึ่งส่งผลกระทบโดยตรงกับประสิทธิภาพในการดำเนินงานโดยรวมของโรงงานอุตสาหกรรม การจัดตารางการผลิตที่มีประสิทธิภาพสามารถลดเวลาในการผลิตซึ่งส่งผลให้โรงงานอุตสาหกรรมสามารถลดต้นทุนการผลิตและและจัดการทรัพยากรได้ดียิ่งขึ้น ปัญหาการจัดตารางการผลิตในระบบไหลเลื่อนได้รับความสนใจจากภาคธุรกิจและอุตสาหกรรมมานานกว่าครึ่งศตวรรษ นักวิจัยได้ออกแบบอัลกอรึทึมที่ซับซ้อนมากมายเพื่อช่วยแก้ปัญหาการจัดตารางการผลิตในระบบไหลเลื่อน และแสดงผลลัพธ์ที่มีประสิทธิภาพ อย่างไรก็ตามการออกแบบอัลกอรึทึมในงานวิจัยจำเป็นต้องคำนึงถึงความซับซ้อนของอัลกอรึทึมและเวลาที่ใช้ในการคำนวณเพื่อให้สามารถนำไปใช้ได้จริงในโรงงานอุตสาหกรรม วิทยานิพนธ์ฉบับนี้นำเสนออัลกอริทึมการบรรจวบเพื่อใช้ในการแก้ปัญหาการจัดตารางการผลิตโดยมีวัตถุประสงค์ในการใช้เวลาในการผลิตน้อยที่สุด ผลจากการทดลองอัลกอริทึมการบรรจวบได้รับการพิสูจน์ว่าเป็นอัลกอริทึมที่มีประสิทธิภาพในการหาคำตอบที่ดีโดยใช้ทรัพยากรและระยะเวลาในการคำนวณต่ำ ในการแก้ไขปัญหาการจัดตารางการผลิตนี้ อัลกอริทึมการบรรจวบได้เจอคำตอบที่ดีที่สุดเป็นจำนวน 10%ของคำตอบทั้งหมด และค่าเฉลี่ยของคำตอบห่างจากค่าที่ดีที่สุดคิดเป็น 0.98% นอกเหนือจากนั้น เวลาที่ใช้ในการหาคำตอบของอัลกอริทึมการบรรจวบยังมีค่าน้อยกว่าเวลาที่ใช้ในการหาคำตอบของอัลกอริทึมอื่นๆที่นำมาใช้เปรียบเทียบในวิทยานิพนธ์

Link to Full Text

Share

COinS