Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • 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
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

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

DeleteCancel

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

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of TADC - PF2 - No Waiting -

Introduction
TADC with no-wait proportional flowshop
Agenda
TADC
Introduction
Other Indices
TADC
Extensions to TADC
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).
TADC
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.
We get that TADC(LPT)=359 and TADC(1,2,3,5,6,7,8,4)=351
Further Discussion
Full transcript