วิทยานิพนธ์ (วท.ม.)--จุฬาลงกรณ์มหาวิทยาลัย, 2548

ในงานวิจัยนี้เป็นการแก้ปัญหารการจัดตารางเครื่องจักรขนาน ที่สามารถควบคุมความเร็วของงานได้ และจะต้องทำให้ค่าฟังก์ชันวัตถุประสงค์ต่ำ ซึ่งค่าฟังก์ชันวัตถุประสงค์นี้ เป็นฟังก์ชันแสดงค่าใช้จ่ายที่เกิดจากเวลาปิดงาน (makespan) รวมกับค่าใช้จ่ายที่เกิดจากความเร็วของเครื่องจักรแต่ละเครื่อง โดยที่ฟังก์ชันค่าใช้จ่ายทั้งสองฟังก์ชันนี้เป็นฟังก์ชันพหุนาม อัลกอริธึมนี้มีค่าความซับซ้อนเป็นค่ากำลังสองของจำนวนงานทั้งหมด คูณกับเอกซ์โพเนนเชียลของจำนวนเครื่องจักร ในงานวิจัยนี้มีอัลกอริทึมหลักเป็นวนรอบทำซ้ำทดลองจัดตาราง เพื่อเลือกเครื่องจักรให้กับงานทุกๆ งาน จากนั้นจึงคำนวณค่าความเร็วของเครื่องจักรแต่ละเครื่อง เพื่อให้เกิดค่าใช้จ่ายต่ำที่สุดแล้วจึงใช้ความเร็วใหม่มาทดลองจัดตารางอีกครั้ง ซึ่งจะมีงานส่วนหนึ่งถูกกำหนดการจัดตารางให้เสร็จสิ้น และงานอีกส่วนหนึ่งต้องนำมาทดลองจัดตารางใหม่ จนกว่าจะได้ตารางครบทุกงาน การคำนวณความเร็วเครื่องจักรใช้การรวมฟังก์ชันค่าใช้จ่ายจากเครื่องจักรทุกๆ เครื่องเข้ากับค่าใช้จ่ายจากค่าเวลาปิดงาน เมื่อแปลงค่าความเร็วเครื่องจักรแต่ละเครื่องไปเป็นตัวแปรความเร็วอ้างอิง แล้วจึงหาค่าต่ำสุดของค่าใข้จ่ายรวมทั้งหมด ด้วยการหาอนุพันธ์ของฟังก์ชันค่าใช้จ่าย จากผลการทดสอบพบว่า อัลกอริทึมจากงานวิจัยนี้ให้ค่าใช้จ่ายเพิ่มขึ้นเล็กน้อย ในกรณีการทดสอบเวลาพร้อมเริ่มงานร่วมกัน และค่าใช้จ่ายเป็นฟังก์ชันเชิงเส้น แต่ในกรณีทดสอบอื่นๆ อีก 3 กรณี อัลกอริทึมจากงานวิจัยนี้ให้ค่าใช้จ่ายที่ลดลง