วิธีวิวัฒนาการโดยใช้ผลต่างสำหรับการแก้ไขปัญหาการมอบหมายงานแบบหลายลำดับขั้น: กรณีศึกษาการขนส่งไก่

บทคัดย่อ

ปัญหาการมอบหมายงานคือปัญหาในการมอบหมายให้พนักงานคนหนึ่งไปทำงานงานหนึ่ง การมอบหมายงานในแต่ละครั้งจะเกิดต้นทุนในการมอบหมายงานที่แตกต่างกัน เป้าหมายในการแก้ไขปัญหาการ มอบหมายงานคือจะมอบหมายงานอย่างไรถึงจะทำให้ต้นทุนในการมอบหมายงานต่ำสุด ปัญหาการมอบหมายงานแบบหลายลำดับขั้นจะมีความซับซ้อนมากกว่าปัญหาการมอบหมายงานแบบดั้งเดิม ลำดับที่หนึ่งคือการมอบหมาย ฟาร์มไก่ให้กับฟาร์มไข่พร้อมกับปริมาณที่ทำการขนส่ง ลำดับที่สองมอบหมายประเภทของรถบรรทุกที่เหมาะสม สำหรับการขนส่งดังกล่าว การมอบหมายงานทั้งสองลำดับขั้นจะเกิดขึ้นพร้อมกันดังนั้นต้นทุนในการมอบหมายงาน จะขึ้นกับการตัดสินใจในการมอบหมายนั้น วิธีการแม่นตรงเป็นวิธีการที่ดีที่สุดในการหาคำตอบสำหรับปัญหาการมอบหมายงาน ยกตัวอย่างเช่น Simplex method, the Hungarian method เป็นต้น เริ่มต้นทำการศึกษาจากการพัฒนาแบบจำลองทางคณิตศาสตร์และการพัฒนาโปรแกรม LINGO เพื่อหาคำตอบที่ดีที่สุด ถึงแม้ว่าวิธีการแม่นตรงจะได้คำตอบที่ดีที่สุด แต่อาจใช้เวลานานในการหาคำตอบ วิธีการฮิวริสติกส์เป็นวิธีการทางเลือกในการแก้ปัญหาโดยใช้เวลาในการหาคำตอบไม่นาน อย่างไรก็ตามคำตอบที่ได้จะใกล้เคียงกับคำตอบที่ดีที่สุด ในกรณีศึกษานี้ใช้วิธีวิวัฒนาการโดยใช้ ผลต่าง (DE) เริ่มจากการกำหนดตัวอย่างเริ่มต้น หลังจากนั้นก็จำทำซ้ำขั้นตอน Mutation, Recombination, และ Selection ไปเรื่อย ๆ จนกว่าจะถึงเงื่อนไขที่กำหนด ผู้วิจัยทำการศึกษาโดยการพัฒนาแบบจำลองทางคณิตศาสตร์ที่ประกอบไปด้วยฟังก์ชันหลักและข้อจำกัดทั้งหมด หลังจากนั้นทำการพัฒนาโปรแกรมลิงโก แล้วทำการทดสอบด้วยการสร้างกลุ่มตัวอย่างที่แตกต่างกันจากขนาดของกลุ่มตัวอย่าง ในแต่ละกลุ่มจะมีจำนวน 5 ตัวอย่าง เมื่อทำการทดสอบแบบจำลองเรียบร้อยแล้วก็จะทำการใช้ข้อมูลจากกรณีศึกษา ในขณะเดียวกันก็ทำการพัฒนาวิธีวิวัฒนาการโดยใช้ผลต่าง โดยใช้กลุ่มตัวอย่างที่สร้างขึ้นข้างต้น และข้อมูลจากกรณีศึกษาเป็นลำดับถัดไป วิธีการแม่นตรงสามารถหาคำตอบได้ในกรณีศึกษาที่มีขนาดเล็กและขนาดกลาง DE สามารถหาคำตอบ ได้ในเวลา 0.2 วินาที ในขณะที่โปรแกรมลิงโกสามารถหาคำตอบได้ในเวลา 5 วินาที หากดัชนีเท่ากับ 100 หมายความว่า DE ให้คำตอบเท่ากับวิธีการแม่นตรง สำหรับกรณีตัวอย่างขนาดเล็กมีดัชนีเท่ากับ 118.4 อาจเนื่องจากระยะทางระหว่างแต่ละฟาร์มมีค่าสูง ในกรณีตัวอย่างขนาดกลาง DE ใช้เวลา 0.6 วินาที ส่วนโปรแกรมลิงโกใช้เวลา 103.6 วินาทีในการหาคำตอบ โดยมีดัชนีเท่ากับ 106.9 ซึ่งถือว่าใกล้เคียงคำตอบที่ดีที่สุดมากกว่ากลุ่มตัวอย่างขนาดเล็ก สำหรับกลุ่มตัวอย่างขนาดใหญ่และกรณีศึกษาไม่สามารถหาคำตอบที่ดีที่สุดได้ในเวลาที่เหมาะสม แต่อย่างไรก็ตามสามารถหาคำตอบที่เป็นไปได้ภายในเวลา 72 ชั่วโมง ดังนั้นจำทำการกำหนดเวลาในการหาคำตอบสำหรับโปรแกรมลิงโก สำหรับปัญหาขนาดใหญ่และกรณีศึกษา มีผลการศึกษาดังนี้ กลุ่มตัวอย่างขนาดใหญ่มีดัชนี 107.1 และใช้เวลาในการหาคำตอบ 4.2 วินาที สำหรับกรณีศึกษามีดัชนีเท่ากับ 109.0 โดยใช้ เวลา 7.8 วินาที เพื่อเป็นการพัฒนาคำตอบสำหรับวิธี DE งานวิจัยในอนาคตควรมีการปรับปรุงวิธีวิวัฒนาการโดยใช้ ผลต่างเพื่อทำให้ได้คำตอบที่ดียิ่งขึ้น นอกจากนี้อาจพัฒนาวิธีฮิวริสติกส์วิธีอื่น ๆ เช่น Particle Swarm Optimization (PSO) หรือวิธีอื่น ๆ ที่จะมาใช้แทนวิธีการ DE