Solving the Multi-Criteria, Total Completion Time, Total Earliness Time, and Maximum Tardiness Problem
Main Article Content
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.
Article Details
This work is licensed under a Creative Commons Attribution 4.0 International License.
licenseTerms
Publication Dates
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.