Minimizing breaks by maximizing cuts

We propose to solve the break minimization problem in sports scheduling by transforming it into a maximum cut problem in an undirected graph and applying a branch-and-cut algorithm. Our approach outperforms previous approaches with constraint programming and integer programming techniques.     

Solving mirrored traveling tournament problem benchmark instances with eight teams

A two-phase method based on generating timetables from one-factorizations and finding optimal home/away assignments solved the mirrored traveling tournament problem benchmark instances NL8 and CIRC8 at the Challenge Traveling Tournament Problems homepage http://mat.gsia.cmu.edu/TOURN/.     

A new branch-and-price algorithm for the traveling tournament problem

The traveling tournament problem (ttp) consists of finding a distance-minimal double round-robin tournament where the number of consecutive breaks is bounded. For solving the problem exactly, we propose a new branch-and-price approach. The starting point is a new compact formulation for the ttp. The corresponding extensive formulation resulting from a Dantzig-Wolfe decomposition is identical to one given by Easton, K., Nemhauser, G., Trick, M., 2003. Solving the traveling tournament problem: a combined interger programming and constraint programming approach. In: Burke, E., De Causmaecker, P. (Eds.), Practice and Theory of Automated Timetabling IV, Volume 2740 of Lecture Notes in Computer Science, Springer Verlag Berlin/Heidelberg, pp. 100–109, who suggest to solve the tour-generation subproblem by constraint programming. In contrast to their approach, our method explicitly utilizes the network structure of the compact formulation: First, the column-generation subproblem is a shortest-path problem with additional resource and task-elementarity constraints. We show that this problem can be reformulated as an ordinary shortest-path problem over an expanded network and, thus, be solved much faster. An exact variable elimination procedure then allows the reduction of the expanded networks while still guaranteeing optimality. Second, the compact formulation gives rise to supplemental branching rules, which are needed, since existing rules do not ensure integrality in all cases. Third, non-repeater constraints are added dynamically to the master problem only when violated. The result is a fast exact algorithm, which improves many lower bounds of knowingly hard ttp instances from the literature. For some instances, solutions are proven optimal for the first time.     

A note on symmetry reduction for circular traveling tournament problems

The traveling tournament problem (TTP) consists of finding a distance-minimal double round-robin tournament where the number of consecutive breaks is bounded. Easton et al. (2001) introduced the so-called circular TTP instances, where venues of teams are located on a circle. The distance between neighboring venues is one, so that the distance between any pair of teams is the distance on the circle. It is empirically proved that these instances are very hard to solve due to the inherent symmetry. This note presents new ideas to cut off essentially identical parts of the solution space. Enumerative solution approaches, e.g. relying on branch-and-bound, benefit from this reduction. We exemplify this benefit by modifying the DFS∗ algorithm of Uthus et al. (2009) and show that speedups can approximate factor 4n.     

Constructing fair single round robin tournaments regarding strength groups with a minimum number of breaks

In this paper, we present a constructive method to show the existence of group-balanced single round robin tournaments (SRRTs) with a minimum number of breaks, if the number of groups is a power of 2 with identical even group sizes. When the number of teams is a multiple of 4, we show the existence of group-changing SRRTs with a minimum number of breaks, if the union of some groups contains exactly half of the teams.     

Sports tournaments, home–away assignments, and the break minimization problem

We consider the break minimization problem for fixing home–away assignments in round-robin sports tournaments. First, we show that, for an opponent schedule with n teams and n−1 rounds, there always exists a home–away assignment with at most breaks. Secondly, for infinitely many n, we construct opponent schedules for which at least breaks are necessary. Finally, we prove that break minimization for n teams and a partial opponent schedule with r rounds is an NP-hard problem for r≥3. This is in strong contrast to the case of r=2 rounds, which can be scheduled (in polynomial time) without any breaks.     

Solution of the NP-hard total tardiness minimization problem in scheduling theory

The classical NP-hard (in the ordinary sense) problem of scheduling jobs in order to minimize the total tardiness for a single machine 1‖ΣT _j is considered. An NP-hard instance of the problem is completely analyzed. A procedure for partitioning the initial set of jobs into subsets is proposed. Algorithms are constructed for finding an optimal schedule depending on the number of subsets. The complexity of the algorithms is O(n ²Σp _j ), where n is the number of jobs and p _j is the processing time of the jth job (j = 1, 2, …, n).     

Complexity of flow time minimization in a crossdock truck scheduling problem with asymmetric handover relations

