Solving Maximum Early Jobs Time and Range of Lateness Jobs Times Problem Using Exact and Heuristic Methods

Safanah Faisal Yousif; Faez Hassan Ali

doi:10.24996/ijs.2024.65.2.28

Authors

Safanah Faisal Yousif Mathematics Department , College of Science, Al- Mustansiriyah University, Bagdad, Iraq https://orcid.org/0009-0009-7319-2633
Faez Hassan Ali Mathematics Department , College of Science, Al- Mustansiriyah University, Bagdad, Iraq

DOI:

https://doi.org/10.24996/ijs.2024.65.2.28

Keywords:

Bicriteria Machine Scheduling Problems, Maximum Early jobs Time, Range of Lateness Jobs Times, Branch and Bound method

Abstract

In this paper, a solution to one of the Bicriteria Machine Scheduling Problems (BCMSP) is proposed. This problem focuses on the maximum early jobs time and range of lateness jobs time on a single machine (1//(E_max,R_L )). First, we derive a subproblem 1//(E_max+R_L ) from the main problem which is a special case for the suggested problem. Secondly, both exact complete enumeration and Branch and Bound (BAB) with two new lower bounds with some heuristic methods to solve the problems are proposed. The results prove the accuracy of BAB to solve the problem for n≤110 jobs in a reasonable time. In addition, the accuracy of the suggested heuristic methods is compared with the results of the exact methods.