•Introduces a new tournament design problem – Rest Mismatch Problem.•Gives mixed-integer linear formulations and constraint programming formulation of the problem.•Provides some theoretical ...findings.•Develops a heuristic algorithm that finds a schedule with few mismatches.•Reports computational results.
In sports tournaments, an occurrence of a difference in the rest periods of opponent teams in a game, which we refer to as a rest mismatch, will disadvantage the less rested team. Thus, it is only fair to expect opposing teams to have rested equally before their game. In this work, we introduce and study the Rest Mismatch Problem where the goal is to minimize the number of rest mismatches in a round robin tournament. Two integer linear formulations and a constraint programming formulation are provided, and their computational performances are compared for several problem instances. Moreover, a heuristic algorithm is developed which finds a single round robin schedule with zero mismatches when the number of teams in the tournament is a multiple of 8, and four mismatches when it is a multiple of 4 but not 8.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK, ZRSKP
A fair schedule helps in improving the competitiveness and attractiveness of sports tournaments and in turn contributes positively to the sports economy. Break minimization and carryover effects ...minimization are considered to be two important criteria of fairness in scheduling of compact round-robin tournaments, and most related research looks at these problems separately. Various studies have sought to minimize the carryover effects in tournaments so that the number of breaks per team does not exceed a specific level. This study, however, is the first effort to define an integrated problem that aims to minimize the carryover effects and the number of breaks simultaneously for round-robin tournaments. We first introduce the mathematical formulation for the problem, whose objective measures how well a schedule simultaneously performs with respect to the number of breaks and the carryover effects. We then develop a heuristic method for this computationally hard problem. Comparing our results with the previous literature and the current practices of some European leagues, we show that our method provides schedules with better objective function values.
Full text
Available for:
CEKLJ, EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
Many sports leagues first announce the games to be played in each round and then determine their matchdays as the season progresses. This study focuses on the fairness criterion of minimizing the ...total rest difference among opposing teams to find the matchdays for an announced schedule. We show that the problem is decomposable into optimizing the rounds separately. We also provide a polynomial-time exact algorithm for canonical schedules.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Fairness is a key consideration in designing sports schedules. When two teams play against each other, it is only fair to let them rest the same amount of time before their game. In this study, we ...aim to reduce, if not eliminate, the difference between the rest durations of opposing teams in each game of a round-robin tournament. The rest difference problem proposed here constructs a timetable that determines both the round and the matchday of each game such that the total rest difference throughout the tournament is minimized. We provide a mixed-integer programming formulation and a matheuristic algorithm that tackle the rest difference problem. Moreover, we develop a polynomial-time exact algorithm for some special cases of the problem. This algorithm finds optimal schedules with zero total rest difference when the number of teams is a positive-integer power of 2 and the number of games in each day is even. Some theoretical results regarding tournaments with one-game matchdays are also presented.
Full text
Available for:
EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
► We examine a novel class of optimization problems that model restoring infrastructure systems. ► These new problems integrate network design and scheduling decisions. ► We utilize residual network ...optimality conditions in creating a dispatching rule. ► Our models and algorithms are tested on realistic case studies of infrastructure systems. ► The dispatching rule can be utilized in real-time restoration planning activities.
We consider the problem of restoring services provided by infrastructure systems after an extreme event disrupts them. This research proposes a novel integrated network design and scheduling problem that models these restoration efforts. In this problem, work groups must be allocated to build nodes and arcs into a network in order to maximize the cumulative weighted flow in the network over a horizon. We develop a novel heuristic dispatching rule that selects the next set of tasks to be processed by the work groups. We further propose families of valid inequalities for an integer programming formulation of the problem, one of which specifically links the network design and scheduling decisions. Our methods are tested on realistic data sets representing the infrastructure systems of New Hanover County, North Carolina in the United States and lower Manhattan in New York City. These results indicate that our methods can be used in both real-time restoration activities and long-term scenario planning activities. Our models are also applied to explore the effects on the restoration activities of aligning them with the goals of an emergency manager and to benchmark existing restoration procedures.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK
•We propose models for decentralization in interdependent infrastructure restoration.•We provide new mathematical formulations to capture restoration interdependencies.•We measure the loss in ...restoration effectiveness resulting from decentralization.•This loss can be greatly mitigated by having infrastructures share information.
We consider restoring multiple interdependent infrastructure networks after a disaster damages components in them and disrupts the services provided by them. Our particular focus is on interdependent infrastructure restoration (IIR) where both the operations and the restoration of the infrastructures are linked across systems. We provide new mathematical formulations of restoration interdependencies in order to incorporate them into an interdependent integrated network design and scheduling (IINDS) problem. The IIR efforts resulting from solving this IINDS problem model a centralized decision-making environment where a single decision-maker controls the resources of all infrastructures. In reality, individual infrastructures often determine their restoration efforts in an independent, decentralized manner with little communication among them. We provide algorithms to model various levels of decentralization in IIR efforts. These algorithms are applied to realistic damage scenarios for interdependent infrastructure systems in order to determine the loss in restoration effectiveness resulting from decentralized decision-making. Our computational tests demonstrate that this loss can be greatly mitigated by having infrastructures share information about their planned restoration efforts.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK
We consider the problem faced by managers of critical civil interdependent infrastructure systems of restoring essential public services after a non-routine event causes disruptions to these ...services. In order to restore the services, we must determine the set of components (or tasks) that will be temporarily installed or repaired, assign these tasks to work groups, and then determine the schedule of each work group to complete the tasks assigned to it. These restoration planning and scheduling decisions are often undertaken in an independent, sequential manner. We provide mathematical models and optimization algorithms that integrate the restoration and planning decisions and specifically account for the interdependencies between the infrastructure systems. The objective function of this problem provides a measure of how well the services are being restored over the horizon of the restoration plan, rather than just focusing on the performance of the systems after all restoration efforts are complete. We test our methods on realistic data representing infrastructure systems in New York City. Our computational results demonstrate that we can provide integrated restoration and scheduling plans of high quality with limited computational resources. We also discuss the benefits of integrating the restoration and scheduling decisions.
Full text
Available for:
CEKLJ, EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
We consider the problem faced by managers of interdependent civil infrastructure systems of mitigating the impact of a non-routine event, and restoring essential public services after this ...non-routine event causes disruptions to these services. In order to restore the services, we must determine the set of components (or tasks) that will be temporarily installed or repaired, assign these tasks to work groups, and then determine the schedule of each work group to complete the tasks assigned to it. This research considers a novel integrated interdependent network design and scheduling problem (IINDS) that can serve as a decision aid to formulate the restoration efforts in these interdependent infrastructure systems. The objective function of the problem provides a measure of the community resilience, which is the ability of communities to carry out response and recovery activities in ways that minimize physical and social disruptions. The objective function of IINDS problem evaluates how well the services are being restored over the horizon of the restoration plan, rather than just focusing on the performance of the systems after all restoration efforts are complete. We develop new optimization methods for this class of problems that use concepts from the areas of network flows and scheduling. Our methods are tested on realistic data sets representing the infrastructure systems of New Hanover County in North Carolina and Lower Manhattan area of New York City, which were created through collaborations with managers of these systems. Our computational results demonstrate that we can provide integrated restoration and scheduling plans of high quality with limited computational resources. We also discuss the benefits of centralized decision making and information sharing among interdependent infrastructure systems as opposed to independent decision making of each infrastructure separately. Further, we provide a mathematical framework that integrates pre-event mitigation decisions into IINDS problem. Finally, we discuss future research directions about how IINDS problem can be extended to model other flow network systems.
This paper describes the decision technology MUNICIPAL (Multi-Network Interdependent Critical Infrastructure Program for the Analysis of Lifelines). This technology supports decision makers in the ...restoration of critical infrastructure systems after an extreme event. MUNICIPAL consists of four components: a vulnerability simulator which predicts damage to infrastructure components given a specific disaster scenario, an optimization module which produces a restoration plan given a damage scenario, a GIS interface to visualize and manipulate the data, and a database structured to support the data needs and integration of the other three modules. A case study was developed with the emergency management department of New Hanover County, North Carolina, to assess the technology with respect to the impact of a hurricane. PUBLICATION ABSTRACT
