PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Mathematical model bounds for maximizing the minimum completion time problem

Treść / Zawartość
Identyfikatory
Warianty tytułu
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.
Rocznik
Strony
43--50
Opis fizyczny
Bibliogr. 20 poz., tab.
Twórcy
  • 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
  • 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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-007a64a2-5ff6-4e67-9978-7160c8ba4518
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.