### Present Remotely

Send the link below via email or IM

• Invited audience members will follow you as you navigate and present
• People invited to a presentation do not need a Prezi account
• This link expires 10 minutes after you close the presentation

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

# TADC - PF2 - No Waiting -

Presentation on TADC (Total absolute deviation of completion times) measurement given by Yoav Ben-Yehoshua and Eyal Hariri.
by

## yoav ben

on 4 January 2015

Report abuse

#### Transcript of TADC - PF2 - No Waiting -

Introduction
Agenda
Introduction
Other Indices
Completion time variance (1972):
Example
Two Machine Proportional Flow-Shop With No-Waiting
Positional Weights
Applications:
To provide customers with an identical or similar quality of service
Objective:
Product delivery
Computers
Restaurants
Waiting time variance (1975):
Both was proved to be NP-Hard for even a single machine by Kubiak (1993)
Other Indices
Other Indices
Total \ Maximum deviations of compleation times from common due date:
Have been extensively studied but was also proved to be NP-hard for a restrictive due date (1991).
Intoduced and proved it can be solved in a polynomial time by Kanet (1981)
Extensions
Other Indices
Finding the optimal solution
2 jobs
Other Indices
Further Discussion
Let's minimize TADC on single machine of the jobs:
Thank You
OPERATIONS RESEARCH AND
OPERATIONS MANAGEMENT
SEMINAR
Yoav Ben-Yehoshua
Eyal Hariri
F
F /No-Wait, P = P /TADC
i,j
i
2
2
:
Two machines flow-shop
No Wait :
After a job finished running on the first machine it must start running on the second.
P = P :
Processing time is machine independent.
i,j
i
Lemma
An optimal schedule exists such that the largest job is scheduled first.
Trivial since we know the longest job must be first and therfore the shortest job must be second
LPT (Longest job first) always gets optimal solution
3 jobs
Since we know that longest job must be first we only need to check two scheduling besides LPT
LPT (Longest job first) always gets optimal solution
4 jobs
Since we know that longest job must be first we only need to check two scheduling besides LPT
LPT (Longest job first) always gets optimal solution
5-6-7 jobs
The same follows for 5 6 and 7 jobs
LPT (Longest job first) always gets optimal solution
8 jobs
When the instance contains 8 jobs, it can be shown that LPT is not necessarily optimal. We found 430 equations that can be positive meaning that LPT is not always optimal.
For example:
Example
[1,2,3] (LPT):
[1,3,2]:
9 jobs
We found 4000+ equations
that might be positive for 9 jobs
8 and 9 jobs optimal solution
For 8 jobs we found out that the optimal soltion is either LPT or [1,2,3,5,6,7,8,4]
For 9 jobs we found out that the optimal soltion is either LPT or [1,2,3,5,6,7,8,9,4]
P1=9, P2=8, P3=7, P4=6,P5= 5,P6= 2,P7= 1,P8= 1.