Transcript Stochastic Model--Preliminaries

IOE/MFG 543
Chapter 9:
Stochastic Models - Preliminaries
1
Uncertainty


In practice, processing times, release
dates, etc., are not known exactly
Uncertainty can be caused by
– weather
– machine breakdown
– operator skills
– unknown demand, order size
–…
2
Incorporating uncertainty
into scheduling models



Model processing times, release dates, etc.,
as random variables
Notation
Xij
=
Rj
Dj
=
=
random processing time of job j on
machine i
random release date of job j
random due date of job j
Lower case letters denote realized values
e.g., xij is the actual processing time of job j on
machine i and is only known after it has been
processed

1/lij = expected value of Xij
3
Probability review


We only need to consider nonnegative
random variables
Continuous nonnegative random
variable X
– Density function f(t)
t
– Distribution function F(t)=P(X≤t)=∫0 f(s)ds

F(0)=0 and limt∞F(t)=1
– Also define F(t)=1-F(t)=P(X>t)
Note: There is a typo in Figure 9.1. The y-axis on the second graph
should be F(t)
4
Probability review (2)

Discrete random variable X
– Mass function p(t)=P(X=t)

Moments
∞
– X continuous: E(Xr)= ∫0 sr f(s) ds
–
–
–
–
r
∞
)=Ss=0 sr
X discrete:
E(X
p(s)
The mean E(X) is the first moment
The variance is Var(X)=E(X2)-(E(X))2
Coefficient of variation
Cv(X)=(√Var(X))/E(X)
5
Completion rate

The completion rate of a job at time t
– X continuous:
– X discrete:

c(t)=f(t) / F(t)
c(t)=p(t) / P(X≥t)
Exponential random variable
(continuous)
– f(t)=le-lt and F(t)=1-e-lt => c(t)=l

Geometric random variable (discrete)
– p(t)=(1-q)qt and P(X≥t)=qt => c(t)=1-q
6
Classifying processing
times according to c(t)

We can classify the random variable X as
having
– increasing completion rate (ICR)

c(t) is increasing in t
– decreasing completion rate (DCR)



c(t) is decreasing in t
The exponential and geometric have a
constant c(t) so are both ICR and DCR
Some random variables are neither ICR nor
DCR
7
Comparing random
variables



How can we compare two random
processing times X1 and X2?
Perhaps base the first order of
comparison on the mean
If the means are equal then look at
the variance
8
Stochastic dominance
based on expectation
X1 is larger in expectation than X2 if
E(X1)≥E(X2)
ii. X1 is stochastically larger in than X2 if
P(X1>t)≥P(X2>t)
and is denoted by X1≥st X2
i.
9
Stochastic dominance
based on expectation (2)
iii. X1 is larger in the likelihood ratio sense
than X2 if the likelihood ratio
X1 and X2 continuous: f1(t)/f2(t)
X1 and X2 discrete:
p1(t)/p2(t)
is nondecreasing
This is denoted by X1≥lr X2
iv. X1 is almost surely larger than X2 if
P(X1≥ X2)=1
and is denoted by X1≥as X2
 Note that iv  iii  ii  i
10
Stochastic dominance
based on variance
i.
ii.
X1 is larger in the variance sense than X2 if
Var(X1)≥Var(X2)
X1 is more variable than X2 if
X1 and X2 continuous:
∞
∞
∫0 h(t) dF1(t) ≥ ∫0 h(t) dF2(t)
X1 and X2 discrete:
∞
S∞
t=0 h(t) p1(t) ≥ St=0 h(t) p2(t)
for all convex functions h(t)
This is denoted by X1≥cx X2
11
Stochastic dominance
based on variance (2)
iii. X1 is symmetrically more variable than X2
if f1(t) and f2(t) are symmetric about the
same mean 1/l and
F1(t)≥F2(t) for t ≤ 1/l and
F1(t)≤F2(t) for t ≥ 1/l


The above variability orderings are based
on the assumption that E(X1)=E(X2)
Note that iii  ii  i
12
Increasing convex
ordering
Continuous case

–
Discrete case

–

X1 is larger than X2 in the increasing convex
sense if
∞
∞
∫0 h(t) dF1(t) ≥ ∫0 h(t) dF2(t)
for all increasing convex functions h(t)
X1 is larger than X2 in the increasing convex
sense if
∞ h(t) p (t) ≥ S ∞ h(t) p (t)
St=0
1
t=0
2
for all increasing convex functions h(t)
This is denoted by X1≥icx X2
13
Lemma 9.4.2

Let
Z(1)=g(X1(1),X2(1),…,Xn(1)) and
Z(2)=g(X1(2),X2(2),…,Xn(2))
where g is increasing convex in each argument



If X1(j)≥icx X2(j) for all j then Z(1)≥icxZ(2)
Example 9.4.3
Example 9.4.4
14
Lemma 9.4.5

If F1 is deterministic, F2 is ICR, F3 is
exponential and F4 is DCR then
F1 ≤cx F2 ≤cx F3≤cx F4

We can use this result to get bounds
on performance measures
– Example 9.4.6
15
Classes of policies


When scheduling under uncertainty
new information becomes available as
the jobs are processed, e.g., the
processing times of the completed
jobs are known
Instead of a fixed schedule it may be
better to develop a policy which
prescribes what job to schedule next
16
Static list policies

Nonpreemptive static list policy
– The decision maker orders the jobs at time zero
according to a priority list. This priority list does
not change during the evolution of the process,
and every time a machine is freed the next job
on the list selected for processing

Preemptive static list policy
– The decision maker orders the jobs at time zero
according to a priority list. This list includes jobs
with nonzero release dates. This list does not
change during the evolution of the process, and
at any point in time the job at the top of the list
of available jobs is selected for processing
17
Dynamic policies

Nonpreemptive dynamic policy
– Whenever a machine is freed the decision maker
chooses which job goes next. The decision may
depend on all the information available at that
time (e.g., jobs waiting for processing, jobs
being processed on other machines and the
amount of processing they have had)

Preemptive dynamic policy
– At any point in time the decision maker chooses
which job should be processed on the machine.
The decision may depend on all the information
available at that time and may require
preemptions
18