Reducing the Quadruple-Criteria with Release Time for Single-Machine Scheduling Problems

Authors

  • Lect. Dr.Nagham M. Neamah Mathematics Department, College of Science for Women, University of Baghdad, Baghdad, Iraq University of Baghdad - College of Science for Women
  • Lect. Dr.Tahani Jabbar Khraibet Thi-Qar Directorates of Education, Ministry of Education, Iraq
  • Lect. Dr.Shaima Abbas Jasim Mathematics Department, College of Science for Women, University of Baghdad, Baghdad, Iraq

DOI:

https://doi.org/10.31185/bsj.Vol23.Iss48.1790

Keywords:

Flow Time, Late Work. Single-Machine Scheduling, Release Time, Tardiness Time

Abstract

In this research, we have researched and discussed the issue of scheduling a single machine. Single-machine scheduling problems. We have proposed the first problem  of scheduling a set of tasks to be processed on a single machine to minimize the maximum lateness , maximum tardiness time , maximum flow time , and total flow time  simultaneously, denoted as ( ), noting that each task has a different release time . From the first problem ( ), we deduced the second problem , which is denoted as ( ). First, we found the mathematical formula for the two problems, and then we discussed the special cases for solving the two problems directly without resorting to CEM, BAB, or mathematical programming. In addition, it has been proven that the optimal solution to problem ( ) is one of the effective solutions to problem ( )

References

Ahmadi, R. H. (1990). Lower Bounds for Single-Machine Scheduling Problems. Naval Research Logistics, 37, 967–979.

Al-Zuwaini M.K. (2011). One Machine Scheduling Problem With Release dates and Two Criteria. Journal of Thi-Qar University2, 6(2), 1–14.

Allahverdi, A., Ng, C. T., Cheng, T. C. E., & Kovalyov, M. Y. (2008). A survey of scheduling problems with setup times or costs. European Journal of Operational Research, 187(3), 985–1032. https://doi.org/10.1016/j.ejor.2006.06.060

Allaoua, H., & Brahim, B. (2017). New Properties for Solving the Single-Machine Scheduling Problem with Early/Tardy Jobs. Journal of Intelligent Systems, 26(3), 531–543. https://doi.org/10.1515/jisys-2016-0063

Baker, T. (n.d.). Principles of Sequencing and Scheduling (U. of A. James J. Cochran & Analytics (eds.); Second Edi). Wiley Series in Operations Research and Management Science Operations. https://doi.org/10.1002/9781119262602

Chu, C., Sagep, P., & Metz, T. (2000). Efficient heuristics to minimize total flow time with release dates. Operations Research Letters, 12(November 1992), 321–330. https://dl.acm.org/doi/10.1016/0167-6377(92)90092-H

E . L . Lawler. (2013). Optimal Sequencing of a Single Machine Subject to Precedence Constraints. Management Science Theory Series ( Jan ., 1973 ), 19(5), 544–546.

Hoogeveen, H. (2005). Multicriteria scheduling. European Journal of Operation Research, 167(3), 592–623. https://doi.org/https://doi.org/10.1016/j.ejor.2004.07.011 Get rights and content

Johnson, S. M. (1954). Optimal two‐and three‐stage production schedules with setup times included. Naval Research Logistics Quarterly, I(1), 61-68.

L.Pinedo, M. (1994). Scheduling: Theory, algorithms, and systems. In Springer Science+Business Media (Fifth Edit). https://doi.org/10.1007/978-3-319-26580-3

Lakshminarayan, S., Lakshmanan, R., Papineau, R. L., & Rochette, R. (1978). Optimal Single-machine Scheduling with Earliness and Tardiness Penalties. Operations Research, 26(6), 1079–1082. http://www.jstor.org/stable/170267 .

Lenstra J.K., Rinnooy Kan A.H.G., B. B. (1977). complexity of machine-schedulingproblems. Annals of Discrete Math., 1, 343–36.

Nagham M. Neamah and Bayda A. Kalaf. (2023). Solving the multi-criteria: total completion time, total late work, and maximum earliness problem. Periodicals of Engineering and Natural Sciences, 11(3), 46–57. https://doi.org/10.21533/pen.v11i3.3559.g1288

