Skip to content
Sem 5 Prep
← OperationsScheduling and sequencing

Formulas for this chapter

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
Step 3 of 21
The real wordsTheory

The performance metrics

Job flow timeThe time from when a job arrives until it is complete, including waiting as well as processing. In a single-centre problem it is the running total of processing times up to and including that job.
Job latenessThe amount by which completion is expected to exceed the promised due date. It can be negative when a job is early.
TardinessLateness with negatives set to zero: a job finished early is not "minus three days late".
MakespanThe total time to complete a group of jobs, from the start of the first to the completion of the last.
← BackContinue →