Scheduling the professional Ecuadorian football league by integer programming

A sports schedule sets the dates and venues of games among teams in a sports league. Constructing a sports schedule is a highly restrictive problem. The schedule must meet constraints due to regulations of a particular sports league federation and it must guarantee the participation of all teams on equal terms. Moreover, economic benefits of the teams and other agents involved in this activity are expected. Until 2011, the Ecuadorian football federation (FEF) had developed schedules for their professional football championship manually. In early 2011, the authors presented to the FEF authorities evidence that the use of mathematical programming to create feasible sports schedules could easily exceed the benefits obtained by the empirical method. Under this premise, this work presents an integer programming formulation, solved to optimality, for scheduling the professional football league in Ecuador, and also a heuristic approach based on three-phases for its solution. The schedules obtained met the expectations of the FEF and one of them was adopted as the official schedule for the 2012 edition of the Ecuadorian professional football championship.     

Planning production using mathematical programming: The case of a woodturning company

Herein we present a case of production planning in a woodturning company. The company wishes to plan the turning of various types of products of different radii in a set of parallel machines (lathes) and with the following principal conditions: for each type of product there is a minimum production lot size; some lathes cannot manufacture every type of product; the production capacity of a lathe depends on the lathe itself and the type of product to be manufactured; the products are classified into families according to radius; and there is an intra-family setup time (for manufacturing different products that have the same radius) and an inter-family setup time (for consecutively manufacturing products that have different radii), which is longer; part of the production can be subcontracted; each type of product can be manufactured on different lathes and/or subcontracted; and the operators can work overtime, during which additional time they can simultaneously operate multiple lathes. The goal is to meet the demand at minimum cost, which includes the cost of any overtime plus that of any subcontracting. The problem was modelled and solved by mixed-integer linear programming (MILP). The company considers the results to be satisfactory.     

Scheduling the Italian Football League: an ILP-based approach

Scheduling the Italian Major Football League (the so-called “Serie A”) consists in finding for that league a double round robin tournament schedule that takes into account both typical requirements such as conditions on home-away matches and specific requests of the Italian Football Association such as twin-schedules for teams belonging to the same home-town. In this paper, we present a solution procedure able to derive feasible schedules that are also balanced with respect to additional cable televisions requirements. This procedure adapts the recent approach by Nemhauser and Trick to schedule a College Basketball Conference that considers however only half of the teams involved here. The proposed procedure is divided into three phases: phase 1 generates a pattern set respecting the cable televisions requirements and several other constraints; phase 2 produces a feasible round robin schedule compatible with the above pattern set; finally, phase 3 generates the actual calendar assigning the teams to the patterns. The procedure allows to generate within short time several different reasonable calendars satisfying the cable television companies requirements and satisfying various other operational constraints while minimizing the total number of violations on the home-away matches conditions.     

L-class enumeration algorithms for a discrete production planning problem with interval resource quantities

A discrete production planning problem which may be formulated as the multidimensional knapsack problem is considered, while resource quantities of the problem are supposed to be given as intervals. An approach for solving this problem based on using its relaxation set is suggested. Some L-class enumeration algorithms for the problem are described. Results of computational experiments are presented.     

A cutting plane approach for integrated planning and scheduling

In this paper we propose a branch-and-cut algorithm for solving an integrated production planning and scheduling problem in a parallel machine environment. The planning problem consists of assigning each job to a week over the planning horizon, whereas in the scheduling problem those jobs assigned to a given week have to be scheduled in a parallel machine environment such that all jobs are finished within the week. We solve this problem in two ways: (1) as a monolithic mathematical program and (2) using a hierarchical decomposition approach in which only the planning decisions are modeled explicitly, and the existence of a feasible schedule for each week is verified by using cutting planes. The two approaches are compared with extensive computational testing.     

Variable assignment and instruction scheduling for processor with multi-module memory

Multi-module memory has been employed in high-end digital signal processing system (DSP). It provides high memory bandwidth and low power operating mode for energy savings. However, making full use of these architectural features is a challenging problem for code optimization. In this paper, we propose an integer linear programming (ILP) model to optimize the performance and energy consumption of multi-module memories by solving variable assignment, instruction scheduling and operating mode setting problems simultaneously. The combined effect of performance and energy saving requirements has been considered as well. Specially, we develop two optimization techniques to improve the computation efficiency of our ILP model. The experimental results show that the optimal performance and energy solution can be achieved within a reasonable amount of time.     

An integer programming approach to generating airline crew pairings

The ability to generate crew pairings quickly is essential to solving the airline crew scheduling problem. Although techniques for doing so are well-established, they are also highly customized and require significant implementation efforts. This greatly impedes researchers studying important problems such as robust planning, integrated planning, and automated recovery, all of which also require the generating of crew pairings. As an alternative, we present an integer programming (IP) approach to generating crew pairings, which can be solved via traditional methods such as branch-and-bound using off-the-shelf commercial solvers. This greatly facilitates the prototyping and testing of new research ideas. In addition, we suggest that our modeling approach, which uses both connection variables and marker variables to capture the non-linear cost function and constraints of the crew scheduling problem, can be applicable in other scheduling contexts as well. Computational results using data from a major US hub-and-spoke carrier demonstrate the performance of our approach.     

