Solving tri-criteria: total completion time, total late work, and maximum earliness by using exact, and heuristic methods on single machine scheduling problem

Authors

  • Nagham Muosa Neamah University of Baghdad
  • Bayda A. Kalaf Mathematics Department, College of Education for Pure Science Ibn-Al-Haitham, University of Baghdad, Baghdad, Iraq https://orcid.org/0000-0003-1136-0055

DOI:

https://doi.org/10.52866/ijcsm.2024.05.03.002

Keywords:

machine scheduling problem(MSP), Multi-Criteria (MC), Multi-Objective Function(MOF), Exact Methods(EM), Heuristic Methods(HM).

Abstract

The presented study investigated the scheduling regarding  jobs on a single machine. Each  job will be processed with no interruptions and becomes available for the processing at time 0. The aim is finding a processing order with regard to jobs, minimizing total completion time , total late work , and maximal tardiness  which is an NP-hard problem. In the theoretical part of the present work, the mathematical formula for the examined problem will be presented, and a sub-problem of the original problem of minimizing the multi-objective functions  is introduced. Also, then the importance regarding the dominance rule (DR) that could be applied to the problem to improve good solutions will be shown. While in the practical part, two exact methods are important; a Branch and Bound algorithm (BAB) and a complete enumeration (CEM) method are applied to solve the three proposed MSP criteria by finding a set of efficient solutions. The experimental results showed that CEM can solve problems for up to  jobs. Two approaches of the BAB method were applied: the first approach was BAB without dominance rule (DR), and the BAB method used dominance rules to reduce the number of sequences that need to be considered. Also, this method can solve problems for up to , and the second approach BAB with dominance rule (DR), can solve problems for up to  jobs in a reasonable time to find efficient solutions to this problem. In addition, to find good approximate solutions, two heuristic methods for solving the problem are proposed, the first heuristic method can solve up to  jobs, while the second heuristic method can solve up to  jobs. Practical experiments prove the good performance regarding the two suggested approaches for the original problem. While for a sub-problem the experimental results showed that CEM can solve problems for up to  jobs, the BAB without dominance rule (DR) can solve problems for up to , and the second approach BAB with dominance rule (DR), can solve problems for up to  jobs in a reasonable time to find efficient solutions to this problem. Finally, the heuristic method can solve up to jobs. Arithmetic results are calculated by coding (programming) algorithms using (MATLAB 2019a)

 

Downloads

Download data is not yet available.

Downloads

Published

2024-06-10

How to Cite

[1]
N. Muosa Neamah and Bayda A. Kalaf, “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, vol. 5, no. 3, pp. 14–25, Jun. 2024.
CITATION
DOI: 10.52866/ijcsm.2024.05.03.002
Published: 2024-06-10

Issue

Section

Articles