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 address the problem of sequencing n jobs that are partitioned into F families on a single processor. A setup operation is needed at the beginning of the schedule and whenever a job of one family is succeeded by a job of another family. These setup operations are assumed to not require time but are associated with a fixed setup cost which is identical for all setup operations. Jobs must be completed no later than by a given deadline. The objective is to schedule all jobs such that the total setup cost is minimized. This objective is identical to minimizing the number of setup operations. We provide a sketch of the proof of the problem’s strong NP-hardness as well as some properties of optimal solutions and an O(nlogn+nF)O(nlog⁡n+nF) algorithm that approximates the cost of an optimal schedule by a factor of F. For details, we refer to our full paper.

This paper addresses a flexible job shop scheduling problem with sequence-dependent setup times that incorporates heterogeneous machine operator qualifications. The objective is to minimize the makespan. We present a mixed-integer program and sketch exact and heuristic solution approaches that are based on a decomposition of the problem into a vehicle routing problem and a machine operator assignment problem. The solution methods are analyzed in computational tests. For details, we refer to our full paper.

We consider a flexible job shop scheduling problem that incorporates machine operators and aims at makespan minimization. In a detailed overview of the related literature, we reveal the fact that the research in this field is mainly concerned with (meta-)heuristic approaches. Only few papers consider exact approaches. In order to promote the use of exact approaches and in order to facilitate the evaluation of the performance of heuristic approaches, we present two mathematical models, a mixed-integer programming model and a constraint programming model, that are analyzed and compared with a state-of-the-art heuristic in computational tests with a standard solver.

There is a finite number of non-cooperating clients, who are averse to uncertain loss and compete for execution of their jobs not later than by their respective due dates in a parallel service environment. For each client, a due date violation implies a cost. In order to address the minimization of the total scheduling cost of all clients as a social criterion, a game mechanism is suggested. It is designed such that no client has an incentive to claim a false due date or cost. The game mechanism allows the clients to move their jobs to complete earlier in a given schedule. However, they must compensate costs of those clients whose jobs miss their due dates because of these moves. Algorithmic aspects are analyzed. Furthermore, a polynomial time algorithm that determines an equilibrium of the considered game is suggested and embedded into the game mechanism. Computational tests analyze the performance and practical suitability of the resulting game mechanism.

We consider a flexible job shop scheduling problem with sequence-dependent setup times that incorporates heterogeneous machine operator qualifications by taking account of machine- and operator-dependent processing times. We analyze two objective functions, minimizing the makespan and minimizing the total tardiness, and present exact and heuristic decomposition-based solution approaches. These approaches divide the scheduling problem into a vehicle routing problem with precedence constraints and an operator assignment problem, and connect these problems via logic inequalities. We assess the quality of our solution methods in an extensive computational study that is based on randomly generated as well as real-world problem instances.

We consider a scheduling problem for two gantry cranes moving on the same rails at a single storage block. Containers originating at the seaside have to be stored in the block and containers that are already stored in the storage area at the beginning of the planning horizon have to be delivered to the landside handover point within given time windows. Most commonly in seaport operations, the berthing time of vessels is to be minimized. Thus, the objective considered in this article is to minimize the makespan of seaside container processing while guaranteeing on-time processing of landside containers and while considering non-crossing constraints among cranes. We allow preemption of seaside container processing. This means that one crane may move a seaside container to an intermediate storage slot, and the other crane takes it to its designated position. This has previously been shown to be an effective method of reducing the makespan when compared to classical approaches. We present a dynamic programming (DP) algorithm and a related beam search heuristic. The DP method makes use of bounding techniques and applies dominance properties of optimal solutions. In computational tests, we show that the DP approach clearly outperforms CPLEX and that it is able to quickly solve instances with real-world yard settings. The beam search heuristic is shown to be capable of quickly improving solutions of heuristic approaches that have previously been introduced in the literature. This allows both algorithms to be applied in real-world online settings, where container data is revealed incrementally.

