Flow time, lateness and tardiness
Flow time (single centre) = running total of processing times
Lateness = Flow time - Due date (can be negative)
Tardiness = max(0, Lateness)
Every single-work-centre sequencing table. Set negative lateness to zero before averaging.
- Flow time
- Arrival to completion, including waiting
- Due date
- Days from now, as the question states it
The three averages
Average flow time = SUM flow times / n
Average tardiness = SUM days late / n
Average number of jobs = SUM flow times / SUM processing times
Comparing two priority rules. The third is a work-in-process measure and its denominator never changes with the sequence.
- n
- Number of jobs
- SUM processing times
- Also the makespan at a single work centre
Critical ratio
CR = (Due date - Current time) / Processing time
Smallest CR goes next. Recompute for every remaining job after each completion; below 1 means the job cannot make its date.
- Current time
- The clock now, which advances as jobs finish
- Processing time
- Work remaining on that job
Johnson's rule
1. List job times at both work centres
2. Find the shortest time anywhere
- at centre 1: schedule that job FIRST
- at centre 2: schedule that job LAST
3. Remove the job
4. Repeat, working towards the centre
Two work centres, same two-step route for every job. Minimises makespan and total idle time.
- shortest time
- The single smallest number remaining in the whole table
- ties
- Broken arbitrarily
Two-centre Gantt timing
Start at centre 2 = max( finish at centre 1, centre 2 becomes free )
Makespan = finish of the last job at centre 2
Idle at centre 2 = initial wait + sum of internal gaps
Reading makespan and idle time off a two-row chart after applying Johnson's rule.
- initial wait
- Time before the first job reaches centre 2
- internal gaps
- Periods when centre 2 is free but no job has arrived