CMA Intermediate · Operations Management and Strategic Management

Scheduling and Queuing Models: formula sheet

Full chapter guide

Key formulas

Forward scheduling: Completion date = Start date + Sum of operation times (including waiting and move times); Gives the earliest possible completion. Use when materials or capacity are the limit.
Backward scheduling: Latest start date = Due date − Sum of operation times (including waiting and move times); Gives the latest date you can start without being late. Use when a due date is fixed.
Slack in a schedule: Slack = Latest start date − Earliest start date; Positive slack means you can still meet the due date. Negative means the job will be late.
Completion time: Completion time of a job = Completion time of previous job + Its processing time; For jobs all available at time 0 and a single machine with no idle time. Add up in the chosen sequence.
Flow time: Flow time = Completion time − Arrival (release) time; If all jobs are ready at time 0, flow time = completion time.
Average flow time: Average flow time = Σ Flow times ÷ Number of jobs; SPT minimises this on a single machine when all jobs are available together.
Lateness and tardiness: Lateness = Completion time − Due date; Tardiness = max(0, Lateness); Average tardiness = Σ Tardiness ÷ Number of jobs. EDD minimises maximum tardiness.
Critical ratio: CR = (Due date − Today's date) ÷ Remaining processing time; Use the same time unit for both. Lowest CR goes first. CR < 1 means behind schedule, CR = 1 on schedule, CR > 1 ahead. A negative CR means the job is already past its due date.
Average number of jobs in system: Average jobs in system = Σ Flow times ÷ Total time to finish all jobs; Total time is the completion time of the last job (the makespan).
Johnson's rule (two machines): Smallest time on M1 → place job at the earliest free position; smallest time on M2 → place job at the latest free position; Remove the placed job and repeat until all jobs are placed. Ties can be broken arbitrarily, so more than one optimal sequence may exist.
Condition for three machines: Min (M1 times) ≥ Max (M2 times), or Min (M3 times) ≥ Max (M2 times); At least one condition must hold. If neither holds, this method is not valid and you should say so.
Fictitious machines: G = M1 + M2 and H = M2 + M3 for each job; Apply Johnson's rule to G and H as if they were two machines. Then compute actual times on all three real machines.
Total elapsed time: Finish time of the last job on the last machine; Find it from the in-out table, not from the G and H columns.
Idle time on a machine: Total elapsed time − Sum of processing times on that machine; Valid when you count idle time from time zero to the end of the whole schedule. State the period you use.
Utilisation of a work centre: Utilisation = Hours actually loaded ÷ Hours available × 100; Read the loaded hours from the load chart. A value above 100% means the centre is overloaded.
Idle time on a load chart: Idle time = Available hours − Loaded hours; Shows spare capacity that can take more jobs.
Assignment problem condition: Number of jobs = Number of centres (square cost matrix); If not equal, add dummy rows or columns with zero cost.
Hungarian reduction: Row reduction, then column reduction, then cover zeros with minimum lines; optimal when lines = n; For maximisation, convert by subtracting every value from the largest value, then minimise.
Average service time: Mean service time = 1 ÷ μ; μ is the service rate per unit time. If μ = 6 per hour, mean service time = 10 minutes.
Average inter-arrival time: Mean time between arrivals = 1 ÷ λ; λ is the arrival rate per unit time. Keep λ and μ in the same time unit.
Traffic intensity (utilisation) for one server: ρ = λ ÷ μ; For a single-server model, a steady state exists only if ρ < 1. If λ ≥ μ, the queue grows without limit.
Traffic intensity for s servers: ρ = λ ÷ (s × μ); A steady state requires ρ < 1 here too.
Kendall notation: A / B / c / K / N / D; A = arrival distribution, B = service distribution, c = number of servers, K = system capacity, N = population size, D = queue discipline. Defaults when omitted: ∞, ∞, FIFO.
Utilisation (traffic intensity): ρ = λ ÷ μ; Probability the server is busy. Must be less than 1. Idle probability = 1 − ρ = P(0).
Average number in the system: Ls = λ ÷ (μ − λ) = ρ ÷ (1 − ρ); Includes the customer being served.
Average number in the queue: Lq = λ² ÷ [μ(μ − λ)] = ρ² ÷ (1 − ρ); Only those waiting, not the one in service. Also Lq = Ls − ρ.
Average time in the system: Ws = 1 ÷ (μ − λ); Waiting plus service. Also Ws = Ls ÷ λ.
Average waiting time in the queue: Wq = λ ÷ [μ(μ − λ)] = ρ ÷ (μ − λ); Also Wq = Lq ÷ λ and Wq = Ws − 1/μ.
Probability of n customers in the system: P(n) = (1 − ρ) × ρⁿ; For n = 0, P(0) = 1 − ρ. Probability of more than k customers = ρ^(k+1).
Average waiting time of those who must wait: W(wait | wait > 0) = 1 ÷ (μ − λ); Average time in the queue for customers who actually have to wait. Use only when asked.
Utilisation factor: ρ = λ ÷ (sμ); λ = arrival rate, μ = service rate per server, s = servers. Steady state needs ρ < 1.
Traffic intensity (offered load): r = λ ÷ μ; Average number of servers' worth of work arriving. Also written as the average number being served.
Probability of an empty system: P0 = 1 ÷ [ Σ (n = 0 to s−1) of rⁿ ÷ n! + rˢ ÷ (s! × (1 − ρ)) ]; Compute the sum term by term for n = 0 up to s−1, then add the last term.
Probability that an arrival has to wait: P(wait) = [rˢ ÷ (s! × (1 − ρ))] × P0; This is the last term inside the P0 bracket multiplied by P0.
Average number waiting in queue: Lq = P0 × rˢ × ρ ÷ [ s! × (1 − ρ)² ]; Counts only those waiting, not those being served.
Average waiting time in queue: Wq = Lq ÷ λ; Little's law. Keep the time unit of λ.
Average time in system: Ws = Wq + 1 ÷ μ; Waiting time plus average service time.
Average number in system: Ls = Lq + λ ÷ μ = λ × Ws; Use this as a check on your working.
Total cost per hour: TC = s × Cs + Cw × (Ls or Lq); Cs = cost per server per hour, Cw = waiting cost per customer per hour. Use Ls if the cost applies to customers in the system, Lq if only to those waiting. Follow the question.

Quick revision

Scheduling sets the timing and order of jobs on resources to meet due dates and use capacity well.
FCFS serves jobs in order of arrival; SPT serves the job with the shortest processing time first.
EDD sequences jobs by earliest due date; it helps reduce maximum lateness.
SPT generally gives the lowest average flow time among simple single-machine rules.
Johnson's rule gives the minimum total elapsed time for n jobs on two machines in the same order.
Johnson's rule: smallest time on machine 1 goes first; smallest time on machine 2 goes last.
Gantt chart: time on the horizontal axis, machines or jobs on the vertical axis.
Queue measures need λ (arrival rate) and μ (service rate) in the same time unit.
M/M/1 utilisation: ρ = λ ÷ μ, and the model needs λ < μ.
M/M/1: Ls = λ ÷ (μ − λ); Ws = 1 ÷ (μ − λ); Lq = λ² ÷ [μ(μ − λ)]; Wq = λ ÷ [μ(μ − λ)].
Little's relations: Ls = λ × Ws and Lq = λ × Wq.
M/M/s needs λ < sμ; the formulas use the probability of an empty system, P0.

Common mistakes

Mixing up forward and backward scheduling. Fix: Ask what is fixed. Start date fixed means forward. Due date fixed means backward.
Leaving out waiting, queue and move time in date calculations. Fix: Add every time stated: setup, processing, waiting and transport.
Treating negative lateness as negative tardiness and subtracting it in the total. Fix: Tardiness is never below zero. Replace every negative lateness with 0 before adding.
Using processing time instead of completion time when calculating average flow time. Fix: Flow time includes waiting. Use the running total (completion time) less arrival time.
Placing a job at the front when the smallest time is on Machine 2 (or the reverse). Fix: Say it aloud: Machine 1 → front, Machine 2 → back. Write 'F' or 'B' beside each pick.
Using Johnson's rule for three machines without checking the condition. Fix: Always write the test first: Min M1 ≥ Max M2 or Min M3 ≥ Max M2. Show the numbers. If it fails, say the method is not applicable.
Confusing a load chart with a schedule chart Fix: Load chart: rows are work centres, showing how much work each carries. Schedule chart: rows are jobs, showing planned versus actual progress.
Totalling the cost from the reduced matrix Fix: Go back to the original matrix and add the costs of the assigned cells.
Mixing time units for λ and μ, such as arrivals per hour with service time in minutes. Fix: Convert both to the same unit first. Service time of 5 minutes means μ = 12 per hour.
Treating the mean service time as μ. Fix: μ is a rate. Mean service time = 1 ÷ μ. Check which one the question gives.

Exam tips

Write definition, objectives and types in that order for a 'discuss' question. It gives a clear structure.
For difference questions, use a two-column comparison in points: starting point, use, result and example.
In MCQs, look for the fixed item in the question: start date or due date.
State whether days are inclusive when you do date calculations, and mention your assumption.
Link job shop to the intermittent system and flow shop to the continuous system to pick up easy marks.
Draw the table first: sequence, processing time, completion time, due date, tardiness. Even a wrong final figure earns method marks.
In MCQs, check the measure asked. Average flow time points to SPT as the best; maximum tardiness points to EDD as the best.
Always show the check that the last completion time equals the sum of processing times.