Basic Concepts
This chapter introduces and summarizes basic concepts and terminology in probability theory and stochastic scheduling, which build the foundation to develop optimal policies for a wide range of scheduling problems in subsequent chapters. In Section 1.1, w
- PDF / 392,410 Bytes
- 47 Pages / 439.36 x 666.15 pts Page_size
- 40 Downloads / 231 Views
Basic Concepts
This chapter introduces and summarizes basic concepts and terminology in probability theory and stochastic scheduling, which build the foundation to develop optimal policies for a wide range of scheduling problems in subsequent chapters. In Sect. 1.1, we summarize the fundamental theory of probability in a compact and concise way. Section 1.2 discusses several versions of stochastic orders for comparing random variables, which are essential for the optimality criteria in scheduling problems. Section 1.3 describes basic concepts of stochastic scheduling models, including job characteristics, machine environments, scheduling policies, performance measures and optimality criteria. The notation used throughout the book is summarized in Sect. 1.4.
1.1 Fundamental of Probability To deal with extensive uncertainty in stochastic scheduling, we apply the theory and methods of probability to quantify the level of uncertainty. This section introduces the basic concepts and fundamental theory of probability.
1.1.1 Probability Space Sample Space A set Ω that includes all elements of interest is referred to as a space. If Ω consists of all possible outcomes of an experiment with uncertain result, it is referred to as a sample space. Typical examples of sample space include Ω = {1, 2, 3, 4, 5, 6}
X. Cai et al., Optimal Stochastic Scheduling, International Series in Operations Research & Management Science 207, DOI 10.1007/978-1-4899-7405-1 1, © Springer Science+Business Media New York 2014
1
2
1 Basic Concepts
for tossing a die, and Ω = [0, ∞) for recording a random time. An element in Ω is denoted by ω , which represents a particular outcome if Ω is a sample space. A set Ω is said to be countable if its elements can be listed as a sequence:
Ω = { ω1 , ω2 , . . . } Otherwise Ω is uncountable. In particular, any finite set Ω is countable. Any interval [a, b] with a < b is uncountable. A sample space Ω is said to be discrete if it is countable; or continuous if it is an interval or a product of intervals, such as: • Ω = R = (−∞, ∞), Ω = [0, ∞), Ω = [0, 1], • Ω = Rn = {(x1 , . . . , xn ) : x1 , . . . , xn ∈ R}, Ω = [0, ∞)2 = {(x, y) : x, y ≥ 0}, or • Ω = [0, ∞) × [0, 1] = {(x, y) : x ≥ 0, 0 ≤ y ≤ 1}, etc.
σ -Algebra Given a space Ω , a collection F of subsets of Ω is said to be a σ -algebra or σ -field on Ω if it satisfies the following three axioms: (i) The empty set 0/ ∈ F ; (ii) If a subset E ∈ F , then its complement E c ∈ F ; (iii) If subsets Ei ∈ F , i = 1, 2, . . . , then
∞
Ei ∈ F .
i=1
These axioms imply: (iv) The sample space Ω ∈ F ; (v) If E ∈ F and F ∈ F , then E ∪ F ∈ F , E ∩ F ∈ F and E − F = E ∩ F c ∈ F ; (vi) If subsets Ei ∈ F , i = 1, 2, . . . , then
∞
Ei ∈ F .
i=1
In summary, a σ -algebra is a “self-contained” collection of subsets of Ω under countable set operations of unions, intersections and complements. Given a collection G of E ⊂ Ω , the smallest σ -algebra F such that G ⊂ F is called the σ -algebra generated by G and denoted by F = σ (G ). For example, the smallest σ -alg
Data Loading...
