Heuristic Approaches for Solving bi-objective Single Machine Scheduling Problems

Section: Research Paper
Issue
Vol. 19 No. 2 (2022): Volume 19 Issue 2
Published
Jun 25, 2025
Pages
36-41

Abstract

In this research paper, n jobs have to be scheduled on one-machine to minimize the sum of maximum earliness and maximum tardiness. We solved a series of bi-criteria scheduling problems that related to minimize the sum of the maximum earliness and tardiness. Three new algorithms were presented, two for hierarchical objective and one for the simultaneous objective. Using the results of these algorithms, we minimize the sum of maximum earliness and maximum tardiness. This objective considered as one of the NP-hard problem, and it is also irregular, so this objective missed some helpful properties of regularity. The proposed algorithms had simple structures, and simple to implement. Lastly, they tested for different n.

References

  1. .
  2. - Abdul-Razaq, T. S., and Mohammed, H. A. (2016). Exact and Approximation Approaches for Solving Multiple Objective Function. Al-Mustansiriyah Journal of Science, 27 (3), 89-97.
  3. - Hoogeveen J. A. and Van de Velde, S. (1990). Polynomial Time Algorithms for Single Machine Multicriteria Scheduling, CWI, BS-R9008. file:///C:/Users/shelan/Downloads/5747D.pdf
  4. - Jawad, A. A., Ali, F. H., and Hasanain, W. S. (2020). Using Heuristic and Branch and Bound Methods to Solve a Multi-Criteria Machine Scheduling Problem. Iraqi Journal of Science,61 (8), 2055-2069, doi: 10.24996/ijs.2020.61.8.21.
  5. - Jouni. L. (2000). Multi-objective Nonlinear Pareto-Optimization. Lappeenranta University of Technology, Laboratory of Information Processing
  6. - Lawler E.L. (1973). Optimal Sequencing 0f a Single Machine Subject to Precedence Constraints. Management Science,19 (5), 544-546.
  7. - Smith, W.E. (1956). Various Optimizers for Single Stage Production, Naval Research Logistics Quarterly, 3(1), 59-66.
  8. - T'kindt, V. and Billaut, J.-C. (2002). Multi-criteria Scheduling. Theory, Models and Algorithms Springer, Berlin.
  9. - Van Wassenhove. L. N. and Gelders, F. (1980). Solving a Bicriterion Scheduling Problem. European Journal of Operational Research. 4, 42-48.
  10. - Werner, F. , Larysa, B. and Sotskov, N. (2018). Special Issue on Algorithms for Scheduling Problems. Algorithms, 11 (6).
  11. - Younis kawi, H. and Abdul-Razaq, T. S. (2017). Single Machine Scheduling To Minimize a Function of Square Completion Time and Maximum Earliness Simultaneously.Journal of Al-Qadisiyah for Computer Science and Mathematics,2 (1), 79-95.
  12. - Ali, F. H., and Jawad, A. A. (2020). Minimizing The Total Completion Time and Total Earliness Time Functions for a Machine Scheduling Problem using Local Search Methods. Iraqi Journal of Science, Special Issue, 126-133, doi: 10.24996/ijs.2020.SI.1.17.
  13. - Amin-Nayeri. M.R. and Moslehi. G. (2000). Optimal Algorithm for Single Machine Sequencing to Minimize Early/ Tardy Cost. ESTEGHLAL Journal of Engineering,19, 3548. https://jcme.iut.ac.ir/article-1-180-en.html
  14. - Aneed, J. S. (2013). Minimizing Three Simultaneous Criteria in Machine Scheduling Problem. Thesis, University of Thi-Qar.
  15. - Baker, K. R. (2014). Minimizing Earliness and Tardiness Costs in Stochastic Scheduling. European Journal of Operational Research,236 (2), 445-452.
  16. - 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 doi: 10.24996/ijs.2019.60.8.17.
  17. - Cheachan, H. A. and Kadhim, M.T. (2021). Exact Method for Solving Single Machine Scheduling Problem under Fuzzy Due Date to Minimize Multi-Objective Functions. Ibn Al-Haitham International Conference for Pure and Applied Sciences (IHICPS), Journal of Physics: Conference Series 1879, 022126 IOP Publishing doi:10.1088/1742-6596/1879/2/022126.
  18. - Hoogeveen, J and Van de Velde, S. (1995). Minimizing Total Completion Time and Maximum Cost Simultaneously is Solvable in Polynomial Time. Operations Research Letters, 17 (5), 205-208, Available: 10.1016/0167-6377(95)00023-d.
  19. - Hoogeveen, J.A. (1992). Single-Machine Bicriteria Scheduling. Doctoral Thesis, CWI, Amsterdam.
  20. References

Authors

Ayad Ramadan

Department. of Mathematics ,College Of Science, University of Sulaimani,Sulaimani,Iraq.

ORCID
Hawzhin Ahmad Salh

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

ORCID

Identifiers

Download this PDF file
PDF

Statistics

How to Cite

Ramadan, A., هاوزین, Ahmad Salh, H., & ایاد. (2025). Heuristic Approaches for Solving bi-objective Single Machine Scheduling Problems. IRAQI JOURNAL OF STATISTICAL SCIENCES, 19(2), 36–41. Retrieved from https://rjps.uomosul.edu.iq/index.php/stats/article/view/20897