CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Scheduling search procedures: The wheel of fortune

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers))
Journal of Scheduling (1094-6136). Vol. 9 (2006), 6, p. 545-557.
[Artikel, refereegranskad vetenskaplig]

Suppose that a player can make progress on n jobs, and her goal is to complete a target job among them, as soon as possible. Unfortunately she does not know what the target job is, perhaps not even if the target exists. This is a typical situation in searching and testing. Depending on the player’s prior knowledge and optimization goals, this gives rise to various optimization problems in the framework of game theory and, sometimes, competitive analysis. Continuing earlier work on this topic, we study another two versions. In the first game, the player knows only the job lengths and wants to minimize the completion time. A simple strategy that we call wheel-of-fortune (WOF) is optimal for this objective. A slight and natural modification however makes this game considerably more difficult: If the player can be sure that the target is present, WOF fails. However, we can still construct in polynomial time an optimal strategy based on WOF. We also prove that the tight absolute bounds on the expected search time. In the final part, we study two competitive-ratio minimization problems where either the job lengths or the target probabilities are known. We show their equivalence, describe the structure of optimal strategies, and give a heuristic solution.

Nyckelord: searching, game theory, nonclairvoyant scheduling



Denna post skapades 2006-08-25. Senast ändrad 2015-02-11.
CPL Pubid: 21849

 

Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers)

Ämnesområden

Teoretisk datalogi

Chalmers infrastruktur