Scheduling and sequencing

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