Solving the Multi-Criteria, Total Completion Time, Total Earliness Time, and Maximum Tardiness Problem

Bayda Atiya kalaf; Nagham Muosa Neamah; Hamiden Abd El-Wahed  Khalifa

doi:10.30526/37.1.3094

Authors

Bayda Atiya kalaf Department of Mathematics, College of Education for Pure Sciences, Ibn Al – Haitham, University of Baghdad Iraq
Nagham Muosa Neamah Department of Mathematics, College of Education for Pure Science Ibn AL-Haitham, University of Baghdad, Baghdad, Iraq.
Hamiden Abd El-Wahed Khalifa Department of Mathematics, College of Science and Arts, Qassim University, Al-Badaya 51951,Saudi Arabia.

DOI:

https://doi.org/10.30526/37.1.3094

Keywords:

Single Machine Scheduling Problem, Total Completion Times, Total Earliness Time, Maximum Tardiness, Multi-Objective

Abstract

Machine scheduling problems (MSP) are considered as one of the most important classes of combinatorial optimization problems. In this paper, the problem of job scheduling on a single machine is studied to minimize the multiobjective and multiobjective objective function. This objective function is: total completion time, total lead time and maximum tardiness time, respectively, which are formulated as are formulated. In this study, a mathematical model is created to solve the research problem. This problem can be divided into several sub-problems and simple algorithms have been found to find the solutions to these sub-problems and compare them with efficient solutions. For this problem, some rules that provide efficient solutions have been proved and some special cases have been introduced and proved since the problem is an NP-hard problem to find some efficient solutions that are efficient for the discussed problem 1// and good or optimal solutions for the multi-objective functions 1// ,, and emphasize the importance of the dominance rule (DR), which can be applied to this problem to improve efficient solutions.

References

WASSENHOVE, L.N.V. Single Machine Scheduling to Minimize Total Late Work. Oper. Res. 1992, 40, 586–595. https://doi:10.1287/opre.40.3.586. DOI: https://doi.org/10.1287/opre.40.3.586

Tanaev, V.; Gordon, W.; Shafransky, Y. M. Scheduling theory. Single-stage systems. Springer Science and Business Media. (2012).‏

Hoogeveen, H. Multicriteria Scheduling. Eur. J. Oper. Res. 2005, 167, 592–623. https://doi:10.1016/j.ejor.2004.07.011. DOI: https://doi.org/10.1016/j.ejor.2004.07.011

Zaidan, A.A.; Atiya, B.; Abu Bakar, M.R.; Zaidan, B. B. A new hybrid algorithm of simulated annealing and simplex downhill for solving multiple-objective aggregate production planning on fuzzy environment. Neural Comput & Applic, 2019, 31, 1823–1834.

https://doi.org/10.1007/s00521-017-3159-5 DOI: https://doi.org/10.1007/s00521-017-3159-5

Chachan, H. A., ; Jaafar, H. A. Exact Solutions for Minimizing cost Function with Five Criteria and Release Dates on Single Machine. Ibn AL-Haitham Journal For Pure and Applied Sciences, 2020. 33(3), 140–157. https://doi.org/10.30526/33.3.2479 DOI: https://doi.org/10.30526/33.3.2479

Ali, Z.M.; Abdul Razaq, T.S. Minimizing The Total Completion Times, The Total Tardinessand The Maximum Tardiness. 2015, 28, 155–170.

Ahmed, M.G.; Ali, F.H. Exact Method with Dominance Rules for Solving Scheduling on a Single Machine Problem with Mult iobjective Function. Al-Mustansiriyah J. Sci. 2022, 33, 56–63. https://doi:10.23851/mjs.v33i2.1091.

Ali, F.H.; Ahmed, M.G. Local Search Methods for Solving Total Completion Times, Range of Lateness and Maximum Tardiness Problem. Proc. 6th Int. Eng. Conf. Sustainable Technol. Dev. IEC 2020, 103–108. https://doi:10.1109/IEC49899.2020.9122821.

Hassan, D.A.; Mehdavi-Amiri, N.; Ramadan, A.M. A Heuristic Approach to Minimize Three Criteria Using Efficient Solutions. Indones. J. Electr. Eng. Comput. Sci. 2022, 6, 334–341. https://doi:10.11591/ijeecs.v26.i1.pp334-341.

Abdullah, H. F. Multicriteria Scheduling Problems to Minimize Total Tardiness Subject to Maximum Earliness or Tardiness. Ibn AL-Haitham Journal For Pure and Applied Sciences, 2017, 23(1), 311–320. https://jih.uobaghdad.edu.iq/index.php/j/article/view/988

Smith, W.E. Various Optimizers for Single-Stage Production. Nav. Res. Logist. Q. 1956, 3, 59–66, https://doi:10.1002/nav.3800030106 DOI: https://doi.org/10.1002/nav.3800030106

