Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
Makespan calculation analysis for job shop scheduling problem
Year (A.D.)
2017
Document Type
Thesis
First Advisor
พันทิพา ทิพย์วิวัฒน์พจนา
Faculty/College
Faculty of Science (คณะวิทยาศาสตร์)
Department (if any)
Department of Mathematics and Computer Science (ภาควิชาคณิตศาสตร์และวิทยาการคอมพิวเตอร์)
Degree Name
วิทยาศาสตรมหาบัณฑิต
Degree Level
ปริญญาโท
Degree Discipline
คณิตศาสตร์
DOI
10.58837/CHULA.THE.2017.787
Abstract
เมคสแปนในปัญหาการจัดตารางการผลิตแบบตามสั่งเป็นค่าที่สำคัญในการหาค่าผลเฉลยใกล้เคียงของการค้นหาแบบทาบู อย่างไรก็ตามขั้นตอนการหาค่าผลเฉลยใกล้เคียงเป็นส่วนที่ใช้เวลาประมวลผลนานที่สุด วิทยานิพนธ์เล่มนี้ทำการปรับปรุงเทคนิคการหาค่าผลเฉลยใกล้เคียงด้วยค่าเมคสแปนที่ถูกเสนอโดย Nowicki และ Smutnicki (2005) และเปรียบเทียบความซับซ้อนของเวลาของวิธีการหาค่าผลเฉลยใกล้เคียง ระหว่างวิธีการของ Nowicki และ Smutnicki และวิธีการที่ได้ปรับปรุงขึ้น ความแตกต่างที่สำคัญของทั้งสองวิธีการคือการหาตำแหน่งสำคัญบางตำแหน่งบนลำดับโทโพโลยีของผลเฉลยเมล็ดพันธุ์ ทั้งสองวิธีการใช้ปัญหามาตรฐานที่มีจำนวนโอเปอเรชันไม่เกิน 400 โอเปอเรชัน ในการทดสอบ ผลการทดลองพบว่า ขั้นตอนวิธีการค้นหาแบบทาบูที่ใช้ขั้นตอนการหาค่าผลเฉลยใกล้เคียงด้วยวิธีการที่ได้ปรับปรุงขึ้น ใช้เวลาประมวลผลน้อยกว่าวิธีการค้นหาแบบทาบูที่ใช้ขั้นตอนการหาค่าผลเฉลยใกล้เคียงด้วยวิธีการของ Nowicki และ Smutnicki
Other Abstract (Other language abstract of ETD)
Makespan in a job shop scheduling problem is a significant value for evaluating a neighborhood solution in the move evaluation strategy of a standard tabu search method. However, the move evaluation is the most time-consuming part of the algorithm. In this work, we improve the move evaluation complexity of the approach by Nowicki and Smutnicki (2005) and compare the move evaluation complexity of the approach by Nowicki and Smutnicki and our approach. The main difference in both approaches is the way to evaluate some specific positions in a topological order of a seed solution. Both algorithms are tested on standard benchmarks with the size at most 400 operations. The results show that the computation time of using our move evaluation in a tabu search algorithm is smaller than the Nowicki and Smutnicki's move evaluation.
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
โฮชิน, วันเฉลิม, "การวิเคราะห์การคำนวณเมคสแปนสำหรับปัญหาการจัดตารางการผลิตแบบตามสั่ง" (2017). Chulalongkorn University Theses and Dissertations (Chula ETD). 1277.
https://digital.car.chula.ac.th/chulaetd/1277