SCHEDULING IDENTICAL JOBS WITH UNEQUAL READY TIMES ON UNIFORM PARALLEL MACHINES TO MINIMIZE THE MAXIMUM EARLINESS

Abstract

This paper consider of scheduling n identical jobs with unequal ready times on m parallel uniform machines to minimize the maximum earliness . To solve this lower bound is derived and it is incorporated in a branch-and-bound algorithm, and introduces six simple single-pass heuristic procedures that approximate the optimal solution. On sample problems, the branch-and-bound procedure in most instances was able to find an optimal solution within 1,000,000 iterations with n ≤ 60 and m ≤ 3. For larger values of m, the heuristics provided approximate solutions close to the optimal values.