Constraint programming solvers are known to perform remarkably well for most scheduling problems. However, when comparing the performance of different available solvers, there is usually no clear winner over all relevant problem instances. This gives rise to the question of how to select a promising solver when knowing the concrete instance to be solved. In this article, we aim to provide first insights into this question for the flexible job shop scheduling problem. We investigate relative performance differences among five constraint programming solvers on problem instances taken from the literature as well as randomly generated problem instances. These solvers include commercial and non-commercial software and represent the state-of-the-art as identified in the relevant literature. We find that two solvers, the IBM ILOG CPLEX CP Optimizer and Google’s OR-Tools, outperform alternative solvers. These two solvers show complementary strengths regarding their ability to determine provably optimal solutions within practically reasonable time limits and their ability to quickly determine high quality feasible solutions across different test instances. Hence, we leverage the resulting performance complementarity by proposing algorithm selection approaches that predict the best solver for a given problem instance based on instance features or parameters. The approaches are based on two machine learning techniques, decision trees and deep neural networks, in various variants. In a computational study, we analyze the performance of the resulting algorithm selection models and show that our approaches outperform the use of a single solver and should thus be considered as a relevant tool by decision makers in practice.

We address an optimization problem that arises at seaports where containers are transported between stacking areas and small buffer areas of restricted capacity that are located within the reach of quay cranes. The containers are transported by straddle carriers that have to be routed such that given unloading and loading sequences of the containers at the quay cranes are respected. The objective is to minimize the turnaround times of the vessels. We analyze the problem’s computational complexity, present an integer program, and propose a heuristic framework that is based on decomposing the problem into its routing component and a component that handles the time variables and buffer capacities. The framework is analyzed in computational tests that are based on real-world data. Based on these tests, we analyze the question of whether or not it pays off to deviate from the approach of permanently assigning a fixed number of straddle carriers to each quay crane, which is the strategy that is currently implemented at the port.

We consider the problem of designing truthful mechanisms for machine scheduling problems with parallel identical machines where some of the jobs’ characteristics are private information of their respective owners and a central decision maker is in charge of computing the schedule. We study a two-parameter setting, where weights and due dates are private information while processing times are publicly known. The global objective is to minimize the sum of the weights of those jobs that are completed after their due dates. We derive a set of properties that is equivalent to the well known condition of cycle monotonicity, which is a general condition for truthful mechanisms in non-coex valuation function domains. Our results utilize knowledge about the underlying scheduling problem, so that the resulting properties are easier to implement and verify than the general condition of cycle monotonicity. We illustrate the use of our results by analyzing an example algorithm that has recently been proposed in the literature for the case of one machine.

This paper provides a literature overview on (direct revelation) algorithmic mechanism design in the context of machine scheduling problems. Here, one takes a game-theoretic perspective and assumes that part of the relevant data of the machine scheduling problem is private information of selfish players (usually machines or jobs) who may try to influence the solution determined by the scheduling algorithm by submitting false data. A central planner is in charge of controlling and designing the algorithm and a rewarding scheme that defines payments among planner and players based on the submitted data. The planner may, for example, want to design algorithm and payments such that reporting the true data always maximizes the utility functions of rationally acting players, because this enables the planner to generate fair solutions with respect to some social criterion that considers the interests of all players. We review the categories and characterizing problem features of machine scheduling settings in the algorithmic mechanism design literature and extend the widely accepted classification scheme of Graham et al. (Ann Discrete Math 5:287–326, <a aria-controls="popup-references" aria-expanded="false" role="button" title="View reference" href="https://link.springer.com/article/10.1007/s00291-018-0512-8#CR54">1979</a>) for scheduling problems to include aspects relating to mechanism design. Based on this hierarchical scheme, we give a systematic overview of recent contributions in this field of research.

In this paper we analyze the effect of including price competition into a classical (market entrant’s) competitive location problem. The multinomial logit approach is applied to model the decision process of utility maximizing customers. We provide complexity results and show that, given the locations of all facilities, a fixed-point iteration approach that has previously been introduced in the literature can be adapted to reliably and quickly determine local price equilibria. We present examples of problem instances that demonstrate the potential non-existence of price equilibria and the case of multiple local equilibria in prices. Furthermore, we show that different price sensitivity levels of customers may actually affect optimal locations of facilities, and we provide first insights into the performance of heuristic algorithms for the location problem.