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

Publication Type:
Journal Article
Computers and Operations Research, 2016, 65 pp. 53 - 63
Issue Date:
Full metadata record
© 2015 Elsevier Ltd. Abstract 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) 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.
Please use this identifier to cite or link to this item: