การวิเคราะห์การคำนวณเมคสแปนสำหรับปัญหาการจัดตารางการผลิตแบบตามสั่ง

วันเฉลิม โฮชิน

Please use this identifier to cite or link to this item: https://cuir.car.chula.ac.th/handle/123456789/72802

Title:	การวิเคราะห์การคำนวณเมคสแปนสำหรับปัญหาการจัดตารางการผลิตแบบตามสั่ง
Other Titles:	Makespan calculation analysis for job shop scheduling problem
Authors:	วันเฉลิม โฮชิน
Advisors:	พันทิพา ทิพย์วิวัฒน์พจนา
Other author:	จุฬาลงกรณ์มหาวิทยาลัย. คณะวิทยาศาสตร์
Advisor's Email:	Phantipa.T@Chula.ac.th
Subjects:	การกำหนดงานการผลิต การกำหนดลำดับงาน การบริหารงานผลิต -- การประมวลผลข้อมูล Production scheduling Scheduling Production management -- Data processing การกำหนดงานการผลิต การกำหนดลำดับงาน การบริหารงานผลิต -- การประมวลผลข้อมูล Production scheduling Scheduling Production management -- Data processing
Issue Date:	2560
Publisher:	จุฬาลงกรณ์มหาวิทยาลัย
Abstract:	เมคสแปนในปัญหาการจัดตารางการผลิตแบบตามสั่งเป็นค่าที่สำคัญในการหาค่าผลเฉลยใกล้เคียงของการค้นหาแบบทาบู อย่างไรก็ตามขั้นตอนการหาค่าผลเฉลยใกล้เคียงเป็นส่วนที่ใช้เวลาประมวลผลนานที่สุด วิทยานิพนธ์เล่มนี้ทำการปรับปรุงเทคนิคการหาค่าผลเฉลยใกล้เคียงด้วยค่าเมคสแปนที่ถูกเสนอโดย Nowicki และ Smutnicki (2005) และเปรียบเทียบความซับซ้อนของเวลาของวิธีการหาค่าผลเฉลยใกล้เคียง ระหว่างวิธีการของ Nowicki และ Smutnicki และวิธีการที่ได้ปรับปรุงขึ้น ความแตกต่างที่สำคัญของทั้งสองวิธีการคือการหาตำแหน่งสำคัญบางตำแหน่งบนลำดับโทโพโลยีของผลเฉลยเมล็ดพันธุ์ ทั้งสองวิธีการใช้ปัญหามาตรฐานที่มีจำนวนโอเปอเรชันไม่เกิน 400 โอเปอเรชัน ในการทดสอบ ผลการทดลองพบว่า ขั้นตอนวิธีการค้นหาแบบทาบูที่ใช้ขั้นตอนการหาค่าผลเฉลยใกล้เคียงด้วยวิธีการที่ได้ปรับปรุงขึ้น ใช้เวลาประมวลผลน้อยกว่าวิธีการค้นหาแบบทาบูที่ใช้ขั้นตอนการหาค่าผลเฉลยใกล้เคียงด้วยวิธีการของ Nowicki และ Smutnicki
Other Abstract:	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.
Description:	วิทยานิพนธ์ (วท.ม.)--จุฬาลงกรณ์มหาวิทยาลัย, 2560
Degree Name:	วิทยาศาสตรมหาบัณฑิต
Degree Level:	ปริญญาโท
Degree Discipline:	คณิตศาสตร์
URI:	http://cuir.car.chula.ac.th/handle/123456789/72802
URI:	http://doi.org/10.58837/CHULA.THE.2017.787
metadata.dc.identifier.DOI:	10.58837/CHULA.THE.2017.787
Type:	Thesis
Appears in Collections:	Sci - Theses

Files in This Item:

File	Description	Size	Format
5872052623_Sc_2017.pdf		1.67 MB	Adobe PDF	View/Open

Show full item record