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

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.