A branch-and-bound algorithm for a single machine sequencing to minimize the sum of maximum earliness and tardiness with idle insert

This paper presents the optimal sequence of a set of jobs for a single machine with idle insert, in which the objective function is to minimize the sum of maximum earliness and tardiness (n/1/I/ETmax). Since this problem tries to minimize and diminish the values of earliness and tardiness, the results can be useful for different production systems such as just in time (JIT). Special case of determining the optimal sequence, considering common due date, is investigated and the structure of optimal solution is introduced, using some simple orders. In the general case, the neighborhood conditions are developed and the dominant set for any optimal solution is determined. The branch-and-bound (B&B) method is used to solve the problem, and the proper upper and lower bounds are also introduced. To show the effectiveness of the proposed algorithm, 780 problems of different sizes, ranging from 5 to 20 jobs, are generated at random and then solved.