A total tardiness problem with preprocessing included

A special case of the two-machine flow-shop total tardiness problem is defined by assuming that the first machine is dedicated to preprocessing and that the second machine performs the main operation, which is longer than preprocessing for each job. It is also assumed that customer orders (jobs) contain varying numbers of otherwise similar parts; therefore orders with longer main processing times have longer preprocessing times as well. The new problem (F2/ppc/T ) is solved by exploiting its structure and its relationship to the single-machine (1//T ) and the two-machine flow-shop (F2//T¯) total tardiness problems. It is shown that shortest-processing-time ordering minimizes the average job completion time in the F2/ppc/T setting. This result leads to the development of dominance conditions to determine a priori the order of some jobs in an optimal F2/ppc/T sequence. These dominance conditions are then embedded in a branch-and-bound algorithm, which is shown to be computationally efficient. A polynomial-time heuristic is also developed for F2/ppc/T . It is concluded that the additional structure of F2/ppc/T (compared to the general F2//T problem) results in highly efficient solution algorithms for it. © 1996 John Wiley & Sons, Inc.