close

Вход

Забыли?

вход по аккаунту

?

Презентация

код для вставкиСкачать
A Modification of Dynamic
Programming Algorithms to Reduce
the Running Time or/and Time
Complexity
Evgeny R. Gafarov, Alexander A. Lazarev
Institute of Control Sciences of the Russian Academy of Sciences
Moscow, Russia
Frank Werner
Otto-von-Guericke-University
Magdeburg, Germany
1
Outline of the Talk
1. Dynamic Programming and Graphical
Algorithms
2. A Polynomial Algorithm for Problem
1 (nd) | | max ∑ Tj
3. A Numerical Example
4. An Overview of Graphical Algorithms for
Single Machine Problems
2
1. Dynamic Programming and Graphical Algorithms
Dynamic Programming (Bellman 1957)
Idea of the graphical algorithm:
Combine several states into a new state
3
Computations in a dynamic programming algorithm
Computations in a graphical algorithm
4
2 . A Polynomial Algorithm for Problem 1 (nd) | | max
∑ Tj
single machine
n jobs
pj processing time
j = 1,2,…,n
dj due date
no idle times, a schedule starts at time 0
maximization of total tardiness ∑ Tj
5
Lemma 1: There exists an optimal schedule
ПЂ = (G, H),
where all jobs in G are on-time and all jobs from H
are tardy. All jobs from set G are processed in SPT
order and all jobs from set H are processed in LPT order.
Notations:
πl(t) – best schedule of jobs 1,2,…,l starting at time t
Fl(t) – corresponding total tardiness
6
7
8
9
10
11
12
Theorem 1: The graphical algorithm constructs
an optimal schedule for problem
1 (nd) | | max ∑ Tj in O(n2) time.
3. A Numerical Example
n=4
13
14
15
16
17
18
4. An Overview of Graphical Algorithms for
Single Machine Problems
19
Two Announcements
1. New Book is ready:
Sotskov, Sotskova, Lai, Werner: Scheduling under Uncertainty:
Theorems and Algorithms, Belarusian Science, Minsk, 326 p., July 2010
(ISBN 978-985-08-1173-8)
- free download of a pdf from
http://www.math.uni-magdeburg.de/~werner/sot-sot-lai-werner.pdf
- paperback book at production cost available
2. LiSA – Version 3.0 with documentation is ready:
Andresen, Bräsel, Engelhardt, Werner: LiSA – A Library of Scheduling
Algorithms, Handbook for Version 3.0, 107 pages,
TR 10-05, August 2010.
Документ
Категория
Презентации
Просмотров
16
Размер файла
876 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа