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

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

Name: Ornrumpha Srimongkolkul

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.

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

Chulalongkorn University. Office of Academic Resources

Address: BANGKOK

Email: cuir@car.chula.ac.th

Name: Prabhas Chongstitvatana

Role: advisor

Created: 2014

Modified: 2016-08-19

Issued: 2016-08-19

วิทยานิพนธ์/Thesis

application/pdf

URL: http://cuir.car.chula.ac.th/handle/123456789/45679

eng

DegreeName: Master of Engineering

Level: Master's Degree

Descipline: Computer Engineering

Grantor: Chulalongkorn University

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	5670462721.pdf	1.55 MB	21	2022-09-26 15:23:36

ใช้เวลา

0.021272 วินาที