Using Local Search Methods for Solving Two Multi-Criteria Machine Scheduling Problems

Safanah Faisal  Yousif; Faez Hassan Ali; Karrar Fatah  Alshaikhli

doi:10.23851/mjs.v34i4.1430

Authors

Safanah Faisal Yousif Department of Mathematics, College of Science, Mustansiriyah University, 10052 Baghdad, IRAQ. https://orcid.org/0009-0009-7319-2633
Faez Hassan Ali Department of Mathematics, College of Science, Mustansiriyah University, 10052 Baghdad, IRAQ. https://orcid.org/0000-0003-2371-069X
Karrar Fatah Alshaikhli Department of Engineering and Mathematics, St. Philip's College, San Antonio, Texas, USA. https://orcid.org/0009-0004-2623-7097

DOI:

https://doi.org/10.23851/mjs.v34i4.1430

Keywords:

Local search Methods, Multi-Criteria Scheduling Problems, Bees Algorithm, Simulated Annealing, Branch and Bound Method

Abstract

In this paper, we have improved solutions for two of the Multi-Criteria Machine Scheduling Problems (MCMSP). These problems are to maximize early jobs time and range of lateness jobs times (1//(E_max,R_L ), and the second problem is maximum tardy jobs time and range of lateness jobs times (1//(T_max,R_L ) in a single machine with Multi-Objective Machine Scheduling Problems (MOMSP) 1//(E_max+R_L ) and 1//(T_max+R_L ) which are derived from the main problems respectively. The Local Search Methods (LSMs), Bees Algorithm (BA), and a Simulated Annealing (SA) are applied to solve all suggested problems. Finally, the experimental results of the LSMs are compared with the results of the Branch and Bound (BAB) method for a reasonable time. These results are ensuring the efficiency of LSMs.

Received: 12/06/2023

Revised: 23/06/2023, 22/07/2023

Accepted: 31/07/2023

Downloads

Download data is not yet available.

References

H. J. Mutashar, Flow Shop Scheduling Problems Using Exact and Local Search Methods, Baghdad: M.Sc. Thesis, Dept. of Mathematics, College of Science, Mustansiriyah University, 2008.

S. J. Ibraheem, Single Machine Multicriteria Scheduling, Baghdad: M. Sc. Thesis, Mathematics department, College of Ibn AL-Haitham, University of Baghdad, 2014.

A. A. Mahmood, "Local Search Algorithms for Multiobjective Scheduling Problem," Journal of Al Rafidain University College, no. 36, 2015.

S. B. Abdulkareem, Algorithms for Solving Multi-Criteria Scheduling Problems, Baghdad: Mathematics department, College of Science, Mustansiriyah University, 2017.

D. A. Abbass, "Using Branch and Bound and Local Search Methods to Solve Muiti-Objective Machine Scheduling Problem," in First International Conference of Computer and Applied Sciences(CAS), IEEE Xplore, 2019.

CrossRef

A. M. Gh, Exact and Approximation Methods for Solving Combinatorial Optimization Problems, Baghdad, Iraq.: Ph. D. Thesis, Mathematics department, College of Science, Mustansiriyah University, 2022.

G. A. Manal and F. H. Ali, "Optimal and Near Optimal Solutions for Multi Objective Function on a Single Machine," in 1st International Conference on Computer Science and Software Engineering (CSASE2020), Sponsored by IEEE Iraq Section, 16-17 Apr., Duhok, Kurdistan Region - Iraq, 2020.

S. F. Yousif and F. H. Ali, "Solving Maximum Early Jobs Time and Range of Lateness Jobs Times Problem Using Exact and Heuristic Methods," Iraqi Journal of Science, (accepted 2023), vol. 65, no. 2, 2024.

M. H. Ibrahim, Exact and Approximation Methods for Solving Machine Scheduling Problems with and without Setup Time, Baghdad: Ph. D. Thesis, Mathematics department, College of Science, Mustansiriyah University, 2022.

S. M. Jasim and F. H. Ali, "Exact and Local Search Methods for Solving Travelling Salesman Problem with Practical Application," Iraqi Journal of Science, [S.l], vol. 60, no. 5, pp. 1138-1153, 2019.

CrossRef

F. A. Ali, Improving Exact and Local Search Algorithms for Solving Some Combinatorial Optimization Problems, Baghdad: Ph. D. Thesis, Dept of Mathematics, College of Science, Al-Mustansiriyah University, 2015.