Scheduling job families on a single machine

Abstract EN

The problem of scheduling n jobs on a single machine is considered, where the jobs are partitioned into several families and a set–up time is necessary between jobs of different families.

The objective is to find a lower bound for the problem of minimizing the sum of completion times and the maximum tardiness.

This paper uses a decomposition property to find a lower bound in order to incorporated in a branch and bound algorithm for constructing an optimal schedule.