We address a novel truck scheduling problem arising in crossdocking logistics, in which inbound trucks carry items (pallets) which must be sorted and loaded onto outbound trucks. We minimize the utilisation of the warehouse by focusing on the synchronisation between the different related trucks. The problem is to assign the trucks to the doors of the warehouse and sequence them, in order to minimize the total time spent in the system by the pallets. We discuss the complexity of the problem, showing that even with a single door the problem is NP-hard in general, and discuss some special cases.     

Scheduling a triple round robin tournament for the best Danish soccer league

In this paper, we present a solution method for the highly constrained problem of finding a seasonal schedule for the best Danish soccer league. The league differs from most sports leagues, since it plays a triple round robin tournament which leads to an uneven distribution of home and away games. The solution method presented here uses a logic-based Benders decomposition in which the master problem finds home-away pattern sets while the subproblem finds timetables. Furthermore, column generation techniques are used to enhance the speed of the master problem. The computational results show that the solution method is capable of solving the problem within reasonable time and the Danish Football Association has used it for scheduling the 2006/2007 season.     

On the convergence of interior-reflective Newton methods for nonlinear minimization subject to bounds

We consider a new algorithm, an interior-reflective Newton approach, for the problem of minimizing a smooth nonlinear function of many variables, subject to upper and/or lower bounds on some of the variables. This approach generatesstrictly feasible iterates by using a new affine scaling transformation and following piecewise linear paths (reflection paths). The interior-reflective approach does not require identification of an activity set. In this paper we establish that the interior-reflective Newton approach is globally and quadratically convergent. Moreover, we develop a specific example of interior-reflective Newton methods which can be used for large-scale and sparse problems.Research partially supported by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013.A000, and in part by NSF, AFOSR, and ONR through grant DMS-8920550, and by the Advanced Computing Research Institute, a unit of the Cornell Theory Center which receives major funding from the National Science Foundation and IBM Corporation, with additional support from New York State and members of its Corporate Research Institute.Corresponding author.     

Workforce routing and scheduling for electricity network maintenance with downtime minimization

We investigate a combined routing and scheduling problem for the maintenance of electricity networks. In electricity networks power lines must be regularly maintained to ensure a high quality of service. For safety reasons a power line must be physically disconnected from the network before maintenance work can be performed. After completing maintenance work the power line must be reconnected. Each maintenance job therefore consists of multiple tasks which must be performed at different locations in the network. The goal is to assign each task to a worker and to determine a schedule such that the downtimes of power lines and the travel effort of workers are minimized. For solving this problem, we combine a Large Neighborhood Search meta-heuristic with mathematical programming techniques. The method is evaluated on a large set of test instances which are derived from network data of a German electricity provider.     

Multi-machine scheduling lower bounds using decision diagrams

We consider parallel multi-machine scheduling with due times, where a partition of jobs is given where jobs in the same partition have a common release time, possibly precedence constraints, and cannot overlap. A formulation of decision diagrams for this problem greatly improves upon a more natural extension of the state-of-the-art for single-machine scheduling, and can provide decent lower bounds, outperforming existing solvers given the same short runtime limit, for problem instances with large time scales and tight due times.     

Minimizing shifts for personnel task scheduling problems: A three-phase algorithm

The personnel task scheduling problem is a subject of commercial interest which has been investigated since the 1950s. This paper proposes an effective and efficient three-phase algorithm for solving the shift minimization personnel task scheduling problem (SMPTSP). To illustrate the increased efficacy of the proposed algorithm over an existing algorithm, computational experiments are performed on a test problem set with characteristics motivated by employee scheduling applications. Experimental results show that the proposed algorithm outperforms the existing algorithm in terms of providing optimal solutions, improving upon most of the best-known solutions and revealing high-quality feasible solutions for those unsolved test instances in the literature.     

Tighter approximation bounds for LPT scheduling in two special cases

