Bi-criteria sequencing of courses and formation of classes for a bottleneck classroom

• Class formation and sequencing with a bottleneck classroom as batch scheduling.
• Proof of strong NP-hardness of minimising the number of late course completions.
• Computational experiments with data based on a real professional training system.

In this paper, the problem of class formation and sequencing for multiple courses subject to a bottleneck classroom with an ordered bi-criteria objective is studied. The problem can be modelled as a single-machine batch scheduling problem with incompatible job families and parallel job processing in batches, where the batch size is family-dependent. For the minimisation of the number of tardy jobs, the strong NP-hardness is proven. For the performance measure of the maximum cost, we consider single criterion and bi-criteria cases. We present an O(n2logn)O(n2logn) algorithm, n is the number of jobs, for both cases. An Integer Programming model as well as Simulated Annealing and Genetic Algorithm matheuristics to solve a fairly general case of the bi-criteria problem is presented and computationally tested.