Abstract

Abstract
The conventional assignment-based first/best fit decreasing algorithms (FFD/BFD) are not polynomial in the one-dimensional cutting stock input size in its most common format. Therefore, even for small instances with large demands, it is difficult to compute FFD/BFD solutions. We present pattern-based methods that overcome the main problems of conventional heuristics in cutting stock problems by representing the solution in a much more compact format Using our pattern-based heuristics, FFD/BFD solutions for extremely large cutting stock instances, with billions of items, can be found in a very short amount of time.

Abstract
In this work we present a tabu search metaheuristic method for solving the permutation flow shop scheduling problem with sequence dependent setup times and the objective of minimising total weighted tardiness. The problem is well known for its practical applications and for the difficulty in obtaining good solutions. The tabu search method proposed is based on the insertion neighbourhood, and is characterised by the selection and evaluation of a small subset of this neighbourhood at each iteration; this has consequences both on diversification and intensification of the search. We also propose a speed-up technique based on book keeping information of the current solution, used for the evaluation of its neighbours. © 2014 Inderscience Enterprises Ltd.

Abstract
The traveling tournament problem is a sports scheduling problem that includes two major issues in creating timetables: home/away pattern feasibility and travel distance. In this problem, the schedule must be compact: every team plays in every time slot. However, there are some sports leagues that have both home/away pattern restrictions and distance limits, but do not require a compact schedule. In such schedules, one or more teams can have a bye in any time slot. This leads us to a variant of the problem: the relaxed traveling tournament problem. We present a complete search method to solve this problem based on branch-and-bound, metaheuristics and dynamic programming. © 2013, Springer-Verlag Berlin Heidelberg and EURO - The Association of European Operational Research Societies.

Abstract
This paper proposes a method for computing the expectation for the length of a maximum set of vertex-disjoint cycles in a digraph where vertices and/or arcs are subject to failure with a known probability. This method has an immediate practical application: it can be used for the solution of a kidney exchange program in the common situation where the underlying graph is unreliable. Results for realistic benchmark instances are reported and analyzed.

Abstract