close

Вход

Забыли?

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

?

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
пѓ� Each with m tasks
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
Документ
Категория
Презентации
Просмотров
15
Размер файла
240 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа