A branch-and-bound algorithm to minimise the sum of maximum earliness and tardiness in the single machine (Q604766)

Summary: We consider the problem of scheduling \(n\) jobs on a single machine to minimise the sum of maximum earliness and tardiness. Since this problem is trying to minimise the earliness and tardiness values, the model is consistent with the just-in-time production system. Most of publications on this subject have studied ``min-sum'' objective functions, but in many settings balancing the costs of the jobs by minimising the cost of the worst scheduled job as ``min-max'' criteria is more important. Using efficient lower and upper bounds and new dominance rules, a branch-and-bound scheme is proposed. The proposed algorithm is then tested on a set of randomly generated problems of different sizes, varying from 5 to 1,000 jobs. Using these approaches, we are able to solve all problems in a reasonable time. Computational results demonstrate the efficiency of our branch-and-bound algorithm over the existing methods reported in the literature.