Monthly tour scheduling models with mixed skills considering weekend off requirements

Unlike manufacturing, where standard shifts and days off are the rule, the service industry operates every day of the week across a month and a year. To maintain the morale and productivity of the workers in the service industry, the weekend off requirements, one of the important work preferences for the workers, should be respected and balanced for a longer planning horizon beyond a week. This paper deals with the monthly tour scheduling problem with mixed skills considering the weekend off requirements in contrast to the weekly planning horizon that is typical in most literature. The objective is to obtain the most economical mix of types of workers satisfying the patterns of demands for the workers and desired work characteristics. Two model formulations are developed based on implicit programming techniques. One model uses a general integer programming (GIP) formulation and assigns the lunch break hours aggregately to the workers based on the worker types. The other one adopts a binary integer programming (BIP) formulation and assigns the lunch break hours explicitly to the individual workers. The effectiveness of the two models is illustrated by the numerical tests and the results show that the BIP formulation is more efficient than the GIP formulation.     

用演化Agent方法处理整数线性规划问题

描述了一种演化ａｇｅｎｔ模型,并用这种模型来处理整数线性规划问题,该模型基于求整数一性规划问题的分枝定界方法,具有解并行,目标驱动,时间复杂性低等特点。     

Time-constrained project scheduling with adjacent resources

We develop a decomposition method for the Time-Constrained Project Scheduling Problem (TCPSP) with adjacent resources. For adjacent resources the resource units are ordered and the units assigned to a job have to be adjacent. On top of that, adjacent resources are not required by single jobs, but by job groups. As soon as a job of such a group starts, the adjacent resource units are occupied, and they are not released before all jobs of that group are completed. The developed decomposition method separates the adjacent resource assignment from the rest of the scheduling problem. Test results demonstrate the applicability of the decomposition method. The presented decomposition forms a first promising approach for the TCPSP with adjacent resources and may form a good basis to develop more elaborated methods.     

New models for the Mirrored Traveling Tournament Problem

The Mirrored Traveling Tournament Problem (mTTP) is a challenging combinatorial optimization problem which consists in generating a timetable for sports tournaments with two half series, what is equivalent to a double round-robin timetable problem. The distance traveled by the teams should be minimized in the final timetable, and a new objective is to minimize the longest distance traveled, named MinMaxTTP. It is proposed an integer programming formulation to the mTTP and two models with dynamic constraints to its solution. Both models are based on the detection of independent sets on conflict graphs, whose use has not been reported in the literature about the problem. Real data benchmarks from a baseball tournament are used in the experiments carried out.     

Throughput-Optimal Sequences for Cyclically Operated Plants

In this paper, we present a method to determine globally optimal schedules for cyclically operated plants where activities have to be scheduled on limited resources. In cyclic operation, a large number of entities is processed in an identical time scheme. For strictly cyclic operation, where the time offset between entities is also identical for all entities, the objective of maximizing throughput is equivalent to the minimization of the cycle time. The resulting scheduling problem is solved by deriving a mixed integer optimization problem from a discrete event model. The model includes timing constraints as well as open sequence decisions for the activities on the resources. In an extension, hierarchical nesting of cycles is considered, which often allows for schedules with improved throughput. The method is motivated by the application to high throughput screening plants, where a specific combination of requirements has to be obeyed (e.g. revisited resources, absence of buffers, or time window constraints).     

A heuristic algorithm for master planning that satisfies multiple objectives

This study proposes a heuristic algorithm, called the multi-objective master planning algorithm (MOMPA), to solve master planning (MP) problems for a supply chain network with multiple finished products. MOMPA has three objectives: to minimize delay penalties, to minimize use of outsourcing capacity, and to minimize the costs of materials, production, processing, transportation, and inventory holding—all while respecting the capacity limitations and the demand deadlines of all those involved in a given supply chain network. MOMPA plans each demand, one by one, without backtracking, and sorts those demands using a sorting mechanism that is part of the algorithm. For each demand, the minimum production cost tree is determined within the limits of the time bucket for the demand deadline. The maximum available capacity of this tree is then computed for the “no delay” case. Following this calculation, the delay-or-not criterion is evaluated to determine whether or not further delay is necessary. MOMPA compares the results of these two procedures and allocates the appropriate capacities to the demand for all the nodes on the selected tree. If the minimum cost production tree has no available capacity, MOMPA adjusts the network and looks for a new tree. With complexity and computational analysis, MOMPA is shown to be very efficient in solving MP problems, sometimes generating the same optimal solution as the LP model.     

Rolling-horizon and fix-and-relax heuristics for the parallel machine lot-sizing and scheduling problem with sequence-dependent set-up costs

In this paper we develop new rolling-horizon and fix-and-relax heuristics for the identical parallel machine lot-sizing and scheduling problem with sequence-dependent set-up costs. Unlike previous papers, our procedures are based on a compact formulation relying on the hypotheses of identical machines. This feature makes our approach suitable for large-scale applications (with hundreds of machines) arising in the textile and fiberglass industries. Moreover, our procedures are shown to provide a feasible solution for any feasible instance. Comparisons with lower bounds provided by a truncated branch-and-bound show that the gap between the best heuristic solution and the lower bound never exceeds 3%.