The heuristic and metahuristic methods to minimize the total completion and total tardiness jobs times problem

Document Type : Research Paper


1 Department of Mathematics, Faculty of Science, Mustansiriyah University, Baghdad, IRAQ

2 Mathematics Department, College of Science, University of Diyala, Iraq


In this paper, we found some methods for solving one of the bicriteria machine scheduling problems (BMSP). Our discussed problem is represented by the total completion and the total tardiness jobs times $(1//(\sum C_j,\sum T_j))$ simultaneously. In order to solve the suggested BMSP, some new heuristic and metaheuristic methods are proposed which are produced good results. The results of the new suggested methods are compared with the exact method; like the complete enumeration method (CEM) and Branch and Bound (BAB) method, then compared results of the heuristics with each other's to obtain to the most efficient method.


[1] T.S. Abdul-Razaq and F.H. Ali, Algorithm for scheduling a single machine to minimize total completion time and
total tardiness, Basrah J. Sci. 34 (2016), no. 2, 113–132.[2] M.G. Ahmed and F.H. Ali, Efficient algorithms to solve tricriteria machine scheduling problem, Al-Rafidain Univ.
College Sci. 46 (2020).
[3] F.H. Ali, Improving exact and local search algorithms for solving some combinatorial optimization problems, Ph.
D. Thesis, Mustansiriyah University, College of Science, Dept. of Mathematics, 2015.
[4] S.A. Ali, A comparison of local search algorithm for multicriteria scheduling problems, M.Sc. Thesis, University
of Al-Mustansiriyah, College of Science, Dept. of Mathematics, 2016.
[5] F.H. Ali and S.B. Abdul-Kareem, Scheduling a single machine to minimize max tardiness, max late work and
total late work, Mathematics and Statistics Journal, 3 (2017), no. 1, 1–17.
[6] F.H. Ali and M.G. Ahmed, Local search methods for solving total completion times, range of lateness and maximum
tardiness problem, 6th Int. Engin. Conf. ”Sustainable Technology and Development” (IEC), IEEE, 2020, pp. 103–
[7] F.H. Ali and M.G. Ahmed, Optimal and near optimal solutions for multi objective function on a single machine,
Int. Conf. Comput. Sci. Software Engin. (CSASE), IEEE, 2020, pp. 152–156.
[8] J. Blazewics, K.H. Ecker, E. Pesch, G. Schmidt and J. Weglarz, Scheduling computer and manufacture processes,
Springer Science and Business Media, 2001.
[9] H.A. Chachan, F.H. Ali and M.H. Ibrahim, Branch and bound and heuristic methods for solving multi-objective
function for machine scheduling problems, 6th Int. Engin. Conf. “Sustainable Technology and Development”(IEC),
IEEE, 202), pp. 109–114.
[10] H.A. Chachan and A.S. Hameed, Exact methods for solving multi-objective problem on single machine scheduling,
Iraqi J. Sci. 60 (2019), no. 8, 1802–1813.
[11] C. Gallo and V. Capozzi, A simulated annealing algorithm for scheduling problems, J. Appl. Math. Phys. 7 (2019),
no. 11, 2579–2594.
[12] J.A. Hoogeveen, Minimizing maximum earliness and maximum lateness on a single machine, Proc. the 1st Integer
Program. Combin.Optim. Conf. 1991, pp. 283–295.
[13] J.A. Hoogeveen, Single machine scheduling to minimize a function of two or three maximum cost criteria, J.
Algorithms 21 (1996), 415–433.
[14] S.M. Jasim and F.H. Ali, Exact and local search methods for solving travelling salesman problem with practical
application, Iraqi J. Sci. 60 (2019), no. 5, 1138–1153.
[15] B. Kolman, Introductory linear algebra with applications, Macmillan Publishing Company, 1988.
[16] C.R. Reeves, Modern heuristic techniques for combinatorial problems, John Wiley and Sons, New York, 1993.
Volume 13, Issue 2
July 2022
Pages 2025-2035
  • Receive Date: 06 January 2022
  • Revise Date: 31 March 2022
  • Accept Date: 24 April 2022