XHSTT: an XML archive for high school timetabling problems in different countries

We present the progress on the benchmarking project for high school timetabling that was introduced at PATAT 2008. In particular, we announce the High School Timetabling Archive XHSTT-2011 with 21 instances from 8 countries and an evaluator capable of checking the syntax of instances and evaluating the solutions.     

An effective greedy heuristic for the Social Golfer Problem

The Social Golfer Problem (SGP) is a combinatorial optimization problem that exhibits a lot of symmetry and has recently attracted significant attention. In this paper, we present a new greedy heuristic for the SGP, based on the intuitive concept of freedom among players. We use this heuristic in a complete backtracking search, and match the best current results of constraint solvers for several SGP instances with a much simpler method. We then use the main idea of the heuristic to construct initial configurations for a metaheuristic approach, and show that this significantly improves results obtained by local search alone. In particular, our method is the first metaheuristic technique that can solve the original problem instance optimally. We show that our approach is also highly competitive with other metaheuristic and constraint-based methods on many other benchmark instances from the literature.     

The break scheduling problem: complexity results and practical algorithms

Break scheduling problems arise in working areas where breaks are indispensable, e.g., in air traffic control, supervision, or assembly lines. We regard such a problem from the area of supervision personnel. The objective is to find a break assignment for an existing shiftplan such that various constraints reflecting legal demands or ergonomic criteria are satisfied and such that staffing requirement violations are minimised. We prove the NP-completeness of this problem when all possible break patterns for each shift are given explicitly as part of the input. To solve our problem we propose two variations of a memetic algorithm. We define genetic operators, a local search based on three neighbourhoods, and a penalty system that helps to avoid local optima. Parameters influencing the algorithms are experimentally evaluated and assessed with statistical methods. We compare our algorithms, each with the best parameter setting according to the evaluation, with the state-of-the-art algorithm on a set of 30 real-life and randomly generated instances that are publicly available. One of our algorithms returns improved results on 28 out of the 30 benchmark instances. To the best of our knowledge, our improved results for the real-life instances constitute new upper bounds for this problem     

Modeling and solving staff scheduling with partial weighted maxSAT

Annals of Operations Research - Employee scheduling is a well known problem that appears in a wide range of different areas including health care, air lines, transportation services, and basically...     

Integer programming model extensions for a multi-stage nurse rostering problem

Annals of Operations Research - In the variant of the well studied nurse rostering problem proposed in the Second International Nurse Rostering Competition, multiple stages have to be solved...     

An improved SAT formulation for the social golfer problem

The Social Golfer Problem (SGP) is a sports scheduling problem that exhibits a lot of symmetry and has recently attracted significant attention. In this paper, we first revisit an existing SAT encoding for the SGP and correct some of its clauses. We then propose a change in the encoding that significantly reduces the number of variables for all instances. We achieve considerable performance improvements when solving many SGP instances with common SAT solvers using local search and complete backtracking. This makes SAT formulations a more promising approach for solving the SGP than previously.     

The minimum shift design problem

The min-Shift Design problem (MSD) is an important scheduling problem that needs to be solved in many industrial contexts. The issue is to find a minimum number of shifts and the number of employees to be assigned to these shifts in order to minimize the deviation from workforce requirements. Our research considers both theoretical and practical aspects of the min-Shift Design problem. This problem is closely related to the minimum edge-cost flow problem (MECF), a network flow variant that has many applications beyond shift scheduling. We show that MSD reduces to a special case of MECF and, exploiting this reduction, we prove a logarithmic hardness of approximation lower bound for MSD. On the basis of these results, we propose a hybrid heuristic for the problem, which relies on a greedy heuristic followed by a local search algorithm. The greedy part is based on the network flow analogy, and the local search algorithm makes use of multiple neighborhood relations. An experimental analysis on structured random instances shows that the hybrid heuristic clearly outperforms our previous commercial implementation. Furthermore, it highlights the respective merits of the composing heuristics for different performance parameters.     

Simultaneous Determination of Lipophilic Vitamin Esters Using Square-wave Voltammetry at the Glassy Carbon Electrode

Simple and rapid voltammetric method for simultaneous determination of all-trans-retinyl acetate (RAc) or all-trans-retinyl palmitate (RPa) and α-tocopheryl acetate (α-TOAc) has been proposed. The respective method was based on the anodic oxidation of the compounds of interest by square-wave voltammetry in acetone with 0.1 mol L⁻¹ LiClO₄ at the glassy carbon electrode. The procedure was also beneficial with respect to simple dissolution of sample directly in the supporting electrolyte. The all-trans-retinyl acetate could be quantified in two linear ranges (3.1–140 μmol L⁻¹ and 140–400 μmol L⁻¹) and α-tocopheryl acetate in linear range 5.3–400 μmol L⁻¹ with detection limits of 0.9 μmol L⁻¹ RAc (or 0.8 μmol L⁻¹ RPa) and of 1.6 μmol L⁻¹ α-TOAc. Selected commercial cosmetic products were analysed achieving satisfactory recoveries.