### Skapa referens, olika format (klipp och klistra)

**Harvard**

Damaschke, P. (2006) *Scheduling search procedures: The wheel of fortune*.

** BibTeX **

@article{

Damaschke2006,

author={Damaschke, Peter},

title={Scheduling search procedures: The wheel of fortune},

journal={Journal of Scheduling},

issn={1094-6136},

volume={9},

issue={6},

pages={545-557},

abstract={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 players 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.},

year={2006},

keywords={searching, game theory, nonclairvoyant scheduling},

}

** RefWorks **

RT Journal Article

SR Print

ID 21849

A1 Damaschke, Peter

T1 Scheduling search procedures: The wheel of fortune

YR 2006

JF Journal of Scheduling

SN 1094-6136

VO 9

IS 6

SP 545

OP 557

AB 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 players 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.

LA eng

DO 10.1007/s10951-006-8788-y

OL 30