Minimizing flow time on a single machine with job classes and setup times

The authors examine the static sequencing problem of ordering the processing of jobs on a single machine so as to minimize the average weighted flow time. It is assumed that all jobs have zero ready times, and that the jobs are grouped into classes with the property that setup tasks are only required when processing switches from jobs of one class to jobs of another class. The time required for each setup task is given by the sum of a setdown time from the previous class and a setup time for the new class. The authors show that an algorithm presented in the literature for solving a special case of this problem gives suboptimal solutions. A number of properties of the optimal solution are derived, and their use in algorithms is evaluated. Computational results are presented for both a branch-and-bound procedure and a simpler depth-first search.