Забыли?

?

Flow shop Scheduling Problems with Transportation and

код для вставкиСкачать
```Flow shop Scheduling Problems
with Transportation and
Capacities Constraints
Oulamara, A.; Soukhal, A.
2001 IEEE SMC Conference
Speaker: Chan-Lon Wang
Scheduling Classification
1. Open-shop scheduling
пѓ� Each job visit each machine again
пѓ� Different jobs have different routes
пѓ� Processing time of job maybe is zero
Open-shop scheduling
вЂў Example: Job: J1, J2, J3, J4
Machine: M1, M2, M3
J1
M1
M2
M3
OUT
J2
M1
M2
M3
OUT
J3
M3
M2
M1
OUT
J4
M2
M1
M3
OUT
Job-shop scheduling
пѓ�Each job visit each machine at most once
пѓ�Each job has own routing
J1
M1
M2
M3
OUT
J2
M1
M2
M3
OUT
J3
M3
M2
M1
OUT
J4
M2
M1
M3
OUT
Flow-shop scheduling
пѓ�Jobs are not preemptive
пѓ�Each job has m tasks with processing time
пѓ�Each job follow a same route
J1
M1
M2
M3
OUT
J2
M1
M2
M3
OUT
J3
M1
M2
M3
OUT
J4
M1
M2
M3
OUT
Scheduling Classification
Simple open shop scheduling
Open shop
Flexible open shop scheduling
Simple Job shop scheduling
Scheduling
Job shop
Flexible Job shop scheduling
Simple Flow shop scheduling
Flow shop
Flexible Flow shop scheduling
Simple Flow Shop Problem
Each machine center has one machine
Ex: A car painting factory
Car-1
(5, 3)
Car-2
P1
(4, 4)
Center 1
painting
degreasing
P2
5
9
Center 2
8
13
The final completion time=13
Flexible Flow-Shop Problem
At least one machine center has more than one machine
Ex: two same machines in each center
Car-1
(5, 3)
Car-2
painting
degreasing
P1
(4, 4)
P2
5
Center 1
Center 2
4
8
8
The final completion time=8
Problem Description-1
Graham et al.:
пЃЎ|пЃў|пЃ§
F2пѓ D|v=1, c=2|Cmax F2:two machines, D:truck,
v: one truck, c=capacity of truck, Cmax=min makespan
Problem Description-2
вЂў The classical problem:
вЂ“ Unlimited intermediate buffer capacity
вЂ“ Infinite speed vehicles
вЂў Constraints:
вЂ“ Transportation capacity
вЂ“ Transportation time
Problem Description-3
вЂў F2пѓ D|v=1, c=1, no wait |Cmax пѓЁF3пѓ D| no wait |Cmax
вЂў If the truck consider as a machine.
Flow-shop with capacity of truck
limited to parts
вЂў Flow-shop with unlimited buffer space
вЂ“ F2пѓ D|v=1, c=2|Cmax is NP-hard
вЂў Flow-shop with limited buffer space at the
output system
вЂ“ F2пѓ D|v=1, c=2, blacking(1, 2)|Cmax is NP-hard
Resolution methods
вЂў
Four greedy algorithms for solving
вЂ“
вЂ“
вЂў
вЂў
вЂў
вЂў
F2пѓ D|v=1, c=2|Cmax and
F2пѓ D|v=1, c=2, blacking(1, 2)|Cmax
L1: no wait + no-decreasing job sequence
L2: no wait + no-increasing job sequence
L3: unlimited buffer space + JohnsonвЂ™s order
L4: no wait + Gilmore & GomoryвЂ™s order
L1: no wait + no-decreasing job sequence
вЂўNo wait regard as no buffer between machine.
вЂўNo decreasing regard as ascending.
вЂўEx: Job order: car2, car4, car1, car3, car5. For machine-1.
Car-1
4
3
Car-2
1
2
Car-3
5
4
Car-4
2
3
Car-5
5
6
L2: no wait + no-increasing job sequence
вЂўNo wait regard as no buffer between machine.
вЂўNo increasing regard as descending.
вЂўEx: Job order: car3, car5, car1, car4, car2.
Car-1
4
3
Car-2
1
2
Car-3
5
4
Car-4
2
3
Car-5
5
6
L3: Unlimited buffer space + JohnsonвЂ™s order
вЂўUnlimited buffer space regard as no buffer between machine.
вЂўJohnsonвЂ™s order is optimal.
Review of Johnson Algorithm
For two machines flow shop
Input:
пѓ� A set of n independent jobs
Output:
пѓ� A schedule
пѓ� A nearly minimum completion time of the last job
Review of Johnson Algorithm
Ex: A car painting factory
Car-1
Sum
4
3
7
Car-2
1
2
3
Car-3
5
4
9
Car-4
2
3
5
Car-5
5
6
11
U= {t1i< t2i}= {Car-2, Car-4, Car-5} =>ascending by Sum
V={t1j>=t2j}= {Car-1, Car-3} =>descending by Sum
The sequence
{U, V} = {
={Car-2, car-4, car-5, car-3, car-1}
Makespan=21
}
The Johnson Final Scheduling
P1=17
P2=21
The final completion time = 21
Problem with unlimited buffer
No buffer area between machines
Conclusions
вЂў With unlimited buffer between machines the
problem is NP-hard
вЂў With no buffer between machines the
problem is NP-hard
```
Документ
Категория
Презентации
Просмотров
16
Размер файла
240 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа