Art der Publikation: Beitrag in Zeitschrift

Incentive Compatible Mechanisms for Scheduling Two-Parameter Job Agents on Parallel Identical Machines to Minimize the Weighted Number of Late Jobs

Autor(en):

Kress, D.; Meiswinkel, S.; Pesch, E.

Titel der Zeitschrift:

Discrete Applied Mathematics

Jahrgang (Veröffentlichung):

242 (2018)

Seiten:

89-101

Sprache:

Englisch

Schlagworte:

Algorithmic mechanism design, Machine scheduling, Truthfulness, Game theory, Logistics

Digital Object Identifier (DOI):

doi:10.1016/j.dam.2017.08.026

Zitation:

Download BibTeX

Kurzfassung

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.