Refine
Document Type
- Article (4)
- Part of a Book (1)
Language
- English (5)
Keywords
- algorithmic mechanism design (3)
- game theory (3)
- machine scheduling (2)
- Logistics (1)
- Scheduling (1)
- incentive compatibility (1)
- logistics (1)
- truthfulness (1)
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.
A parallel machine schedule updating game with compensations and clients averse to uncertain loss
(2019)
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 eironment. 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, 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 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.
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 iolve multiple selfish players.