In considering the problem of sequentially ordering N jobs, it is known that 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-and-bound method applied directly to Lawler's decomposition theorem and gives an optimal solution. In the algorithm, special care is given to the calculation procedure and the setup of the upper bound values to shorten the calculation time.
