ฮิวริสติกแบบกำหนดการเชิงเส้นจำนวนเต็มผสมสำหรับปัญหาการจัดตารางการผลิตของระบบการผลิตแบบตามงาน

Mixed integer linear programming based Heuristic for job shop scheduling problem

Name: พัชรินทร์ ศรีสองสกุล

ThaSH: มหาวิทยาลัยบูรพา.สาขาวิชาวิศวกรรมอุตสาหการ

ThaSH: การกำหนดงานการผลิต

ThaSH: ฮิวริสติกอัลกอริทึม

Abstract: งานวิจัยนี้เสนอวิธีการจัดตารางการผลิตของระบบการผลิตแบบตามงานที่มีสองจุดประสงค์คือการทำให้เวลาปิดงานของระบบและเวลาสายสูงสุดของทุกงานต่ำที่สุด การจัดตารางการผลิตเดิมของกระบวนการผลิตชิ้นส่วนยานยนต์แห่งหนึ่งที่มีลักษณะการผลิตเป็นระบบการผลิตแบบตามงานใช้วิธีการกำหนดลำดับความสำคัญของงานจากกำหนดส่งมอบเร็วกว่าให้ทำการผลิตก่อน (Earliest due date, EDD) ซึ่งให้ผลเวลาปิดงานของระบบสูงและไม่สามารถส่งมอบงานได้ทันตามกำหนด งานวิจัยนี้ออกแบบฮิวริสติกแบบกำหนดการเชิงเส้นจำนวนเต็มผสม (Mixed integer linear programming based heuristic, MILP_H) โดยมีการแบ่งงานที่ต้องการจัดตารางการผลิตที่มีจำนวนมากออกเป็นกลุ่มย่อยตามกฏลำดับความสำคัญแบบ EDD ตารางการผลิตของกลุ่มย่อยหนึ่ง ๆ ถูกสร้างขึ้นจากแบบจำลองกำหนดการเชิงเส้นจำนวนเต็มผสม (Mixed integer linear programming, MILP) หากไม่มีงานสายเกิดขึ้นจะใช้ MILP ที่มีจุดประสงค์ที่ทำให้เวลาปิดงานของระบบต่ำที่สุด แต่หากมีงานสายเกิดขึ้นจะใช้ MILP ที่มีจุดประสงค์ที่ทำให้ผลรวมแบบถ่วงน้ำหนักของเวลาปิดงานของระบบและเวลาสายสูงสุดของทุกงานต่ำที่สุด โดยให้น้ำหนักเวลาสายสูงสุดมากกว่าเวลาปิดงานเพื่อลดเวลาการทำงานล่วงเวลาในการผลิตงานที่เสร็จไม่ทันตามกำหนด ส่งมอบตารางการผลิตของกลุ่มย่อยแต่ละกลุ่มย่อยจะถูกนำมารวมกันตามลำดับกลุ่ม EDD ให้เป็นตารางการผลิตสำหรับใช้งานซอฟต์แวร์ OpenSolver ด้วยโปรแกรมประมวลผล Gurobi 7.5.2 ถูกนำมาใช้ในการหาผลลัพธ์ที่เหมาะสมของแบบจำลอง MILPโดยกำหนดเวลาประมวลผลสูงสุด เท่ากับ 600 วินาที การทดสอบประสิทธิภาพเปรียบเทียบกับวิธีการเดิมด้วยปัญหาการจัดตารางการผลิตจริงและปัญหาจำลองด้วยคอมพิวเตอร์รวม 15 ปัญหา จำนวนงานเฉลี่ย 47 งาน และแต่ละงานมีขั้นตอนการผลิตที่แตกต่างกัน 4 เครื่องจักรจากทั้งหมด 9 เครื่องจักรผลการวิจัยพบว่า ตารางการผลิตที่สร้างด้วยวิธี MILP_H สามารถลดเวลาปิดงานลงได้เฉลี่ย 220 นาทีและลดเวลาสายสูงสุดลงได้เฉลี่ย 74 นาที หรือคิดเป็นการลดลงร้อยละ 4.22 และ 22.62 ตามลำดับ

Abstract: This research proposed a job shop scheduling method with two objectives which are minimizing the makespan and the maximum tardiness. The earliest due date rule was used for solving this problem which is the job shop scheduling problem in an automotive part manufacturing process. Production schedulesgenerated by using the EDD method werenot effective when consider theirs makespan and the number of tardy jobs. This research developed a mixed integer linear programming based heuristic (MILP_H) to build the production schedules. The MILP_H is the heuristic for dividing the jobs to be scheduled to several subgroups withthe EDD rule. Then one of the proposed mixed integer linear programming (MILP) models isused for generating a schedule for each subgroup. If all jobs in the subgroup have completed before their due date the MILP with minimizing the makespan will be chosen for scheduling. Otherwise, the MILP with minimizing the total weighted makespan and the maximum tardiness will be used. The subgroup schedules then are combined in the EDD group order to a production schedule for practice. This research assigned the weight of the maximum tardiness more than the makespan in the purpose of reduction the extra time for producing the tardy jobs to be finished within their due date. The OpenSolver software with Gurobi 7.5.2 optimizer was used to find the solution from the proposed MILP models. The maximum computation time was set at 600 seconds. The performance of the MILP_H was evaluated by comparing with the EDD method. The 15-problem set consistsof real scheduling problems and simulation problems with the average number of jobs equal to 47 jobs and each job has different process steps produced by 4 machines form 9 possible machines. The results revealed that the MILP_H can create production schedules that the average makespan was reduced 200 minutes or 4.22% and the average of the maximum tardiness was reduced 74 minutes or 22.62%.

มหาวิทยาลัยบูรพา. สำนักหอสมุด

Address: ชลบุรี

Email: buulibrary@buu.ac.th

Name: จักรวาล คุณะดิลก

Role: อาจารย์ที่ปรึกษาหลัก

Created: 2561

Modified: 2563-07-14

Issued: 2563-07-14

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

application/pdf

CallNumber: ว 670.285 พ523ฮ

tha

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

Level: ปริญญาโท

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

Grantor: มหาวิทยาลัยบูรพา

©copyrights มหาวิทยาลัยบูรพา

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	58920782.pdf	4.66 MB	14	2025-07-06 10:55:42

ใช้เวลา

0.027125 วินาที