Nikola KNEŽEVIĆ, PhD Faculty of Transport and Traffic Engineering ...

Description

Nikola KNEŽEVIĆ, PhD Faculty of Transport and Traffic Engineering, University of Belgrade, Serbia Nikola TRUBINT, PhD Republic Agency for Postal Services, Belgrade, Serbia Dragana MACURA1 Faculty of Transport and Traffic Engineering University of Belgrade, Serbia E-mail: Nebojša BOJOVIĆ, PhD Faculty of Transport and Traffic Engineering, University of Belgrade, Serbia A TWO-LEVEL APPROACH FOR HUMAN RESOURCE PLANNING TOWARDS ORGANIZATIONAL EFFICIENCY OF A POSTAL DISTRIBUTION SYSTEM Abstract: Optimal human resources management, optimization of the required number of workers in specific technological operation phases, represents one of the most important management tasks in postal systems

• universal service segment
• initial list of factors for the examination
• distributive system units
• postal services
• efficiency
• regression analysis
• business activities
• factors
• -1 unit
• unit

Sujets

• Kne?evi?
• University of Belgrade
• Taïwan
• Belgrade
• Delphi
• Southern
• Spain

Informations

• Publié par: phawyir
• Nombre de lectures: 17
• Langue: English

Extrait

ELE539A: Optimization of Communication Systems
Lecture 3B: Network Flow Problems
Professor M. Chiang
Electrical Engineering Department, Princeton University
February 12, 2007Lecture Outline
• Network flow problems
• Problem 1: Maximum flow problem
• Ford Fulkerson algorithm
• Problem 2: Shortest path routing
• Bellman Ford algorithm
• Simple IP routing: RIP
• Dynamic ProgrammingGraph Theory Notation
G = (V,E): directed graph with vertex set V and edge set E
b : external supply to each node i∈V
i
u : capacity of each edge (i,j)∈E
ij
c : cost per unit flow on edge (i,j)∈E
ij
I(i) ={j ∈V|(j,i)∈E}: set of start nodes of incoming edges to i
O(i)={j ∈V|(i,j)∈E}: set of end nodes of outgoing edges from i
Sources: {i|b > 0}. Sinks: {i|b < 0}
i i
Feasible flow f:
P P
• Flow conservation: b + f = f , ∀i∈V
i ji ij
j∈I(i) j∈O(i)
• Capacity constraint: 0≤f ≤u
ij ijBasic Formulation
Network flow problem:
P
minimize c f
ij ij
(i,j)∈E
P P
subject to b + f = f , ∀i∈V
i ji ij
j∈I(i) j∈O(i)
0≤f ≤u
ij ij
In matrix notation as a LP:
T
minimize c f
subject to Af =b
0f u
|V|×|E|
where A∈R is defined as
8
>
1, i is the start node of edge k
<
A =
−1, i is the end node of edge k
ik
>
:
0, otherwiseSpecial Cases
• Maximum flow problem (this lecture)
• Shortest path problem (this lecture)
• Transportation problem (uncapacitated bipartite graph)
P
minimize c f
ij ij
i,j
P
m
subject to f =d , j = 1,...,n
ij j
i=1
P
n
f =s , i = 1,...,m
ij i
j=1
f ≥ 0, i = 1,...,m,j = 1,...,n
ij
Variables f . Constants d ,s ,c
ij j i ij
• Assignment problem (homework):
m =n,d =s = 1 in transportation problem
j i6
Maximum Flow Problem
maximize b
s
subject to Af =b
b =−b
t s
b = 0, ∀i =s,t
i
0≤f ≤u
ij ij
Reformulated as network flow problem:
• Costs for all edges are zero
• Introduce a new edge (t,s) with infinite capacity and cost −1
• Minimize total cost is equivalent to maximize f
tsFord Fulkerson Algorithm
1. Start with feasible flow f
2. Search for an augmenting path P
3. Terminate if no augmenting path
4. Otherwise, if flow can be pushed, push δ(P) units of flow along P
and repeat Step 2
5. Otherwise, terminate
Q: How to find augmenting path?
Q: How much flow can be pushed?Augmenting Path
Idea: find a path where we can increase flow along every forward edge
and decrease flow along backward edge by the same amount. Still
satisfy constraints. Increase objective function
Augmenting path: a path from s to t such that f <u on forward
ij ij
edges and f > 0 on backward edges
ij
Augmenting flow amount along augmenting path P:
 ff
δ(P)= min min (u −f ), min f
ij ij ij
(i,j)∈F (i,j)∈B
Can search for augmenting path by following possible paths leading
from s and checking conditions aboveExample
12
4/12
a b a b
16
20
20
4/16
9
4
4/9
10 4
s 7 t s 10
7
13
13
4/4
4
c d c d
14 4/14
8
4/12
a b a b
4
7/20
20
11/16
12
4
4 4
4 4/9
s t s 7/10
7/7
10 7
5
13 13
4
4/4
10 11/14
c d c d
4Example
8
12/12
a b a b
4
15/20
13
5
11/16
7
11
1/4
11 5
4
s t s
3 10 4/9
7/7
7
13 4
8/13
4/4
11/14
3
c d c d
11
12 12/12
a b a b
5 19/20
5 15
11/16
11 3 1/4
4 9
s t s
11 7 10
7/7
5 5
4
8 12/13
4/4
3 11/14
c d c d
11