Mathematical model bounds for maximizing the minimum completion time problem

• Autorzy: Jemmali Mahdi , Alourani Abdullah

Identyfikatory

DOI

10.17512/jamcm.2021.4.04

• Języki publikacji: EN

Abstrakty

EN

This paper focuses on the parallel machine scheduling problem related to maximizing the minimum completion time. This problem affects several industrial applications. The application of this problem in real life is very impressive. This paper is based on the development of new lower bounds for the exact solution of the studied problem. It is shown in the literature that the problem is strongly NP-hard. The first developed lower bound is obtained by utilizing the probabilistic method to generate several solutions for the lower bound. The second is based on the knapsack problem with the iterative method. These numerical methods give new, better lower bounds.

Słowa kluczowe

EN

numerical methods; optimization; mathematical model; lower bounds

PL

metody numeryczne; optymalizacja; model matematyczny; dolna granica

• Wydawca: Wydawnictwo Politechniki Częstochowskiej
• Czasopismo: Journal of Applied Mathematics and Computational Mechanics
• Rocznik: 2021
• Tom: Vol. 20, nr 4
• Strony: 43--50
• Opis fizyczny: Bibliogr. 20 poz., tab.

Twórcy

autor

Jemmali Mahdi

• Department of Computer Science and Information, College of Science at Zulfi, Majmaah University Majmaah, 11952, Saudi Arabia
• MARS Laboratory, University of Sousse, Sousse, Tunisia
• Department of Computer Science, Higher Institute of Computer Science and Mathematics of Monastir, University of Monastir, Monastir, 5000, Tunisia

autor

Alourani Abdullah

• Department of Computer Science, Higher Institute of Computer Science and Mathematics of Monastir, University of Monastir, Monastir, 5000, Tunisia

Bibliografia

• [1] Deuermeyer, B.L., Friesen, D.K., & Langston, M.A. (1982). Scheduling to maximize the minimum processor finish time in a multiprocessor system. SIAM Journal on Algebraic Discrete Methods, 3(2), 190-196. https://doi.org/10.1137/0603019.
• [2] Lawler, E.L., Lenstra, J.K., Kan, A.H.R., & Shmoys, D.B. (1993). Sequencing and scheduling: Algorithms and complexity. Handbooks in Operations Research and Management Science, 4, 445-522. https://doi.org/10.1016/S0927-0507(05)80189-6.
• [3] Tan, Z., & Wu, Y. (2007). Optimal semi-online algorithms for machine covering. Theoretical Computer Science, 372(1), 69-80. https://doi.org/10.1016/j.tcs.2006.11.015.
• [4] Jiang, Y., Tan, Z., & He, Y. (2005). Preemptive machine covering on parallel machines. Journal of Combinatorial Optimization, 10(4), 345-363. https://doi.org/10.1007/s10878-005-4923-5.
• [5] He, Y., & Jiang, Y. (2005). Optimal semi-online preemptive algorithms for machine covering on two uniform machines. Theoretical Computer Science, 339(2-3), 293-314. https://doi.org/10.1016/j.tcs.2005.02.008.
• [6] Skutella, M., & Verschae, J. (2010). A robust PTAS for machine covering and packing. In European Symposium on Algorithms (pp. 36-47). Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-642-15775-24.
• [7] Azar, Y., & Epstein, L. (1998). On-line machine covering. Journal of Scheduling, 1(2), 67-77.
• [8] Walter, R., Wirth, M., & Lawrinenko, A. (2017). Improved approaches to the exact solution of the machine covering problem. Journal of Scheduling, 20(2), 147-164. https://doi.org/10.1007/s10951-016-0477-x.
• [9] Haouari, M., & Jemmali, M. (2008). Maximizing the minimum completion time on paralel machines. 4OR, 6(4), 375-392. https://doi.org/10.1007/s10288-007-0053-5.
• [10] Yong, H. (2001). Semi-on-line scheduling problems for maximizing the minimum machine completion time. Acta Mathematicae Applicatae Sinica, 17(1), 107-113.
• [11] Gerke, S., Panagiotou, K., Schwartz, J., & Steger, A. (2015). Maximizing the minimum load for random processing times. ACM Transactions on Algorithms (TALG), 11(3), 1-19.
• [12] Alharbi, M., & Jemmali, M. (2020). Algorithms for investment project distribution on regions. Computational Intelligence and Neuroscience. 147-164. https://doi.org/10.1155/2020/3607547.
• [13] Jemmali, M. (2021). An optimal solution for the budgets assignment problem. RAIRO: Operational Research, 55, 873.
• [14] Jemmali, M. (2019). Approximate solutions for the projects revenues assignment problem. Communications in Mathematics and Applications, 10(3), 653-658.
• [15] Jemmali, M. (2019). Budgets balancing algorithms for the projects assignment. International Journal of Advanced Computer Science and Applications (IJACSA), 10(11), 574-578.
• [16] Jemmali, M., Melhim, L.K.B., Alharbi, S.O.B., & Bajahzar, A.S. (2019). Lower bounds for gas turbines aircraft engines. Communications in Mathematics and Applications, 10(3), 637-642.
• [17] Jemmali, M., Melhim, L.K.B., & Alharbi, M. (2019). Randomized-variants lower bounds for gas turbines aircraft engines. World Congress on Global Optimization (pp. 949-956). Cham: Springer.
• [18] Jemmali, M., & Alquhayz, H. (2020). Equity data distribution algorithms on identical routers. In International Conference on Innovative Computing and Communications (pp. 297-305). Singapore: Springer.
• [19] Jemmali, M., & Alquhayz, H. (2020). Time-slots transmission data algorithms into network. 2020 International Conference on Computing and Information Technology (ICCIT-1441) (pp. 1-4). IEEE.
• [20] Jemmali, M. (2021). Intelligent algorithms and complex system for a smart parking for vaccine delivery center of COVID-19. Complex & Intelligent Systems, 1-13.