Volltext-Downloads (blau) und Frontdoor-Views (grau)

Incentive compatible mechanisms for scheduling two-parameter job agents on parallel identical machines to minimize the weighted number of late jobs

  • 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.

Export metadata

Additional Services

Search Google Scholar


Document Type:Article
Author:Dominik KressORCiD, Sebastian Meiswinkel, Erwin PeschORCiD
Center:Center for Advanced Studies in Management (CASiM)
Parent Title (English):Discrete Applied Mathematics
Issue:June 2018
Year of Completion:2018
First Page:89
Last Page:101
Tag:algorithmic mechanism design; game theory; logistics; machine scheduling; truthfulness
Content Focus:Academic Audience
Peer Reviewed:Yes
Rankings:AJG Ranking / 2
VHB Ranking / A
SJR Ranking / Q2
Licence (German):License LogoUrheberrechtlich geschützt