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 criteriaF₁, ...,F_m ordered by their relative importance. The objective is to minimize the least important criterionF_m subject to the schedule being optimal with respect to the more important criterionF_m–1 which is minimized on the set of schedules minimizing criterionF_m–2 and so on. The most important criterion isF₁, which is minimized on the set of all feasible schedules. An approach to solve this multicriterion problem in polynomial time is presented if functionsF₁, ...,F_m have special properties. The total weighted completion time and the total weighted exponential time are the examples of functionsF₁, ...,F_m–1 and the maximum cost is an example of functionF_m for which our approach can be applied.The research of the authors was partially supported by a KBN Grant No. 3 P 406 003 05, the Fundamental Research Fund of Belarus, Project N 60-242, and the Deutsche Forschungsgemeinschaft, Project Schema, respectively. The paper was completed while the first author was visiting the University of Melbourne.