Please use this identifier to cite or link to this item:
https://cuir.car.chula.ac.th/handle/123456789/7928
| Title: | วิธีการการจัดตารางเครื่องจักรขนานที่สามารถควบคุมความเร็วเครื่องจักรได้ |
| Other Titles: | An approach of parallel machine scheduling with controllable machine speed |
| Authors: | ศราวุธ บุญอาชาทอง |
| Advisors: | อรรถสิทธิ์ สุรฤกษ์ นครทิพย์ พร้อมพูล |
| Other author: | จุฬาลงกรณ์มหาวิทยาลัย. คณะวิศวกรรมศาสตร์ |
| Advisor's Email: | athasit@cp.eng.chula.ac.th Nakornthip.p@chula.ac.th |
| Subjects: | การกำหนดงานการผลิต การควบคุมการผลิต -- แบบจำลองทางคณิตศาสตร์ อัลกอริทึม |
| Issue Date: | 2548 |
| Publisher: | จุฬาลงกรณ์มหาวิทยาลัย |
| Abstract: | ในงานวิจัยนี้เป็นการแก้ปัญหารการจัดตารางเครื่องจักรขนาน ที่สามารถควบคุมความเร็วของงานได้ และจะต้องทำให้ค่าฟังก์ชันวัตถุประสงค์ต่ำ ซึ่งค่าฟังก์ชันวัตถุประสงค์นี้ เป็นฟังก์ชันแสดงค่าใช้จ่ายที่เกิดจากเวลาปิดงาน (makespan) รวมกับค่าใช้จ่ายที่เกิดจากความเร็วของเครื่องจักรแต่ละเครื่อง โดยที่ฟังก์ชันค่าใช้จ่ายทั้งสองฟังก์ชันนี้เป็นฟังก์ชันพหุนาม อัลกอริธึมนี้มีค่าความซับซ้อนเป็นค่ากำลังสองของจำนวนงานทั้งหมด คูณกับเอกซ์โพเนนเชียลของจำนวนเครื่องจักร ในงานวิจัยนี้มีอัลกอริทึมหลักเป็นวนรอบทำซ้ำทดลองจัดตาราง เพื่อเลือกเครื่องจักรให้กับงานทุกๆ งาน จากนั้นจึงคำนวณค่าความเร็วของเครื่องจักรแต่ละเครื่อง เพื่อให้เกิดค่าใช้จ่ายต่ำที่สุดแล้วจึงใช้ความเร็วใหม่มาทดลองจัดตารางอีกครั้ง ซึ่งจะมีงานส่วนหนึ่งถูกกำหนดการจัดตารางให้เสร็จสิ้น และงานอีกส่วนหนึ่งต้องนำมาทดลองจัดตารางใหม่ จนกว่าจะได้ตารางครบทุกงาน การคำนวณความเร็วเครื่องจักรใช้การรวมฟังก์ชันค่าใช้จ่ายจากเครื่องจักรทุกๆ เครื่องเข้ากับค่าใช้จ่ายจากค่าเวลาปิดงาน เมื่อแปลงค่าความเร็วเครื่องจักรแต่ละเครื่องไปเป็นตัวแปรความเร็วอ้างอิง แล้วจึงหาค่าต่ำสุดของค่าใข้จ่ายรวมทั้งหมด ด้วยการหาอนุพันธ์ของฟังก์ชันค่าใช้จ่าย จากผลการทดสอบพบว่า อัลกอริทึมจากงานวิจัยนี้ให้ค่าใช้จ่ายเพิ่มขึ้นเล็กน้อย ในกรณีการทดสอบเวลาพร้อมเริ่มงานร่วมกัน และค่าใช้จ่ายเป็นฟังก์ชันเชิงเส้น แต่ในกรณีทดสอบอื่นๆ อีก 3 กรณี อัลกอริทึมจากงานวิจัยนี้ให้ค่าใช้จ่ายที่ลดลง |
| Other Abstract: | This research provides an algorithm for parallel machine scheduline with controllable job speed, in order to minimize an objective cost. The cost is expressed by the makespan cost and the job speed assigined costs, where the objective function is described by a polynomial function. Time complexity of the proposed algorithm is O(n [superscrip 2] 2 [superscrip m]) where n is the number of jobs and m denotes the number of machines. The main algorithm of thes research is to repeat a testing schedule for assigning a machine for each job. Then all machine speeds must be computer for minimizing the cost. After that, the schedule must be recalculated with the new speeds. Then some jobs are completely scheduled and the rest needs to be rescheduled until all jobs are completely scheduled. The machine speed computation is composed of all machine speed assigned cost functions and the makespan cost functions. The total cost function is obtained using the differentiation technique of the total cost function. Experimental results show that the total cost can increase only in the case of using common release time with linear cost function, otherwise the obtained costs decrease. |
| Description: | วิทยานิพนธ์ (วท.ม.)--จุฬาลงกรณ์มหาวิทยาลัย, 2548 |
| Degree Name: | วิทยาศาสตรมหาบัณฑิต |
| Degree Level: | ปริญญาโท |
| Degree Discipline: | วิทยาศาสตร์คอมพิวเตอร์ |
| URI: | http://cuir.car.chula.ac.th/handle/123456789/7928 |
| ISBN: | 9745325236 |
| Type: | Thesis |
| Appears in Collections: | Eng - Theses |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| sarawut.pdf | 1.23 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.