| 1. |
- Bidot, Julien, et al.
(författare)
-
A theoretic and practical framework for scheduling in a stochastic environment
- 2009
-
Ingår i: Journal of Scheduling. - : Springer Science and Business Media LLC. - 1094-6136 .- 1099-1425. ; 12:3, s. 315-344
-
Tidskriftsartikel (refereegranskat)abstract
- There are many systems and techniques that address stochastic planning and scheduling problems, based on distinct and sometimes opposite approaches, especially in terms of how generation and execution of the plan, or the schedule, are combined, and if and when knowledge about the uncertainties is taken into account. In many real-life problems, it appears that many of these approaches are needed and should be combined, which to our knowledge has never been done. In this paper, we propose a typology that distinguishes between proactive, progressive, and revision approaches. Then, focusing on scheduling and schedule execution, a theoretic model integrating those three approaches is defined. This model serves as a general template to implement a system that will fit specific application needs: we introduce and discuss our experimental prototypes which validate our model in part, and suggest how this framework could be extended to more general planning systems.
|
|
| 2. |
- Damaschke, Peter, 1963
(författare)
-
Scheduling search procedures: The wheel of fortune
- 2006
-
Ingår i: Journal of Scheduling. - : Springer Science and Business Media LLC. - 1099-1425 .- 1094-6136. ; 9:6, s. 545-557
-
Tidskriftsartikel (refereegranskat)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.
|
|
