Pub. online:23 Mar 2020Type:Research ArticleOpen Access
Journal:Informatica
Volume 31, Issue 1 (2020), pp. 1–20
Abstract
This paper investigates the problem of partitioning a complete weighted graph into complete subgraphs, each having the same number of vertices, with the objective of minimizing the sum of edge weights of the resulting subgraphs. This NP-complete problem arises in many applications such as assignment and scheduling-related group partitioning problems and micro-aggregation techniques. In this paper, we present a mathematical programming model and propose a complementary column generation approach to solve the resulting model. A dual based lower bounding feature is also introduced to curtail the notorious tailing-off effects often induced when using column generation methods. Computational results are presented for a wide range of test problems.
Pub. online:1 Jan 2017Type:Research ArticleOpen Access
Journal:Informatica
Volume 28, Issue 4 (2017), pp. 583–608
Abstract
This paper presents a column generation-based modelling and solution approach for a teaching assistant workload scheduling problem that arises at academic institutions. A typical weekly workload schedule involves teaching deficiency classes, instructing problem-solving tutorial sessions, and allocating help-hours for students. For this purpose, a mixed-integer programming model that selects valid combinations of weekly schedules from the set of all feasible schedules is formulated. Due to the overwhelming number of variables in this model, an effective column generation procedure is developed. To illustrate the proof-of-concept along with modelling and algorithmic constructs, a case study related to the Department of Mathematics at Kuwait University is addressed. Computational results based on real data indicate that the generated schedules using the proposed model and solution procedure yield improved weekly workloads for teaching assistants in terms of fairness, and achieve enhanced satisfaction levels among assistants, as compared to schedules obtained using ad-hoc manual approaches.