COMBINATION OF ACO AND PSO TO MINIMIZE MAKESPAN IN ORDERED FLOWSHOP SCHEDULING PROBLEMS
Keywords:
Ordered Flowshop Scheduling, Makepan Minimalization, ACO-PSO
Abstract
The problem of scheduling flowshop production is one of the most versatile problems and is often encountered in many industries. Effective scheduling is important because it has a significant impact on reducing costs and increasing productivity. However, solving the ordered flowshop scheduling problem with the aim of minimizing makespan requires a difficult computation known as NP-hard. This research will contribute to the application of combination ACO and PSO to minimize makespan in the ordered flowshop scheduling problem. The performance of the proposed scheduling algorithm is evaluated by testing the data set of 600 ordered flowshop scheduling problems with various combinations of job and machine size combinations. The test results show that the ACO-PSO algorithm is able to provide a better scheduling solution for the scheduling group with small dimensions, namely 76 instances from a total of 600 inctances and is not good at obtaining makespan in the scheduling group with large dimensions. The ACO-PSO algorithm uses execution time which increases as the dimension size (multiple jobs and many machines) increases in a scheduled instance
Downloads
Download data is not yet available.
References
[1] Allahverdi, A., Aydilek, H. & Aydilek, A., (2018). No-Wait Flowshop Scheduling Problem With Two Criteria; Total Tardiness And Makespan. European Journal of Operational Research, Vol. 269(2), pp. 590–601.
[2] Arora, D. & Agarwal, G., (2016). Meta-Heuristic Approaches For Flowshop Scheduling Problems: A Review. International Journal of Advanced Operations Management, Vol. 8(1), pp. 1–16.
[3] Assia, S., El-Abbassi, I., El-Barkany, A., Darcherif, M., & El-Biyaali, A., (2020). Green Scheduling of Jobs and Flexible Periods of Maintenance in a Two-Machine Flowshop to Minimize Makespan, a Measure of Service Level and Total Energy Consumption. Advances in Operations Research, pp. 1–9.
[4] Baker, K. R., & Trietsch, D. (2009). Three Heuristic Procedures for the Stochastic Flow Shop Problem. In Proceedings, Multidisciplinary International Conference on Scheduling. Theory and Applications (MISTA 2009), 10-12 August 2009, Dublin, Ireland.
[5] Choi, B. C., & Park, M. J. (2016). An Ordered Flow Shop With Two Agents. Asia-Pacific Journal of Operational Research, Vol. 33, No. 5 pp. 1650037 (24 pages).
[6] Davendra, D., Zelinka, I., Bialic-Davendra, M., Senkerik, R., & Jasek, R., (2013). Discrete Self-Organising Migrating Algorithm For Flow-Shop Scheduling With No-Wait Makespan. Mathematical and Computer Modelling, Vol. 57, pp. 100–110.
[7] Enxing, Z. & Ranran, L. (2017). Routing Technology in Wireless Sensor Network Based on Ant Colony Optimization Algorithm. Wireless Personal Communications, Vol. 95(3), pp. 1911–1925.
[8] Fernandez-Viagas, V., Ruiz, R. & Framinan, J. M., (2017). A new vision of approximate methods for the permutation flowshop to minimise makespan: State-of-the-art and computational evaluation. European Journal of Operational Research, Vol. 257(3), pp. 707–721.
[9] Fuchigami, H. Y., & Rangel, S. (2018). A Survey Of Case Studies In Production Scheduling: Analysis And Perspectives. Journal of Computational Science.
[10] Gao, Y., Wang, J., Wu, W., Sangaiah, A.K., & Lim, S., (2019). A Hybrid Method For Mobile Agent Moving Trajectory Scheduling Using ACO and PSO in WSNs. Sensors (Switzerland), Vol. 19(3), pp. 1-19.
[11] Gupta, J. N. D., Majumder, A. & Laha, D., (2020). Flowshop Scheduling With Artificial Neural Networks. Journal of the Operational Research Society, Vol. 71(10), pp. 1619–1637.
[12] Habibi, R. (2017). Teknik Linierisasi Untuk Menyelesaikan Persoalan Rantai Suplai Lokasi-Inventori. Jurnal As-Salam, Vol. 1(1), pp. 44–55.
[13] Hornig, E. J. S. & Zimmermann, H. J. (2013). Scheduling Multi-Stage Batch Production Systems With Continuity Constraints: The Steelmaking And Continuous Casting System. publications.rwth-aachen.de. Available at:
[14] http://publications.rwth-aachen.de/record/229769.
[15] Javier, E., Hornig, S. and Dyckhoff, H. (2013). Scheduling Multi-Stage Batch Production Systems With Continuity Constraints. The Steelmaking and Continuous Casting System.
[16] Hossain, M. S. , Asadujjaman, M. & Bhattacharya, P., (2014). Minimization of Makespan in Flow Shop Scheduling Using Heuristics. ICMIEE.
[17] Ilić, A. (2015). On The Variable Common Due Date, Minimal Tardy Jobs Bicriteria Two-Machine Flow Shop Problem With Ordered Machines. Theoretical Computer Science, Vol, 582, pp. 70–73.
[18] Kao, Y., Chen, M. H. & Huang, Y. T. (2012). A Hybrid Algorithm Based On Aco And Pso For Capacitated Vehicle Routing Problems. Mathematical Problems in Engineering. hindawi.com. Available at: https://www.hindawi.com/journals/mpe/2012/726564/abs/.
[19] Khatami, M., Salehipour, A. & Hwang, F. J. (2019). Makespan Minimization For The M-Machine Ordered Flow Shop Scheduling Problem. Computers and Operations Research, Vol. 111, pp. 400–414.
[20] Kim, B. G., Choi, B. C. & Park, M. J. (2017). Two-Machine And Two-Agent Flow Shop With Special Processing Times Structures. Asia-Pacific Journal of Operational. ….
[21] Available at: https://www.worldscientific.com/doi/abs/10.1142/S0217595917500178.
[22] Kiran, S., Guru, J. & Sharma, M., (2018) . Credit Card Fraud Detection Using Naïve Bayes Model Based And KNN Classifier. International Journal of Advance Research, Ideas and Innovations in Technology, Vol. 4, pp. 44-47.
[23] Koulamas, C. & Panwalkar, S. S., (2015). Job Selection In Two-Stage Shops With Ordered Machines. Computers and Industrial Engineering, Vol. 88, pp. 350–353.
[24] Lee, K., Zheng, F. & Pinedo, M. L., (2019). Online Scheduling Of Ordered Flow Shops. European Journal of Operational Research, Vol. 272(1), pp. 50–60.
[25] Muharni, Y., Febianti, E. & Sofa, N. N., (2019). Minimasi Makespan Pada Penjadwalan Flow Shop Mesin Paralel Produk Steel Bridge B-60 Menggunakan Metode Longest Processing Time Dan Particle Swarm Optimization. Journal Industrial Servicess, Vol. 4(2).
[26] Panwalkar, S. S. & Koulamas, C., (2012). An O (N2) Algorithm For The Variable Common Due Date, Minimal Tardy Jobs Bicriteria Two-Machine Flow Shop Problem With Ordered Machines. European Journal of Operational Research, Vol. 221, Issue 1, pp. 7-13.
[27] Panwalkar, S. S. & Koulamas, C. (2017). On The Dominance Of Permutation Schedules For Some Ordered And Proportionate Flow Shop Problems. Computers and Industrial Engineering, Vol. 107, pp. 105–108.
[28] Panwalkar, S. S., Smith, M. L. & Koulamas, C., (2013). Review Of The Ordered And Proportionate Flow Shop Scheduling Research. Naval Research Logistics (NRL).
[29] Panwalkar, S.S. & Smith, Milton & Koulamas, Christos. (2013). Review of the Ordered and Proportionate Flow Shop Scheduling Research. Naval Research Logistics (NRL), Vol. 60(1).
[30] Pinedo M.L., (2016). Flow Shops, Job Shops and Open Shops (Stochastic). In: Scheduling. Springer, Cham. https://doi.org/10.1007/978-3-319-26580-3_13
[31] Rahman, H. F., Janardhanan, M. N. & Nielsen, I. E., (2019). Real-Time Order Acceptance and Scheduling Problems in a Flow Shop Environment Using Hybrid GA-PSO Algorithm. IEEE Access. Available at: https://ieeexplore.ieee.org/abstract/document/8798615/.
[32] Riahi, V. & Kazemi, M., (2018). A New Hybrid Ant Colony Algorithm For Scheduling Of No-Wait Flowshop. Operational Research, Vol. 18(1), pp. 55–74.
[33] Sun, Y., Dong, W. & Chen, Y., (2017). An Improved Routing Algorithm Based On Ant Colony Optimization In Wireless Sensor Networks. IEEE communications Letters.
[34] Tuegeh, M., Soeprijanto & Purnomo, M. H., (2009). Modified Improved Particle Swarm Optimization For Optimal. Seminar Nasional Aplikasi Teknologi Informassi 2009 (SNATI 2009), pp. 85–90.
[35] Widyawati, W. (2018). Penerapan Algoritma Ant Colony Optimization (ACO) Pada Job Shop SCHEDULING PROBLEM (JSSP) di PT. Siemens Indonesia (Cilegon Factory). Jurnal Sistem Informasi Dan Informatika (SIMIKA), Vol. 1(01), pp. 35-51.
[36] Xiao, Y., Wang, Y. & Sun, Y. (2018). Reactive Power Optimal Control Of A Wind Farm For Minimizing Collector System Losses. Energies.
[2] Arora, D. & Agarwal, G., (2016). Meta-Heuristic Approaches For Flowshop Scheduling Problems: A Review. International Journal of Advanced Operations Management, Vol. 8(1), pp. 1–16.
[3] Assia, S., El-Abbassi, I., El-Barkany, A., Darcherif, M., & El-Biyaali, A., (2020). Green Scheduling of Jobs and Flexible Periods of Maintenance in a Two-Machine Flowshop to Minimize Makespan, a Measure of Service Level and Total Energy Consumption. Advances in Operations Research, pp. 1–9.
[4] Baker, K. R., & Trietsch, D. (2009). Three Heuristic Procedures for the Stochastic Flow Shop Problem. In Proceedings, Multidisciplinary International Conference on Scheduling. Theory and Applications (MISTA 2009), 10-12 August 2009, Dublin, Ireland.
[5] Choi, B. C., & Park, M. J. (2016). An Ordered Flow Shop With Two Agents. Asia-Pacific Journal of Operational Research, Vol. 33, No. 5 pp. 1650037 (24 pages).
[6] Davendra, D., Zelinka, I., Bialic-Davendra, M., Senkerik, R., & Jasek, R., (2013). Discrete Self-Organising Migrating Algorithm For Flow-Shop Scheduling With No-Wait Makespan. Mathematical and Computer Modelling, Vol. 57, pp. 100–110.
[7] Enxing, Z. & Ranran, L. (2017). Routing Technology in Wireless Sensor Network Based on Ant Colony Optimization Algorithm. Wireless Personal Communications, Vol. 95(3), pp. 1911–1925.
[8] Fernandez-Viagas, V., Ruiz, R. & Framinan, J. M., (2017). A new vision of approximate methods for the permutation flowshop to minimise makespan: State-of-the-art and computational evaluation. European Journal of Operational Research, Vol. 257(3), pp. 707–721.
[9] Fuchigami, H. Y., & Rangel, S. (2018). A Survey Of Case Studies In Production Scheduling: Analysis And Perspectives. Journal of Computational Science.
[10] Gao, Y., Wang, J., Wu, W., Sangaiah, A.K., & Lim, S., (2019). A Hybrid Method For Mobile Agent Moving Trajectory Scheduling Using ACO and PSO in WSNs. Sensors (Switzerland), Vol. 19(3), pp. 1-19.
[11] Gupta, J. N. D., Majumder, A. & Laha, D., (2020). Flowshop Scheduling With Artificial Neural Networks. Journal of the Operational Research Society, Vol. 71(10), pp. 1619–1637.
[12] Habibi, R. (2017). Teknik Linierisasi Untuk Menyelesaikan Persoalan Rantai Suplai Lokasi-Inventori. Jurnal As-Salam, Vol. 1(1), pp. 44–55.
[13] Hornig, E. J. S. & Zimmermann, H. J. (2013). Scheduling Multi-Stage Batch Production Systems With Continuity Constraints: The Steelmaking And Continuous Casting System. publications.rwth-aachen.de. Available at:
[14] http://publications.rwth-aachen.de/record/229769.
[15] Javier, E., Hornig, S. and Dyckhoff, H. (2013). Scheduling Multi-Stage Batch Production Systems With Continuity Constraints. The Steelmaking and Continuous Casting System.
[16] Hossain, M. S. , Asadujjaman, M. & Bhattacharya, P., (2014). Minimization of Makespan in Flow Shop Scheduling Using Heuristics. ICMIEE.
[17] Ilić, A. (2015). On The Variable Common Due Date, Minimal Tardy Jobs Bicriteria Two-Machine Flow Shop Problem With Ordered Machines. Theoretical Computer Science, Vol, 582, pp. 70–73.
[18] Kao, Y., Chen, M. H. & Huang, Y. T. (2012). A Hybrid Algorithm Based On Aco And Pso For Capacitated Vehicle Routing Problems. Mathematical Problems in Engineering. hindawi.com. Available at: https://www.hindawi.com/journals/mpe/2012/726564/abs/.
[19] Khatami, M., Salehipour, A. & Hwang, F. J. (2019). Makespan Minimization For The M-Machine Ordered Flow Shop Scheduling Problem. Computers and Operations Research, Vol. 111, pp. 400–414.
[20] Kim, B. G., Choi, B. C. & Park, M. J. (2017). Two-Machine And Two-Agent Flow Shop With Special Processing Times Structures. Asia-Pacific Journal of Operational. ….
[21] Available at: https://www.worldscientific.com/doi/abs/10.1142/S0217595917500178.
[22] Kiran, S., Guru, J. & Sharma, M., (2018) . Credit Card Fraud Detection Using Naïve Bayes Model Based And KNN Classifier. International Journal of Advance Research, Ideas and Innovations in Technology, Vol. 4, pp. 44-47.
[23] Koulamas, C. & Panwalkar, S. S., (2015). Job Selection In Two-Stage Shops With Ordered Machines. Computers and Industrial Engineering, Vol. 88, pp. 350–353.
[24] Lee, K., Zheng, F. & Pinedo, M. L., (2019). Online Scheduling Of Ordered Flow Shops. European Journal of Operational Research, Vol. 272(1), pp. 50–60.
[25] Muharni, Y., Febianti, E. & Sofa, N. N., (2019). Minimasi Makespan Pada Penjadwalan Flow Shop Mesin Paralel Produk Steel Bridge B-60 Menggunakan Metode Longest Processing Time Dan Particle Swarm Optimization. Journal Industrial Servicess, Vol. 4(2).
[26] Panwalkar, S. S. & Koulamas, C., (2012). An O (N2) Algorithm For The Variable Common Due Date, Minimal Tardy Jobs Bicriteria Two-Machine Flow Shop Problem With Ordered Machines. European Journal of Operational Research, Vol. 221, Issue 1, pp. 7-13.
[27] Panwalkar, S. S. & Koulamas, C. (2017). On The Dominance Of Permutation Schedules For Some Ordered And Proportionate Flow Shop Problems. Computers and Industrial Engineering, Vol. 107, pp. 105–108.
[28] Panwalkar, S. S., Smith, M. L. & Koulamas, C., (2013). Review Of The Ordered And Proportionate Flow Shop Scheduling Research. Naval Research Logistics (NRL).
[29] Panwalkar, S.S. & Smith, Milton & Koulamas, Christos. (2013). Review of the Ordered and Proportionate Flow Shop Scheduling Research. Naval Research Logistics (NRL), Vol. 60(1).
[30] Pinedo M.L., (2016). Flow Shops, Job Shops and Open Shops (Stochastic). In: Scheduling. Springer, Cham. https://doi.org/10.1007/978-3-319-26580-3_13
[31] Rahman, H. F., Janardhanan, M. N. & Nielsen, I. E., (2019). Real-Time Order Acceptance and Scheduling Problems in a Flow Shop Environment Using Hybrid GA-PSO Algorithm. IEEE Access. Available at: https://ieeexplore.ieee.org/abstract/document/8798615/.
[32] Riahi, V. & Kazemi, M., (2018). A New Hybrid Ant Colony Algorithm For Scheduling Of No-Wait Flowshop. Operational Research, Vol. 18(1), pp. 55–74.
[33] Sun, Y., Dong, W. & Chen, Y., (2017). An Improved Routing Algorithm Based On Ant Colony Optimization In Wireless Sensor Networks. IEEE communications Letters.
[34] Tuegeh, M., Soeprijanto & Purnomo, M. H., (2009). Modified Improved Particle Swarm Optimization For Optimal. Seminar Nasional Aplikasi Teknologi Informassi 2009 (SNATI 2009), pp. 85–90.
[35] Widyawati, W. (2018). Penerapan Algoritma Ant Colony Optimization (ACO) Pada Job Shop SCHEDULING PROBLEM (JSSP) di PT. Siemens Indonesia (Cilegon Factory). Jurnal Sistem Informasi Dan Informatika (SIMIKA), Vol. 1(01), pp. 35-51.
[36] Xiao, Y., Wang, Y. & Sun, Y. (2018). Reactive Power Optimal Control Of A Wind Farm For Minimizing Collector System Losses. Energies.
Published
2021-06-10
How to Cite
Wandi Nduru, S., Purba, R., & Andri. (2021). COMBINATION OF ACO AND PSO TO MINIMIZE MAKESPAN IN ORDERED FLOWSHOP SCHEDULING PROBLEMS. INFOKUM, 9(2, June), 150-158. Retrieved from http://seaninstitute.org/infor/index.php/infokum/article/view/106
Section
Articles
