We consider the scheduling of N jobs divided into G families for processing on a single machine. No set-up is necessary between jobs belonging to the same family. A set-up must be scheduled when switching from the processing of family i jobs to those of another family j, i ≠ j, the duration of this set-up being the sequence-independent set-up time sj for family j. We propose lower bounds for the problem of minimizing the weighted flowtime on a single machine with family set-up times and static job availability. These lower bounds are incorporated into a branch-and-bound algorithm which can efficiently solve instances with up to 70 jobs.
