Забыли?

?

# On the Complexity of Scheduling

код для вставкиСкачать
```On the Complexity of Scheduling
Peter Brucker
University of Osnabrueck
Germany
1.Scheduling Problems
In a scheduling problem one has to find time slots
in which activities (or jobs) should be processed
under given constraints. The main constraints are
resource constraints and precedence constraints
between activities. A quite general scheduling
problem is the Resource Constrained Project
Scheduling Problem (RCPSP) which can be
formulated as follows:
The RCPSP
We have
вЂў Activities j = 1, ... , n with processing times pj.
вЂў Resources k = 1, ... , r. A constant amount of
Rk units of resource k is available at any time.
During processing, activity j occupies rjk units
of resource k for k = 1, ... , r.
вЂў Precedence constrains i п‚® j between some
activities i, j with the meaning that activity j
cannot start before i is finished..
The RCPSP
The objective is to determine starting times Sj
for all activities j in such a way that
вЂў at each time t the total demand for resource
k is not greater than the availability Rk for
k = 1, ... , r,
вЂў the given precedence constraints are
fulfilled, i. e. Si+ pi п‚Ј Sj if i п‚® j ,
The RCPSP
вЂў some objective function f( C1, ... , Cn) is
minimized where Cj = Sj + pj is the
completion time of activity j.
The fact that activities j start at time Sj and
finish at time Sj + pj implies that the activities
j are not preempted. We may relax this
condition by allowing preemption (activity
splitting).
The RCPSP
If preemption is not allowed the vector S = (Sj)
defines a schedule. S is called feasible if all
resource and precedence constraints are
fulfilled. One has to find a feasible schedule
which minimizes the objective function
f( C1, ... , Cn). In project planning f( C1, ... , Cn) is
often replaced by the makespan Cmax which is
the maximum of all Cj - values.
An Example
Consider a project with n = 4 activities, r = 2
resources with capacities R1 = 5 and R2 = 7, a
precedence relation 2 п‚® 3 and the following data:
An Example
2п‚®3
A corresponding schedule with minimal makespan
The RCPSP
вЂў The constraints Si + pi п‚Ј Sj may be replaced
by Si + dij п‚Ј Sj (positive and negative timelags).
вЂў With time-lags we may model release times
rj or deadlines dj .
вЂў We may have more than one objective
function (multi-criteria optimization).
вЂў There are other generalizations.
RCPSP with Multiple Modes
вЂў Associated with each activity j is a set Mj
of modes (processing alternatives).
вЂў The processing time pjm and per period
usage rjkm of resource k for activity j
depends on mode m.
вЂў One has to assign a mode to each activity
and to schedule the activities in the assigned
modes.
Applications
вЂў Production scheduling
вЂў Robotic cell
scheduling
вЂў Computer processor
scheduling
вЂў Timetabling
вЂў Personnel scheduling
вЂў Railway scheduling
вЂў Air traffic control
вЂў etc.
Assumptions
вЂў All data are assumed to be integers.
вЂў We consider only off-line scheduling
problems (on-line scheduling problems will
be discussed in another talk).
Next machine scheduling problems will be
discussed in detail.
2. Machine Scheduling Problems
and their Classification
вЂў Most machine scheduling problems are
special cases of the RCPSP.
Here we will consider
вЂў single machine problems,
вЂў parallel machine problems, and
вЂў shop scheduling problems.
Single machine problems
вЂў We have n jobs j =1, ... , n to be processed on
a single machine. Additionally precedence
constraints between the jobs may be given.
вЂў This problem can be modeled by an RCPSP
with r = 1, R1 = 1, and rj1 = 1 for all jobs j.
Parallel Machine Problems
вЂў We have jobs j as before and m identical
machines M1, ... , Mm . The processing time
for j is the same on each machine. One has
to assign the jobs to the machines and to
schedule them on the assigned machines.
вЂў This problem corresponds to an RCPSP
with r = 1, R1 = m, and rj1 = 1 for all jobs j.
Parallel Machine Problems
Parallel Machine Problems
вЂў For unrelated machines the processing
time pjk depends on the machine Mk on
which j is processed.
вЂў The machines are called uniform if
pjk = pj/rk.
вЂў In a problem with multi-purpose machines
a set of machines mj is is associated with
each job j indicating that j can be processed
on one machine in mj only.
Shop Scheduling Problems
вЂў In a general shop scheduling problem we have
m machines M1, ... , Mm and n jobs j = 1, ... , n.
вЂў Job j consists of n(j) operations O1j, O2j, ... , On(j)j
where Oij must be processed for pij time units on a
dedicated machine mij пѓЋ {M1, ... , Mm }.
вЂў Two operations of the same job cannot be
processed at the same time. Precedence constraints
are given between the operations.
Shop Scheduling Problems
To model the general shop scheduling problem as
RCPSP we consider
вЂў r = n + m resources k = 1, ..., n + m with Rk = 1 for
all k. While resources k = 1, ... , m correspond to the
machines, resources m + j (j = 1, ... , n) are needed
to model that different operations of the same job
cannot be scheduled at the same time.
вЂў n(1) + n(2) + ... + n(n) activities Oij where operation
Oij needs one unit of вЂњmachine resourceвЂќ mij and
one unit of the вЂњjob resourceвЂќ m + j.
Shop Scheduling Problems
вЂў A job-shop problem is a general shop
scheduling problem with chain precedence
constraints of the form O1j п‚® O2j п‚® ... п‚® On(j)j.
вЂў A flow-shop problem is a special job-shop
problem with n(j) = m operations for j = 1, ..., n
and mij = Mi for i = 1, ..., m and j = 1, ..., n .
Shop Scheduling Problems
вЂў In a permutation flow-shop problem the
jobs have to be processed in the same order
on all machines.
Shop Scheduling Problems
вЂў An open-shop problem is like a flow-shop
problem but without precedence constraints
between the operations.
Classification of Scheduling
Problems
Classes of scheduling problems can be specified
in terms of the three-field classification a | b | g
where
п‚• a specifies the machine environment,
п‚• b specifies the job characteristics, and
п‚• g describes the objective function(s).
Machine Environment
To describe the machine environment the following
symbols are used:
вЂў 1 single machine
вЂў P parallel identical
machines
вЂў Q uniform machines
вЂў R unrelated machines
вЂў MPM multipurpose
machines
вЂў J job-shop
вЂў F flow-shop
вЂў O open-shop
The above symbols are used if the number of machines is
part of the input. If the number of machines is fixed to m
we write Pm, Qm, Rm, MPMm, Jm, Fm, Om.
Job Characteristics
вЂў
вЂў
вЂў
вЂў
pmtn preemption
rj release times
dj deadlines
pj = 1 or pj = p or
pj пѓЋ {1,2} restricted
processing times
вЂў prec
arbitrary
precedence constraints
вЂў intree (outtree) intree
(or outtree) precedences
вЂў chains chain precedences
вЂў series-parallel a seriesparallel precedence graph
Objective Functions
Two types of objective functions are most
common:
вЂў bottleneck objective functions
max {fj(Cj) | j= 1, ... , n}, and
вЂў sum objective functions S fj(Cj) = f1(C1) +
f2(C2) + ... ... + fn(Cn) .
Objective Functions
Cmax and Lmax symbolize the bottleneck
objective functions with fj(Cj) = Cj
(makespan) and fj(Cj) = Cj - dj (maximum
lateness), respectively.
Common sum objective functions are:
п‚• S Cj (mean flow-time) and S wj Cj
(weighted flow-time)
Objective Functions
п‚• S Uj (number of late jobs) and S wj Uj
(weighted number of late jobs) where Uj = 1
if Cj > dj and Uj = 0 otherwise.
п‚• S Tj (sum of tardiness) and S wj Tj
(weighted sum of tardiness) where the
tardiness of job j is given by
Tj = max { 0, Cj - dj }.
Examples
вЂў
вЂў
вЂў
вЂў
вЂў
вЂў
вЂў
1 | prec; pj = 1 | S wj Cj
P2 | | Cmax
P | pj = 1; rj | S wj Uj
R2 | chains; pmtn | Cmax
J3 | n = 3 | Cmax
F | pij = 1; outtree; rj | S Cj
Om | | pj = 1 | S Tj
3. Complexity Theory
3.1 Polynomial algorithms
3.2 Classes P and NP
3.3 NP- complete and NP- hard problems
3.1 Polynomial algorithms
вЂў An algorithm h transforms an input x into an
output h(x). h(x) is the answer for a
corresponding problem solved by the algorithm.
вЂў |x| denotes the length of input x with respect to
some binary encoding.
вЂў An algorithm is called polynomial if h(x) can be
computed in at most O(p(|x| ) step where p is a
polynomial.
3.1 Polynomial algorithms
вЂў A problem is called polynomially solvable if
it can be solved by a polynomial algorithm.
Example
1 | | S wjCj can be solved by scheduling the jobs
in an ordering of non-increasing wj/pj - values.
Complexity: O(n log n)
3.1 Polynomial algorithms
вЂў If we replace the binary encoding by an
unary encoding we get the concept of a
pseudo-polynomial algorithm.
Example
An algorithm for a scheduling problem with
computational effort O(S pj) is pseudopolynomial.
3.2 Classes P and NP
вЂў A problem is called a decision problem if
the output range is {yes, no}.
вЂў We may associate with each scheduling
problem a decision problem by defining a
threshold k for the objective function f. The
decision problem is: Does a feasible
schedule S exist satisfying f(S) п‚Ј k?
вЂў P is the class of decision problems which
are polynomially solvable.
3.2 Classes P and NP
вЂў NP is the class of decision problems with
the property that for each вЂњyesвЂќ-answer a
certificate exists which can be used to verify
the вЂњyesвЂќ-answer in polynomial time.
вЂў Decision versions of scheduling problems
belong to NP (a вЂњyesвЂќ-answer is certified by
a feasible schedule S with f(S) п‚Ј k).
вЂў P пѓЌ NP holds. It is open whether P = NP.
3.3 NP- complete and NP- hard
problems
вЂў For two decision problems P and Q, we say
that P reduces to Q (denoted by P a Q) if
there exists a polynomial-time computable
function g that transforms inputs for P into
inputs for Q such that x is a вЂњyesвЂќ-input for P
if and only if g(x) is a вЂњyesвЂќ-input for Q.
3.3 NP- complete and NP- hard
problems
Properties of polynomial reductions:
вЂў Let P, Q be decision problems. If P a Q then
Q пѓЋ P implies P пѓЋ P (and, equivalently,
P
пѓЏ P implies Q пѓЏ P) .
вЂў Let P, Q, R be decision problems. If P a Q
and Q a R, then P a R.
3.3 NP- complete and NP- hard
problems
вЂў A decision problem Q is called NP - complete
if Q пѓЋ NP and, for all other decision problems
P пѓЋ NP, we have P a Q.
If any single NP- complete decision problem Q
could be solved in polynomial time then we
would have P = NP.
3.3 NP- complete and NP- hard
problems
To prove that a decision problem P is NP complete it is sufficient to prove the
following two properties:
вЂў P пѓЋ NP, and
вЂў there exist an NP- complete problem Q with
Q a P.
3.3 NP- complete and NP- hard
problems
An optimization problem is NP- hard if its
decision version is NP- complete.
3.3 NP- complete and NP- hard
problems
Cook [1971] has shown that the satisfiability
problem from Boolean logic is NP- complete.
Using this result he used reduction to prove
that other combinatorial problems are NPcomplete as well.
In a follow-up paper Karp [1972] derived NPcompleteness results for many other problems.
4. Complexity of machine
scheduling problems
Complexity results for different classes of
scheduling problems can be found under
http://www.mathematik.uniosnabrueck.de/research/OR/class/
These results are based on
вЂў results found in the literature, and
вЂў elementary reductions between scheduling
problems.
4. Complexity of machine
scheduling problems
In these web-pages for several classes of machine
scheduling problems the following results are
listed:
вЂў the hardest problems which are known to be
polynomially solvable,
вЂў the easiest problems which are known to be NP hard,
вЂў the hardest and easiest problems which are open.
Elementary reductions
Hereby the following elementary reductions
are used
Elementary reductions
Elementary reductions
Elementary reductions
For single machine problems we have more
specific elementary reductions.
Polynomially solvable single machine
problems
NP - hard single machine scheduling
problems
Minimal and maximal open problems
Polynomially solvable parallel machine
problems without preemption
Polynomially solvable parallel machine
problems without preemption
Polynomially solvable parallel machine
problems without preemption
NP- hard parallel machine problems
without preemption
NP- hard parallel machine problems
without preemption
Minimal and maximal open problems
5. How to Live with NP - hard
Scheduling Problems?
Small sized problems can be solved by
вЂў Mixed integer linear programming
вЂў Dynamic programming
вЂў Branch and bound methods
To solve problems of larger size one has to
apply
вЂў Approximation algorithms
вЂў Heuristics
6. Other Types of Scheduling
Problems
There are other classes of scheduling problems.
Some of them are discussed in this book.
вЂў Due-date scheduling
вЂў Batching problems
вЂў Multiprocessor task
scheduling
вЂў Cyclic scheduling
вЂў Scheduling with
controllable data
вЂў
вЂў
вЂў
вЂў
вЂў
Shop problems with buffers
Inverse scheduling
No-idle time scheduling
Multi-criteria scheduling
Scheduling with noavailable constraints
6. Other Types of Scheduling
Problems
Scheduling problems are also discussed in
connection with other areas:
вЂў Scheduling and transportation
вЂў Scheduling and game theory
вЂў Scheduling and location problems
вЂў Scheduling and supply chains
References
P. Brucker (2007), Scheduling Algorithms,
fifth edition, Springer, Heidelberg
M.R. Garey, D.S. Johnson (1979), Computers
and Intractability: A Guide to the Theory of
NP-Completeness, W.H. Freeman and
Company, San Francisco.
http://www.mathematik.uniosnabrueck.de/research/OR/class/
```
###### Документ
Категория
Презентации
Просмотров
11
Размер файла
843 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа