Incentive compatible mechanisms for scheduling two-parameter job agents on parallel identical machines to minimize the weighted number of late jobs
Publication date
2017-10-05
Document type
Forschungsartikel
Author
Organisational unit
University of Siegen
Publisher
Elsevier
Series or journal
Discrete Applied Mathematics
ISSN
Periodical volume
242
First page
89
Last page
101
Peer-reviewed
✅
Part of the university bibliography
Nein
Language
English
Keyword
Algorithmic mechanism design
Machine scheduling
Truthfulness
Game theory
Logistics
Abstract
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.
Version
Published version
Access right on openHSU
Metadata only access