Informatica

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.

This paper presents an optimization based mathematical modelling approach for a single source single destination crude oil facility location transshipment problem. We began by formulating a mixed-integer nonlinear programming model and use a rolling horizon heuristic to find an optimal location for a storage facility within a restricted continuous region. We next design a hybrid two-stage algorithm that combines judicious facility locations resulting from the proposed model into a previously developed column generation approach. The results indicate that improved overall operational costs can be achieved by strategically determining cost-effective locations of the transshipment facility.

This paper is concerned with an employee scheduling problem involving multiple shifts and work centers, where employees belong to a hierarchy of categories having downward substitutability. An employee at a higher category may perform the duties of an employee at a lower category, but not vice versa. However, a higher category employee receives a higher compensation than a lower category employee. For a given work center, the demand for each category during a given shift is fixed for the weekdays, and may differ from that on weekends. Two objectives need to be achieved: The first is to find a minimum-cost workforce mix of categories of employees that is needed to satisfy specified demand requirements, and the second is to assign the selected employees to shifts and work centers taking into consideration their preferences for shifts, work centers, and off-days. A mixed-integer programming model is initially developed for the problem, based on which a specialized scheduling heuristic is subsequently developed for the problem. Computational results reported reveal that the proposed heuristic determines solutions proven to lie within 92–99% of optimality for a number of realistic test problems.