A branch and bound approach for earliness and tardiness penalty problem with distinct due dates

In this paper, a single machine, n-job scheduling problem, in which each job has a distinct due date-and equal earliness and tardiness coefficients, is studied. The objective is to determine an optimal schedule to minimize the sum of earliness-tardiness penalties. Based on a new theorem for the idle time insertion in the optimal schedule, the paper presents a deterministic algorithm to obtain the upper bound of an optimal schedule. By combining it with an existing lower bound estimation scheme, a fast branch and bound approach for optimal schedule is proposed. Finally, a numerical example is given to illustrate the effectiveness of the new method.