A quick optimal algorithm for sequencing on one machine to minimize total tardiness

In considering the problem of sequentially ordering N jobs, it is known tha t large-scale problems cannot be solved readily in order to find optimality since there are N! possibilities to the schedules. In this paper, a quick optimal algorithm for sequencing jobs processed on one machine to minimize total tardiness is proposed. The optimal algorithm relies upon the branch-a nd-bound method applied directly to Lawler's decomposition theorem and give s an optimal solution. In the algorithm, special care is given to the calcu lation procedure and the setup of the upper bound values to shorten the cal culation time. (C) 1999 Elsevier Science B.V. All rights reserved.