The problem of scheduling n jobs in an m-machine permutation flow-shop is considered. Each job requires processing on machines 1,...,m in that order. The processing order of jobs is to be the same for each machine. A due date for each job is specified that represents the time by which it should ideally be completed. The objective is to schedule the jobs so that the number completed after their due dates is minimized. A lower bound, which is obtained by solving a single machine subproblem, is derived. Also, two improvement procedures which consider all subproblems together are developed. A branch and bound algorithm that uses these lower bounds is described. Computational experience with the algorithm is reported.