We address the single-machine batch scheduling problem with the objective of minimizing the total setup cost. This problem arises when there are n jobs that are partitioned into F families and when setup operations are required whenever the machine switches from processing a job of one family to processing a job of another family. We assume that setups do not require time but are associated with a fixed cost which is identical for all setup operations. Each job has a processing time and an associated deadline. The objective is to schedule all jobs such that they are on time with respect to their deadlines and the total setup cost is minimized. We show that the decision version of this problem is NP-complete in the strong sense. Furthermore, we present properties of optimal solutions and an O(nlogn+nF)O(nlog⁡n+nF) algorithm that approximates the cost of an optimal schedule by a factor of F. The algorithm is analyzed in computational tests.

Globalization and digitalization have lead to new challenges and perspectives in intermodal transport logistics of large city sea ports and megahubs. In particular, due to an enormous increase of the container throughput over the last decades and the automatization of megahubs, new planning problems in this field must consistently be addressed by smart software solutions. In this research article, we sketch some challenges that arise at megahubs and outline how mechanism design, as a popular tool that combines ideas from game theory and computer science, can be an approach to tackle logistics problems that involve multiple selfish players.

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, 1979) 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.

We consider the problem of scheduling two identical rail mounted gantry cranes (twin cranes) working within a single storage area (block) at a seaport. The cranes, referred to as seaside crane and landside crane, cannot pass each other. Our focus is on peak times, where the minimization of dwell times of vessels at the berth is typically the major objective of port authorities. We allow the seaside crane to drop inbound containers at intermediate positions where the landside crane takes over and delivers the containers to their target slots. Earlier studies have shown that allowing the cranes to cooperate in this manner is beneficial, at least when there are no containers that are already stored in the block at the beginning of the planning horizon and that have to be delivered to the landside handover point by the landside crane within given time windows. In this paper, we analyze if the positive effect of letting the cranes cooperate persists when these latter jobs are present. This might have a critical impact, because these tasks are performed close to the landside whereas supporting the seaside crane is performed rather close to the seaside. We present complexity results and some general problem insights. Furthermore, we introduce lower bounds and develop heuristic procedures that apply these bounds. The performance of the algorithms is evaluated in computational tests.

We consider the problem of designing polynomial time 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-convex 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.

There is a finite number of non-cooperating clients competing for execution of their jobs by a single service provider in order to minimize job completion time costs. The clients can move their jobs to complete earlier in a given sequence. However, they have to compensate the cost increase to the other clients whose jobs are completed later due to this move. All clients are assumed to be fully risk averse. A game mechanism is suggested, such that no client has an incentive to claim false cost and a social criterion, i.e. the minimization of the total cost of all clients, is addressed. A polynomial time algorithm that finds a game equilibrium is suggested and embedded into the game mechanism. Computational tests analyze the performance and practical suitability of the resulting mechanism. We outline potential directions for future research in a similar setting in a parallel service environment.

We consider a basic partition problem that subdivides Stock Keeping Units (SKUs) into disjoint subsets, such that the minimum number of groups has to be accessed when retrieving a given order set under a pick-by-order policy. We formalize this SKU partition problem and show its applicability in a wide range of storage systems that are based on separating their storage space into groups of SKUs stored in separate areas; examples are carousel racks and mobile shelves. We analyze the computational complexity and propose two mathematical models for the problem under consideration. Furthermore, we present an ejection chain heuristic and a branch and bound procedure. We analyze these algorithms and the mathematical models in computational tests.

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.

We introduce a combination of the problem of partitioning a set of vertices of a bipartite graph into disjoint subsets of restricted size and the Min-Max Weighted Matching Problem. The resulting problem has applications in intermodal transport. We propose a mathematical model and prove the problem to be NP-hard in the strong sense. Two heuristic frameworks that decompose the problem into its partitioning and matching components are presented. Additionally, we analyze a basic implementation of tabu search and a genetic algorithm for the integrated problem. All algorithms outperform standard optimization software. Moreover, the decomposition heuristics outperform the classical metaheuristic approaches for the integrated problem. All algorithms outperform standard,,optimization software. Moreover, the decomposition heuristics outperform the classical metaheuristic approaches.

We introduce and analyze the Partitioning Min–Max Weighted Matching (PMMWM) Problem. PMMWM combines the problem of partitioning a set of vertices of a bipartite graph into disjoint subsets of restricted size and the strongly NP-hard Min–Max Weighted Matching (MMWM) Problem, that has recently been introduced in the literature. In contrast to PMMWM, the latter problem assumes the partitioning to be given. Applications arise in the field of intermodal container terminals and sea ports. We propose a MILP formulation for PMMWM and prove that the problem is NP-hard in the strong sense. Two heuristic frameworks are presented. Both of them outperform standard optimization software. Our extensive computational study proves that the algorithms provide high quality solutions within reasonable time.

We reinvestigate a theoretical result by Rhim and Cooper (2005), who provide a uniqueness condition for price equilibria in a two-stage competitive product positioning model. We show that this condition is very restrictive by providing a simple proof for the fact that it eventually results in parametric pricing. As a consequence, it misses the two-stage characteristic that the model originally aims at.

In this paper we analyze the performance of several heuristic and metaheuristic approaches for solving the Partitioning Min-Max Weighted Matching (PMMWM) Problem. Applications of PMMWM arise in the field of balancing workload at intermodal container terminals. The problem combines the problem of partitioning a set of vertices of a bipartite graph into disjoint subsets of restricted size and the strongly NP-hard Min-Max Weighted Matching (MMWM) Problem. Both problems have recently been introduced in the literature.

The Logistics Algorithms Visualization and Education Software (LAVES) is an open source project at the University of Siegen, aiming at supporting business and business informatics students in understanding the basic concepts of algorithms that are applied to solve problems arising in operations research, especially in logistics, by means of visualization. It allows students to create problem instances click-by-click with direct graphical feedback, offers a set of algorithm-related controls, presents execution-table-views as used by the students when manually processing algorithms, depicts and highlights the related pseudocode (including LATEX formulas), and includes an exercise mode. LAVES is accompanied by a development kit (LAVESDK) that allows instructors (with Java knowledge) to implement course-specific algorithm visualizations (called plugins) to be used with LAVES. The development kit is generic and provides a broad range of tools. In this paper, we present the basic features of LAVES and LAVESDK and report on first classroom experiences and student feedback.

This book deals with classical competitive location problems where two players, leader and follower, sequentially enter markets with given numbers of facilities. The markets under consideration are represented as networks. The book provides a detailed overview of the literature on competitive and voting location, and it presents extensions and variations of the classical models, with a focus on the incorporation of proportional choice rules, non-discrete demand (edge demand), or additional pricing decisions of the players. It provides corresponding mathematical models, insights into the computational complexity of the resulting problems and proposes and analyzes adequate solution methods.

This paper analyzes (r|p)-centroid problems on networks with vertex and edge demand under a binary choice rule. Bilevel programming models are presented for the discrete problem class. Furthermore, NP-hardness proofs for the discrete and continuous (1|p)-centroid problem on general networks with edge demand only are provided. Nevertheless, an efficient algorithm to determine a discrete (1|p)-centroid of a tree network with vertex and edge demand can be derived.

We present a survey of recent developments in the field of sequential competitive location problems, including the closely related class of voting location problems, i.e. problems of locating resources as the result of a collective election. Our focus is on models where possible locations are not a priori restricted to a finite set of points. Furthermore, we restrict our attention to problems defined on networks. Since a line, i.e. an interval of one-dimensional real space, may be interpreted as a special type of network and because models defined on lines might contain ideas worth adopting in more general network models, we include these models as well, yet without describing them in detail for the sake of brevity.

This paper is concerned with a competitive or voting location problem on networks under a proportional choice rule that has previously been introduced by Bauer et al. (1993). We refine a discretization result of the authors by proving convexity and concavity properties of related expected payoff functions. Furthermore, we answer the long time open question whether 1-suboptimal points are always vertices by providing a counterexample on a tree network.