Art der Publikation: Beitrag in Sammelwerk

Decentralized Sequencing of Jobs on a Single Machine

Autor(en):

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

Titel des Sammelbands:

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

Seiten:

1-7

Ort(e):

Athens, Greece

Veröffentlichung:

2017

Sprache:

Englisch

Schlagworte:

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

Digital Object Identifier (DOI):

doi:10.1109/SSCI.2016.7850053

Zitation:

Download BibTeX

Kurzfassung

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.