A New Theorem for Lower Bounds in NP-Hard Multi-Objective Scheduling Problems

Section: Article
Issue
Vol. 22 No. 2 (2025): Volume 22 Issue 2
Published
Nov 30, 2025
Pages
96-101

Abstract

On a single machine, each of n jobs must be processed continuously. At time zero, every job is ready for processing. The tasks to process a sequence that minimizes the total sum of competition times plus the sum of tardiness . This bi-criteria problem is NP-hard because of the second one. We provide a theorem that demonstrates a relationship between the optimal solution, lower bounds, and the number of efficient solutions. The case is that the theorem works for NP-hard problems, whereas in previous works the focus was on P-hard problems. The theorem limits the lower bound's range, which is crucial for determining the best answer. Additionally, the theorem allows for discovering new lower bounds by opening algebraic procedures and concepts.

References

  1. M. G. A., and Faez H. Ali. (2020). Optimal and Near Optimal Solutions for Multi Objective Function on a Single Machine. in 1st International Conference on Computer Science and Software Engineering (CSASE2020), 16-17 Apr., Duhok, Kurdistan Region – Iraq.
  2. Liu, C., Li, J., Liu, J., and Jiao, L. A. (2020). Survey on Dynamic Multi-Objective Optimization, Chin. J. Comput., 43: 1246–1278.
  3. Luo, Z., Liu, X., Tan, S., Xu, H., and Liu, J. (2023). Multi-Objective Multi-Stage Optimize Scheduling Algorithm for Nonlinear Virtual Work-Flow Based on Pareto, Processes, 11(4): 1147. https://doi.org/ 10.3390/pr11041147
  4. Lauff, V., and F. Werner. (2004). Scheduling with Common Due Date, Earliness and Tardiness Penalties for Multi-Machine Problems: A Survey, Compu.Oper., 317-345.
  5. Qader, N. H., Mahmood, R. F., Mrakhan, M. B., Ramadan, A. (2023). Techniques to Restrict an Interval of a Lower Bound in Fuzzy Scheduling Problems, Iraqi Journal of Statistical Sciences, 20(1): 1-8. doi: 10.33899/iqjoss.2023.0178678
  6. Salh, H., Ramadan, A. (2022). Heuristic Approaches for Solving bi-objective Single Machine Scheduling Problems, Iraqi Journal of Statistical Sciences, 19(2): 36-41. doi:10.33899/iqjoss.2022.0176202
  7. Abdulkareem Zeidan, M. (2013). A Genetic Algorithm to Minimize the makespan for Three Machine Flow Shop Scheduling, Iraqi Journal of Statistical Sciences, 13(1): 11-26. DOI: 10.33899/iqjoss.2013.075435
  8. Manal, G., and Faez, A. H. (2022). Exact Method with Dominance Rules for Solving Scheduling on a Single Machine Problem with Multiobjective Function, Al-Mustansiriyah Journal of Science, 3 (2): 56–63
  9. Du, J. Z., and Leung, J.Y.-T. (1990). Minimizing Total Tardiness on One Machine is NP-Hard, Mathematics of Operations Research, 15(3): 483–495.
  10. Abdullah, H. F. (2010). Multicriteria Scheduling Problems to Minimize Total Tardiness Subject to Maximum Earliness or Tardiness, Ibn Al-Haitham. J. for pure & Appl. Sci., 23(1): 311-320
  11. Abdul-Razaq, T.S. and Ali, Z.M (2015). Minimizing the Total Completion Time, the Total Tardiness and the Maximum Tardiness, Ibn Al-Haitham. J. for pure & Appl. Sci., 28: 155-170.
  12. Chachan, H. A., and Hameed, A. S. (2019). Exact Methods for Solving Multi-Objective Problem on Single Machine Scheduling, Iraqi Journal of Science, 60 (8): 1802-1813. https://doi.org/10.24996/ijs.2019.60.8.17
  13. Chachan, H. A., Ali, F. H., and Ibrahim, M. H. (2020). Branch and Bound and Heuristic Methods for Solving Multi-Objective Function for Machine Scheduling Problems. 6th International Engineering Conference “Sustainable Technology and Development" (IEC), Erbil, Iraq:109-114. doi:10.1109/IEC49899.2020.9122793.
  14. Ibrahim., M. H., Faez, A. H., and Chachan, H. A. (2022). Solving Multi-Objective Function Problem Using Branch and Bound and Local Search Methods, International Journal of Nonlinear Analysis and Applications, 13(1): 1649-1658. doi: 10.22075/ijnaa.2022.5780
  15. Zhao, Q., and Yuan, J. (2024). Single-Machine Primary–Secondary Scheduling with Total Tardiness being the Primary Criterion, J Sched, 27: 309–318
  16. Ramadhan, A.M., and Jabbar, A.K. (2006). Techniques of Finding Lower Bounds in Multi-Objective Functions, Al-Rafidain Journal of Computer Sciences and Mathematics, 3 (2): 23-29.
  17. Ramadan, A., M. (2011). Range of Lower Bounds, Applied Mathematics and Computation, 218:1008-1011, https://doi.org/10.1016/j.amc.2020.125904
  18. Amin, B.A., and Ramadan, A.M. (2021). Novel Heuristic Approach for Solving Multi-objective Scheduling Problems, Ibn AL-Haitham Journal for Pure and Applied Sciences, 34 (3):50–59. https://doi.org/10.30526/34.3.2677.
  19. Mahmood, R. F., Ramadan, A. M., Mrakhan, M. B., and Qader, N. H. (2022). On Pareto Set for A Bi-Criteria Single Machine Scheduling Problem, Tikrit Journal of Pure Science, 27 (6): 88-91
  20. Ramadan, A. M. (2021). On Pareto Set for a Bi-criterion Scheduling Problem Under Fuzziness, Iraqi Journal of Statistical Sciences, 18 (33): 6471, doi: 10.33899/iqjoss.2021.168375.
  21. Ramadan, A. M. (2023). Techniques to Restrict an Interval of a Lower Bound in Fuzzy Scheduling Problems, Iraqi Journal of Statistical Sciences, 20(1): 1-8, DOI: 10.33899/iqjoss.2023.0178678
  22. Hassan, D. A., Amiri, N. M., and Ramadan, A. M. (2022). A Heuristic Approach to Minimize Three Criteria Using Efficient Solutions, Indonesian Journal of Electrical Engineering and Computer Science, 26(1): 334-341
  23. Sharif, R. A., and Ramadan, A. M. (2023). On Solving Tri-Criteria of Scheduling and Fuzzy Scheduling Problems, Journal of Southwest Jiaotong University, 58 (6): 375-384

Authors

Hassan A. Mahmood

Department of Mathematics, College of Education, Garmian University, KRG, Iraq

Ayad M. Ramadan

Department of Mathematics, College of Science, Sulaimani University, KRG, Iraq

Identifiers

https://doi.org/10.33899/iqjoss.v22i2.54081
Download this PDF file
PDF

Statistics

How to Cite

Mahmood, H. A. ., & Ramadan, A. M. . (2025). A New Theorem for Lower Bounds in NP-Hard Multi-Objective Scheduling Problems. IRAQI JOURNAL OF STATISTICAL SCIENCES, 22(2), 96–101. https://doi.org/10.33899/iqjoss.v22i2.54081