Type of Publication: Article in Collected Edition

Decentralized Sequencing of Jobs on a Single Machine

Author(s):

Pesch, E.; Kovalyov, M. Y.; Kress, D.; Meiswinkel, S.

Title of Anthology:

Proceedings of the 2016 IEEE Symposium Series on Computational Intelligence (IEEE SSCI 2016)

pages:

1-7

Location(s):

Athens, Greece

Publication Date:

2017

Language:

Englisch

Keywords:

Games, Cost function, Contracts, Job shop scheduling, Processor scheduling, Companies, Computers

Digital Object Identifier (DOI):

doi:10.1109/SSCI.2016.7850053

Citation:

Download BibTeX

Abstract

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.