$Q||C_{\max }$ denotes the problem of scheduling n jobs on m machines of different speeds such that the makespan is minimized. In the paper two special cases of $Q||C_{\max }$ are considered: case I, when $m?1$ machine speeds are equal, and there is only one faster machine; and case II, when machine speeds are all powers of 2 (2-divisible machines). Case I has been widely studied in the literature, while case II is significant in an approach to design so called monotone algorithms for the scheduling problem.We deal with the worst case approximation ratio of the classic list scheduling algorithm ‘Largest Processing Time (LPT)’. We provide an analysis of this ratio $\mathit{Lpt}/\mathit{Opt}$ for both special cases: For ‘one fast machine’, a tight bound of $(\sqrt{3}+1)/2\approx 1.3660$ is given. For 2-divisible machines, we show that in the worst case $1.3673<\mathit{Lpt}/\mathit{Opt}<1.4$. Besides, we prove another lower bound of $955/699>(\sqrt{3}+1)/2$ when LPT breaks ties arbitrarily.To our knowledge, the best previous lower and upper bounds were $(4/3,3/2?1/2m]$ in case I [T. Gonzalez, O.H. Ibarra, S. Sahni, Bounds for LPT schedules on uniform processors, SIAM Journal on Computing 6 (1) (1977) 155–166], respectively $[4/3?1/3m,3/2]$ in case II [R.L. Graham, Bounds on multiprocessing timing anomalies, SIAM Journal on Applied Mathematics 17 (1969) 416–429; A. Kovács, Fast monotone 3-approximation algorithm for scheduling related machines, in: Proc. 13th Europ. Symp. on Algs. (ESA), in: LNCS, vol. 3669, Springer, 2005, pp. 616–627]. Moreover, Gonzalez et al. conjectured the lower bound 4/3 to be tight in the ‘one fast machine’ case [T. Gonzalez, O.H. Ibarra, S. Sahni, Bounds for LPT schedules on uniform processors, SIAM Journal on Computing 6 (1) (1977) 155–166].     

A composite-neighborhood tabu search approach to the traveling tournament problem

The Traveling Tournament Problem (TTP) is a combinatorial problem that combines features from the traveling salesman problem and the tournament scheduling problem. We propose a family of tabu search solvers for the solution of TTP that make use of complex combination of many neighborhood structures. The different neighborhoods have been thoroughly analyzed and experimentally compared. We evaluate the solvers on three sets of publicly available benchmarks and we show a comparison of their outcomes with previous results presented in the literature. The results show that our algorithm is competitive with those in the literature.     

Tight upper bounds for semi-online scheduling on two uniform machines with known optimum

We consider a semi-online version of the problem of scheduling a sequence of jobs of different lengths on two uniform machines with given speeds 1 and s. Jobs are revealed one by one (the assignment of a job has to be done before the next job is revealed), and the objective is to minimize the makespan. In the considered variant the optimal offline makespan is known in advance. The most studied question for this online-type problem is to determine the optimal competitive ratio, that is, the worst-case ratio of the solution given by an algorithm in comparison to the optimal offline solution. In this paper, we make a further step towards completing the answer to this question by determining the optimal competitive ratio for s between \(\frac{5 + \sqrt{241}}{12} \approx 1.7103\) and \(\sqrt{3} \approx 1.7321\), one of the intervals that were still open. Namely, we present and analyze a compound algorithm achieving the previously known lower bounds.

     

Heuristics for the mirrored traveling tournament problem

Professional sports leagues are a major economic activity around the world. Teams and leagues do not want to waste their investments in players and structure in consequence of poor schedules of games. Game scheduling is a difficult task, involving several decision makers, different types of constraints, and multiple objectives to optimize. The traveling tournament problem abstracts certain types of sport timetabling issues, where the objective is to minimize the total distance traveled by the teams. In this work, we tackle the mirrored version of this problem. We first propose a fast and effective constructive algorithm. We also describe a new heuristic based on the combination of the GRASP and iterated local search metaheuristics. A strong neighborhood based on ejection chains is also proposed and leads to significant improvements in solution quality. Very good solutions are obtained for the mirrored problem, sometimes even better than those found by other approximate algorithms for the less constrained non-mirrored version. Computational results are shown for benchmark problems and for a large instance associated with the main division of the 2003 edition of the Brazilian soccer championship, involving 24 teams.     

Tight bounds for popping algorithms

We sharpen run‐time analysis for algorithms under the partial rejection sampling framework. Our method yields improved bounds for: the cluster‐popping algorithm for approximating all‐terminal network reliability; the cycle‐popping algorithm for sampling rooted spanning trees; and the sink‐popping algorithm for sampling sink‐free orientations. In all three applications, our bounds are not only tight in order, but also optimal in30 constants.     

两台自私型机器上自私工件排序的PoA紧界

本文研究了两台自私型机器上有自私型工件的关于二元均衡的排序问题。对任意工件序列$L$, 证明了二元均衡排序的PoA的紧界为$\frac{8}{7}$。如果工件尺寸在区间$[1, r](r\ge1)$内, 得到了二元均衡排序的PoA的紧界为关于$r$的分段线性函数。