Nagham M. Neamah and Bayda A. Kalaf. (2024a). A Hybrid Approach for Efficiently Solving Multi-Criteria Scheduling Problems on a Single Machine. Iraqi Journal of Science, 65(12), 7117–7129. https://doi.org/10.24996/ijs.2024.65.12.26

Nagham M. Neamah and Bayda A. Kalaf. (2024b). Minimizing Total Completion Time, Total Earliness Time, and Maximum Tardiness for a Single Machine scheduling problem. Ibn AL-Haitham Journal For Pure and Applied Sciences, 37(1), 386–402. https://doi.org/10.30526/37.1.3094

Nagham M. Neamah and Bayda A. Kalaf. (2024c). Solving the Multi-Criteria Problem: Total Completion Time, Total Late Work, Total Earliness Time, Maximum Earliness, and Maximum Tardiness. Iraqi Journal of Science, 65(5), 2724–2735. https://doi.org/10.21533/pen.v11i3.3559.g1288

Nagham M. Neamah and Bayda A. Kalaf. (2024d). Solving Tri-criteria: Total Completion Time, Total Earliness, and Maximum Tardiness Using Exact and Heuristic Methods on Single-Machine Scheduling Problems. Mathematical Modelling of Engineering Problems, 11(4), 987–995. https://doi.org/10.18280/mmep.110415

Nagham M. Neamah, & Bayda A. Kalaf. (2024). Solving tri-criteria: total completion time, total late work, and maximum earliness by using exact, and heuristic methods on single machine scheduling problem. Iraqi Journal for Computer Science and Mathematics, 5(3), 14–25. https://doi.org/https:// doi.org/10.52866/ijcsm.2024.05.03.002

Opérationnelle, R., & Opérationnelle, R. E. (1996). A new class of scheduling criteria and theid optimization. Recherche Opérationnelle/Opérations Research, 30(2), 171–189. https://www.numdam.org/item/?id=RO_1996__30_2_171_0

Phrueksanant, J. (2013). Machine scheduling using the Bees algorithm [Cardiff University - United Kingdom]. http://orca.cf.ac.uk/58594/

Pinedo, M. (1992). Scheduling : Theory, Algorithms and System Dvelopment. Operations Research Proceedings 1991, March, 35–42. https://doi.org/10.1007/978-3-642-46773-8_5

Smith, W. E. (1956). Various optimizers for single-stage production. Navel Research Logistics Quarterly, 3, 59–66. https://doi.org/10.1002/nav.3800030106

Stevenson. (2015). Operations Management (W. j . Stevenson (ed.); Thirteenth). McGraw-Hill Education. https://doi.org/LCC TS155 .S7824 2018 | DDC 658.5--dc23

Taylor, P., Mahnam, M., & Moslehi, G. (2009). A branch-and-bound algorithm for minimizing the sum of maximum earliness and tardiness with unequal release times. Taylor & Francis, December 2014, 37–41. https://doi.org/10.1080/03052150802657290

Vincent and Billaut. (2005). Multicriteria Scheduling Theory, Models and Algorithms. In P. J.-C. B. Associate Professor Vincent T’kindt (Ed.), Springer Berlin Heidelberg New York (Second Edi). Springer Berlin Heidelberg New York. https://doi.org/10.1007/b106275

Woeginger, G. J. (1999). Approximability and Nonapproximability Results for Minimizing Total Flow Time on a Single Machine. Eindhoven University of Technology, 28(4). https://doi.org/https://doi.org/10.1137/S0097539796305778

Downloads

Published

2026-09-22

Issue

Vol. 23 No. 48

Section

Articles

License

Copyright (c) 2026 م.د.نغم موسى نعمه جامعة بغداد / كلية العلوم للبنات / قسم الرياضيات، م.د.تهاني جبار خريبط وزارة التربية / مديرية تربية ذي قار، م.د.شيماء عباس جاسم جامعة بغداد / كلية العلوم للبنات / قسم الرياضيات

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.