Abdul-Razaq, T.S.; Akram, A.O. Local Search Algorithms for Multi-Criteria Single Machine Scheduling Problem. Ibn AL-Haitham J. Pure Appl. Sci. 2018, 436–451.https://doi:10.30526/2017.ihsciconf.1817. DOI: https://doi.org/10.30526/2017.IHSCICONF.1817

Hoogeveen, J.A. Minimizing Maximum Promptness and Maximum Lateness on a Single Machine. Math. Oper. Res. 1996, 21, 100–114, https://doi:10.1287/moor.21.1.100. DOI: https://doi.org/10.1287/moor.21.1.100

Jawad, A.A.; Ali, F.H.; Hasanain, W.S. Using Heuristic and Branch and Bound Methods to Solve a Multi-Criteria Machine Scheduling Problem. Iraqi J. Sci. 2020, 61, 2055–2069. https://doi:10.24996/ijs.2020.61.8.21

Abdul-Zahra, I.; Abbas, I. T.; Kalaf, B. A.; Bakar, R. A.; June, L. W., ; Monsi, M. B. . The Role of Dynamic Programming in the Distribution of Investment Allocations between Production Lines with an Application. International Journal of Pure and Applied Mathematics, 2016, 106(2), 365-380. DOI: https://doi.org/10.12732/ijpam.v106i2.2

Atiya, B.; Bakheet, A. J. K.; Abbas, I. T.; Bakar, M. R. A.; Soon, L. L., ; Monsi, M. B. Application of simulated annealing to solve multi-objectives for aggregate production planning. AIP Conference Proceedings (2016, June). 1739(1), 020086). AIP Publishing LLC. https://doi.org/10.1063/1.4952566 DOI: https://doi.org/10.1063/1.4952566

Kalaf, B. A., Mohammed, G. J.; Salman, M. D. A New Hybrid Meta-Heuristics Algorithms to Solve APP Problems. In Journal of Physics: Conference Series (2021, May). 1897(1), 012011). IOP Publishing.‏

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

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

Jawad, A.A.; Ali, F.H. ; Hasanain, W.S. .Using heuristic and branch and bound methods to solve a multi-criteria machine scheduling problem, Iraqi Journal of Science, 2020, 61(8), 2055–2069. https://doi.org/10.24996/ijs.2020.61.8.21

Mahnam, M.; Moslehi, G.; Fatemi Ghomi, S.M.T. Single machine scheduling with unequal release times and idle insert for minimizing the sum of maximum earliness and tardiness, Mathematical and Computer Modelling, 2013, 57(9–10), 2549–2563 https://doi.org/10.1016/j.mcm.2013.01.007. DOI: https://doi.org/10.1016/j.mcm.2013.01.007

Mosheiov, G.; Oron, D. ; Shabtay, D. Minimizing total late work on a single machine with generalized due-dates, European Journal of Operational Research, 2021, 293(3), 837–846. https://doi.org/10.1016/j.ejor.2020.12.061.

Neamah, N. M.; Kalaf, B. A. Solving the multi-criteria: Total completion time, total late work, and maximum earliness problem. Periodicals of Engineering and Natural Sciences, 2023. 11(3), 46-57.‏

Centinkaya, M.; Ozyurek, C., The Effect of Inquiry-Based Science Activities on Prospective Science Teachers’ Scientific Process Skills, International Online Journal of Education and Teaching, . 2019, 6(1), 56–70.

Chachan, H.A. Solving Machine Scheduling Problem Using Particle Swarm Optimization Method, The Iraqi Magazine For Administrative Sciences, 2012, 8(33), 197–213.

Abid, H. ; Mohammed, A. Scheduling job families with setups on a single machine, Journal of Kerbala University, 2012, 10(2), 99–113.

Adel D., Search method for solving multicriteria scheduling problem, 2022, 13(March 2021), 1709–1720.

Ahmadov, Y. ; Helo, P., A cloud based job sequencing with sequence-dependent setup for sheet metal manufacturing’, Annals of Operations Research, 2018, 270(1–2),5–24. https://doi.org/10.1007/s10479-016-2304-3. DOI: https://doi.org/10.1007/s10479-016-2304-3

Ahmed, M. ; Ali, F. Efficient Algorithms to Solve Tricriteria Machine Scheduling Problem. Journal of Al-Rafidain University College For Sciences, 2020, (1), 485-493.‏

Ahmed, M.G. and Ali, F.H. Exact Method with Dominance Rules for Solving Scheduling on a Single Machine Problem with Multi objective Function’, Al-Mustansiriyah Journal of Science, 2022, 33(2), 56–63. Available at: https://doi.org/10.23851/mjs.v33i2.1091.