บรานซ์แอนด์บาวด์คัทแบบปรับปรุงสำหรับปัญหาการจัดตารางงานสำหรับงานรับทำตามสั่ง
Article Sidebar
เผยแพร่แล้ว:
เม.ย. 5, 2018
คำสำคัญ:
บรานซ์แอนด์บาวด์ โมดิฟายด์บรานซ์แอนด์บาวด์ งานรับทำตามสั่ง
Main Article Content
บทคัดย่อ
บทความนี้นำเสนอการปรับปรุงวิธี Branch and Bound (B&B) เนื่องจากวิธีนี้สามารถหาค่าคำตอบที่เป็น Global optimal ได้ดีแต่มีข้อเสียคือถ้าปัญหามีขนาดใหญ่ขึ้นจะใช้เวลาในการแก้ปัญหานานมาก โดยที่วิธีที่นำเสนอจะสามารถลดเวลาในการหาค่าคำตอบ แต่เวลาที่ลดลงในการหาค่าคำตอบนั้นจะลดโอกาสในการได้มาซึ่งคำตอบที่เป็น ค่าคำตอบที่ดีที่สุด แต่วิธี Modified Branch and Bound (MB&B) สามารถทำให้มีการลู่เข้าในการหาค่าคำตอบโดยมีการเปรียบเทียบกับ ปัญหามาตรฐาน ได้แก่ FT06, FT10, LA19, LA20 โดยพบว่าในการหาค่าด้วยวิธี MB&B จะใช้เวลาในการหาค่าคำตอบน้อยกว่าวิธี B&B แบบธรรมดา
Article Details
บท
บทความวิจัย
References
Conway, R.W., Maxwell, W.L., Miller, L.W. 1967. Theory of Scheduling, Addison-Wesley, Reading, MA.
Davis, L. 1985. "Job shop scheduling with genetic algorithms", Proceedings of the First International Conference on Genetic Algorithms, Lawrence-Erlbaum, Mahwah, NJ, 136-40.
Gonzalo, M. 2005. “An approach using Petri Nets and improved heuristic search for manufacturing system scheduling”. Journal of Manufacturing Systems, 24 (2), 79-92.
Graham, R. 1966. "Bounds for certain multiprocessing anomalies". Bell System Technical Journal, 45, 1563–1581.
Jose F. G., Jorge, J. d., & Mauricio, G.C. 2005. “A hybrid genetic algorithm for the job shop scheduling problem.” European Journal of Operational Research, 167, 77- 95.
Jose F. 2007. “An adaptive branch and bound approach for transforming job shops into flow shops.” Computers & Industrial Engineering, 52, 1-10.
Land, A.H.; Doig, A.G. 1960. “An Automatic Method of Solving Discrete Programming Problems.” Econometrica, 28 (3), 497-520.
Lloyd, S., Yu, H., & Konstas, N. 1995.” FMS scheduling using Petri net modeling and a branch & bound search.” Proceedings of the IEEE International
Symposium on Assembly and Task Planning. Pittsburgh, USA, 211-216.
Satyaki, G. D. & Rakesh, N. 2005. “Scheduling injection molding operations with multiple resource constraints and sequence dependent setup times and costs.” Computers & Operations Research, 32, 2987-3005.
Sabuncuoglu, M. B. 1999. “Job shop scheduling with beam search. European Journal of Operational Research, 118, 390-412.
Sadrieh, M. G, Bahri, P. A., & Lee, P.L, 2007. “An integrated Petri net and GA based approach for scheduling of hybrid plants.“ Computers in Industry, 58, 519-530.
Van, d. A.1996. “ Petri net based scheduling." OR Spektrum, 18, 219-229.
Wongwiwat, A., & Bohez, E. L.J. 2013. “Production scheduling for injection molding manufacture using Petri Net model”. Assembly Automation, 33(1), 282-293.
Davis, L. 1985. "Job shop scheduling with genetic algorithms", Proceedings of the First International Conference on Genetic Algorithms, Lawrence-Erlbaum, Mahwah, NJ, 136-40.
Gonzalo, M. 2005. “An approach using Petri Nets and improved heuristic search for manufacturing system scheduling”. Journal of Manufacturing Systems, 24 (2), 79-92.
Graham, R. 1966. "Bounds for certain multiprocessing anomalies". Bell System Technical Journal, 45, 1563–1581.
Jose F. G., Jorge, J. d., & Mauricio, G.C. 2005. “A hybrid genetic algorithm for the job shop scheduling problem.” European Journal of Operational Research, 167, 77- 95.
Jose F. 2007. “An adaptive branch and bound approach for transforming job shops into flow shops.” Computers & Industrial Engineering, 52, 1-10.
Land, A.H.; Doig, A.G. 1960. “An Automatic Method of Solving Discrete Programming Problems.” Econometrica, 28 (3), 497-520.
Lloyd, S., Yu, H., & Konstas, N. 1995.” FMS scheduling using Petri net modeling and a branch & bound search.” Proceedings of the IEEE International
Symposium on Assembly and Task Planning. Pittsburgh, USA, 211-216.
Satyaki, G. D. & Rakesh, N. 2005. “Scheduling injection molding operations with multiple resource constraints and sequence dependent setup times and costs.” Computers & Operations Research, 32, 2987-3005.
Sabuncuoglu, M. B. 1999. “Job shop scheduling with beam search. European Journal of Operational Research, 118, 390-412.
Sadrieh, M. G, Bahri, P. A., & Lee, P.L, 2007. “An integrated Petri net and GA based approach for scheduling of hybrid plants.“ Computers in Industry, 58, 519-530.
Van, d. A.1996. “ Petri net based scheduling." OR Spektrum, 18, 219-229.
Wongwiwat, A., & Bohez, E. L.J. 2013. “Production scheduling for injection molding manufacture using Petri Net model”. Assembly Automation, 33(1), 282-293.