Single machine group scheduling with ordered criteria

The single machine group scheduling problem is considered. Jobs are classified into several groups on the basis of group technology, i.e. jobs of the same group have to be processed jointly. A machine set-up time independent of the group sequence is needed between each two consecutive groups. A schedule specifies the sequence of groups and the sequence of jobs in each group. The quality of a schedule is measured by the criteria F1,...,Fm ordered by their relative importance. The objective is to minimize the least important criterion Fm subject to the schedule being optimal with respect to the more important criterion FmÅ-1 which is minimized on the set of schedules minimizing criterion FmÅ-2 and so on. The most important criterion is F1, which is minimized on the set of all feasible schedules. An approach to solve this multicriterion problem in polynomial time is presented if functions F1,...,Fm have special properties. The total weighted completion time and the total weighted exponential time are the examples of functions F1,...,FmÅ-1 and the maximum cost is an example of function Fm for which the present approach can be applied.