The Central Idea
Scheduling, assignment, and routing problems are all forms of discrete optimization.
A discrete optimization problem asks us to choose from separate, countable alternatives while satisfying restrictions and improving some measure of performance.
The general structure is:
\[ \boxed{\text{choose a feasible arrangement that best meets an objective}} \]The three families differ mainly in what is being arranged.
- Scheduling: arrange tasks in time.
- Assignment: match agents or resources to tasks.
- Routing: choose paths through a network.
Decision Variables, Constraints, and Objectives
Most problems in this family can be described using three ingredients.
Decision variables
These represent the choices we control.
Examples include:
- which worker is assigned to which job;
- which task is performed first;
- which route a vehicle follows;
- whether an edge is included in a selected path.
Constraints
Constraints describe what is allowed.
Examples include:
- a worker can perform only one job at a time;
- a task cannot begin until another task finishes;
- a vehicle cannot exceed its capacity;
- a route must begin and end at specified locations.
Objective
The objective tells us what to optimize.
Common objectives include:
- minimize total completion time;
- minimize total cost;
- minimize total distance;
- minimize lateness;
- maximize the number of completed tasks;
- maximize utilization or coverage.
Feasible and Optimal Solutions
A solution is feasible if it satisfies every required constraint.
A solution is optimal if it is feasible and no other feasible solution has a better value under the chosen objective.
These are different ideas.
A schedule can be valid but inefficient. A route can reach every required destination but be unnecessarily long. An assignment can respect all restrictions while producing a higher total cost than another assignment.
Scheduling Problems
A scheduling problem assigns tasks to times, machines, workers, rooms, processors, or other limited resources.
A schedule may need to account for:
- task durations;
- deadlines;
- precedence requirements;
- resource conflicts;
- release times;
- setup times;
- priorities.
A First Scheduling Example
Suppose four tasks require the following times:
| Task | Duration |
|---|---|
| A | 4 hours |
| B | 2 hours |
| C | 5 hours |
| D | 3 hours |
If one worker must complete all four tasks and there are no other constraints, then every ordering requires the same total processing time:
\[ 4+2+5+3=\boxed{14\text{ hours}}. \]However, the order can still affect other measures such as average completion time, lateness, or customer waiting.
Completion Time
The completion time of a task is the time at which it finishes.
Suppose the tasks are performed in the order
\[ A\rightarrow B\rightarrow C\rightarrow D. \]Then the completion times are:
| Task | Completion Time |
|---|---|
| A | 4 |
| B | 6 |
| C | 11 |
| D | 14 |
The total completion time is
\[ 4+6+11+14=\boxed{35}. \]Shortest Processing Time First
When all jobs are available at the start and the objective is to reduce the sum or average of completion times on one machine, a useful rule is shortest processing time first.
For the durations
\[ 2,\ 3,\ 4,\ 5, \]the order becomes
\[ B\rightarrow D\rightarrow A\rightarrow C. \]The completion times are
\[ 2,\ 5,\ 9,\ 14. \]Their sum is
\[ 2+5+9+14=\boxed{30}. \]This is smaller than the total completion time of \(35\) in the earlier ordering.
Average Completion Time
If \(C_1,C_2,\ldots,C_n\) are the completion times of \(n\) tasks, the average completion time is
\[ \boxed{\bar C=\frac{C_1+C_2+\cdots+C_n}{n}}. \]In the shortest-processing-time example,
\[ \bar C=\frac{2+5+9+14}{4} =\frac{30}{4} =\boxed{7.5}. \]Deadlines and Lateness
Scheduling becomes more complicated when jobs have due dates.
Let
\[ C_i=\text{completion time of job }i \]and
\[ d_i=\text{due date of job }i. \]The lateness of job \(i\) is
\[ \boxed{L_i=C_i-d_i}. \]If \(L_i<0\), the job finishes early.
If \(L_i=0\), the job finishes exactly on time.
If \(L_i>0\), the job finishes late.
Tardiness
Sometimes we care only about how late a job is, not how early it finishes.
The tardiness of job \(i\) is
\[ \boxed{T_i=\max(0,C_i-d_i)}. \]Thus tardiness is never negative.
If a job finishes two hours early,
\[ C_i-d_i=-2, \]but
\[ T_i=0. \]Precedence Constraints
A precedence constraint says one task must occur before another.
If task A must finish before task C can begin, we can write
\[ A\prec C. \]Precedence constraints naturally form a directed graph.
An arrow
\[ A\rightarrow C \]means A is a predecessor of C.
Precedence Graphs
Suppose a project contains the constraints
\[ A\prec C,\qquad B\prec C,\qquad C\prec D. \]A simple precedence diagram is:
A ──┐
├──> C ───> D
B ──┘
Tasks A and B may be performed before C. Task D must wait until C is complete.
Topological Ordering
A topological ordering is an ordering of the vertices of a directed acyclic graph in which every predecessor appears before its successor.
For the constraints
\[ A\prec C,\qquad B\prec C,\qquad C\prec D, \]both
\[ A,B,C,D \]and
\[ B,A,C,D \]are valid topological orderings.
The ordering
\[ C,A,B,D \]is not valid because C appears before its required predecessors.
Parallel Scheduling
When several workers or machines are available, tasks may sometimes be performed simultaneously.
Suppose tasks A and B can begin immediately and take 4 hours and 3 hours, respectively. Task C requires both and then takes 2 hours.
If A and B are performed in parallel, C can start only after the slower predecessor finishes.
Therefore,
\[ \max(4,3)+2=\boxed{6\text{ hours}}. \]This is shorter than performing A and B sequentially.
Makespan
The makespan of a schedule is the time at which the entire set of scheduled work is complete.
If the last task finishes at time \(M\), then
\[ \boxed{\text{makespan}=M}. \]Minimizing makespan is a common objective in machine scheduling, project planning, computing, manufacturing, and logistics.
Load Balancing
When tasks can be divided among several machines or workers, one goal is to balance the workload.
Suppose the task durations are
\[ 8,\ 7,\ 5,\ 4. \]With two workers, one possible assignment is:
- Worker 1: \(8+4=12\);
- Worker 2: \(7+5=12\).
The makespan is
\[ \boxed{12}. \]This is perfectly balanced.
Assignment Problems
An assignment problem matches members of one set to members of another set.
Typical examples include:
- workers to jobs;
- drivers to routes;
- machines to production tasks;
- students to projects;
- crews to flights;
- servers to requests.
A basic assignment problem usually requires a one-to-one matching.
A Cost Matrix
Suppose three workers can each perform three jobs. The cost matrix is
\[ C= \begin{bmatrix} 8 & 6 & 10\\ 9 & 7 & 5\\ 6 & 8 & 7 \end{bmatrix}. \]The rows represent workers A, B, and C.
The columns represent jobs 1, 2, and 3.
For example,
\[ c_{23}=5 \]means assigning worker B to job 3 has cost \(5\).
One-to-One Assignment
In the basic three-by-three assignment problem:
- each worker receives exactly one job;
- each job is assigned to exactly one worker.
One possible assignment is
\[ A\rightarrow2,\qquad B\rightarrow3,\qquad C\rightarrow1. \]Its total cost is
\[ 6+5+6=\boxed{17}. \]Counting Possible Assignments
With \(n\) workers and \(n\) jobs, a one-to-one assignment corresponds to a permutation of the jobs.
Therefore, the number of possible complete assignments is
\[ \boxed{n!}. \]For three workers and three jobs,
\[ 3!=3\cdot2\cdot1=\boxed{6}. \]For ten workers and ten jobs,
\[ 10!=3,628,800. \]This rapid growth explains why systematic algorithms become important.
Enumerating a Small Assignment Problem
For the matrix
\[ \begin{bmatrix} 8 & 6 & 10\\ 9 & 7 & 5\\ 6 & 8 & 7 \end{bmatrix}, \]the six possible job permutations are:
| A | B | C | Total Cost |
|---|---|---|---|
| 1 | 2 | 3 | \(8+7+7=22\) |
| 1 | 3 | 2 | \(8+5+8=21\) |
| 2 | 1 | 3 | \(6+9+7=22\) |
| 2 | 3 | 1 | \(6+5+6=17\) |
| 3 | 1 | 2 | \(10+9+8=27\) |
| 3 | 2 | 1 | \(10+7+6=23\) |
The minimum cost is
\[ \boxed{17}. \]Assignment as a Bipartite Graph
Assignment problems can also be represented using bipartite graphs.
One vertex set contains the workers:
\[ \{A,B,C\}. \]The other contains the jobs:
\[ \{1,2,3\}. \]An edge connects a worker to a job when that assignment is allowed.
Edge weights can represent costs, times, scores, or benefits.
Perfect Matchings
A matching is a set of edges that do not share endpoints.
A perfect matching matches every vertex in both sets.
In a balanced one-to-one assignment problem, a feasible complete assignment is a perfect matching in the corresponding bipartite graph.
This connects assignment problems directly to graph theory.
Forbidden Assignments
Not every worker may be qualified for every job.
Suppose worker A cannot perform job 3.
We can represent that restriction by:
- omitting the corresponding edge in a bipartite graph;
- marking the matrix entry as forbidden;
- assigning a sufficiently large penalty cost when using a numerical algorithm.
The important point is that infeasible assignments must not be treated as ordinary choices.
Binary Assignment Variables
Assignment problems are often expressed using binary variables.
Let
\[ x_{ij}= \begin{cases} 1,&\text{if worker }i\text{ is assigned to job }j,\\ 0,&\text{otherwise.} \end{cases} \]If each worker receives exactly one job, then for each worker \(i\),
\[ \boxed{\sum_j x_{ij}=1}. \]If each job receives exactly one worker, then for each job \(j\),
\[ \boxed{\sum_i x_{ij}=1}. \]Assignment Objective Function
If \(c_{ij}\) is the cost of assigning worker \(i\) to job \(j\), the total assignment cost is
\[ \boxed{\sum_i\sum_j c_{ij}x_{ij}}. \]A cost-minimization assignment problem therefore seeks
\[ \min \sum_i\sum_j c_{ij}x_{ij} \]subject to the assignment constraints.
Balanced and Unbalanced Assignment Problems
A problem is balanced when the number of agents equals the number of tasks.
It is unbalanced when the two sets have different sizes.
For example, five workers and three jobs form an unbalanced assignment problem.
Some algorithms convert an unbalanced problem into a balanced one by adding dummy rows or columns with appropriately chosen values.
Routing Problems
A routing problem asks how something should move through a network.
The network may represent:
- roads;
- air routes;
- communication links;
- warehouse connections;
- pipes;
- computer networks;
- delivery stops.
Vertices represent locations or states, and edges represent possible connections.
Weighted Routes
Routing problems usually attach a weight to each edge.
A weight may represent:
- distance;
- travel time;
- cost;
- risk;
- energy use;
- delay.
If a path uses edges with weights \(w_1,w_2,\ldots,w_k\), its total weight is
\[ \boxed{w_1+w_2+\cdots+w_k}. \]A First Shortest-Route Example
Suppose the network contains the following travel times:
- A to B: 4;
- A to C: 7;
- B to C: 2;
- B to D: 6;
- C to D: 3.
Two routes from A to D are:
\[ A\rightarrow B\rightarrow D \]with total time
\[ 4+6=10, \]and
\[ A\rightarrow B\rightarrow C\rightarrow D \]with total time
\[ 4+2+3=\boxed{9}. \]The second route is shorter.
Shortest Path
A shortest path is a path between two vertices having minimum total weight.
If \(P\) is a path containing edges \(e_1,e_2,\ldots,e_k\), then its weight is
\[ w(P)=\sum_{r=1}^{k}w(e_r). \]A shortest path from \(s\) to \(t\) satisfies
\[ \boxed{w(P^\ast)\le w(P)} \]for every feasible path \(P\) from \(s\) to \(t\).
Dijkstra's Method: The Core Idea
For networks with nonnegative edge weights, Dijkstra's algorithm finds shortest paths from a starting vertex.
The core process is:
- assign the starting vertex distance \(0\);
- assign all other vertices temporary distance \(\infty\);
- select the unresolved vertex with smallest temporary distance;
- use it to improve distances to its neighbors;
- mark the selected vertex resolved;
- repeat until the desired destination or all reachable vertices are resolved.
Relaxation
The update step in shortest-path algorithms is often called relaxation.
If we know a current best distance \(d(u)\) to vertex \(u\), and the edge from \(u\) to \(v\) has weight \(w(u,v)\), then a possible new distance to \(v\) is
\[ d(u)+w(u,v). \]We update \(d(v)\) when
\[ d(u)+w(u,v)Routing Is Not Always Shortest Path
A shortest-path problem travels from one origin to one destination.
Many practical routing problems are more complicated.
A vehicle may need to:
- visit several locations;
- return to its starting point;
- respect delivery windows;
- avoid restricted roads;
- stay within capacity;
- serve each customer exactly once.
These additional requirements create different routing models.
The Traveling Salesperson Problem
The traveling salesperson problem, or TSP, asks for a minimum-weight tour that visits every required vertex exactly once and returns to the starting point.
The objective is
\[ \boxed{\text{minimize total tour length}} \]subject to visiting every required location.
TSP is a classic example of a problem that is easy to state but becomes computationally difficult as the number of locations grows.
Counting Tours
If a starting city is fixed and \(n-1\) other cities must be visited, then a direct ordering produces
\[ (n-1)! \]possible visit sequences.
In a symmetric problem, a route and its reverse have the same length, so the number of distinct tours can often be reduced to
\[ \boxed{\frac{(n-1)!}{2}}. \]Even this reduced count grows very quickly.
A Small Traveling-Salesperson Example
Suppose four locations A, B, C, and D must be visited, beginning and ending at A.
One tour is
\[ A\rightarrow B\rightarrow C\rightarrow D\rightarrow A. \]Another is
\[ A\rightarrow B\rightarrow D\rightarrow C\rightarrow A. \]For a small number of vertices, every tour may be evaluated directly.
For larger instances, exhaustive enumeration becomes impractical.
Nearest-Neighbor Heuristic
A heuristic is a practical rule intended to produce a good solution without necessarily guaranteeing the optimal one.
A common TSP heuristic is nearest neighbor:
- start at a chosen vertex;
- travel to the nearest unvisited vertex;
- repeat until all vertices have been visited;
- return to the starting point.
The method is simple and fast, but it can produce a tour that is not globally optimal.
Local Choices Can Produce Global Mistakes
A greedy routing rule may choose the cheapest immediate edge.
That can be useful, but the cheapest next step can force an expensive final connection later.
This illustrates an important optimization principle:
\[ \boxed{\text{locally best does not always mean globally best}} \]Greedy methods must therefore be justified for the specific problem in which they are used.
Vehicle Routing
The vehicle routing problem generalizes route planning to multiple vehicles and operational constraints.
A vehicle-routing model may include:
- several vehicles;
- customer demand;
- vehicle capacities;
- delivery windows;
- driver-hour limits;
- multiple depots;
- pickup-and-delivery requirements.
These problems combine graph theory, combinatorics, optimization, and algorithm design.
Capacity Constraints
Suppose a vehicle has capacity \(Q\) and visits customers with demands \(q_1,q_2,\ldots,q_k\).
A feasible route must satisfy
\[ \boxed{q_1+q_2+\cdots+q_k\le Q}. \]If the total demand exceeds capacity, the route must be split, additional vehicles must be used, or another operational change must be made.
Time-Window Constraints
Some locations can be served only during specified intervals.
If customer \(i\) must be served between times \(a_i\) and \(b_i\), then the service time \(t_i\) should satisfy
\[ \boxed{a_i\le t_i\le b_i}. \]A short-distance route can therefore be infeasible if it reaches a customer outside the required time window.
Scheduling and Routing Can Interact
In practice, these problem families often overlap.
A delivery company may need to decide:
- which driver receives each delivery;
- which route each driver follows;
- when each stop is served;
- how vehicle capacities are respected.
This single operational problem contains assignment, routing, and scheduling simultaneously.
Assignment and Scheduling Can Interact
Suppose three technicians have different qualifications and three jobs have different durations.
The first question may be:
Which technician should perform each job?
That is an assignment problem.
The next question may be:
In what order should each technician perform the assigned jobs?
That is a scheduling problem.
Routing and Assignment Can Interact
Suppose a company has several vehicles with different capacities.
Assigning customers to vehicles is an assignment-type decision.
Choosing the order in which each assigned group of customers is visited is a routing decision.
Many real optimization systems therefore solve several linked subproblems.
Exact Methods and Heuristics
An exact algorithm guarantees an optimal solution when it finishes correctly.
A heuristic seeks a good solution efficiently but may not guarantee optimality.
Exact methods are attractive when the problem is small enough or when optimality is operationally important.
Heuristics become useful when the search space is enormous or a rapid high-quality solution is more valuable than a proof of optimality.
Brute Force
Brute force evaluates every feasible candidate and selects the best one.
For a small assignment problem with \(3!=6\) possibilities, brute force is reasonable.
For \(12\) assignments,
\[ 12!=479,001,600. \]Direct enumeration is now much more demanding.
The growth of the search space is often the central computational challenge.
Greedy Methods
A greedy algorithm repeatedly makes a locally attractive choice.
Examples include:
- choosing the shortest available job next;
- choosing the nearest unvisited location;
- selecting the least-cost feasible assignment at a step.
Some greedy methods are provably optimal for specific problems.
Others are merely heuristics.
Optimization Depends on the Objective
The same feasible arrangement can look good under one objective and poor under another.
A route minimizing distance may not minimize:
- travel time;
- fuel use;
- tolls;
- risk;
- lateness.
A schedule minimizing makespan may not minimize average customer waiting.
Therefore, the objective must be stated before the phrase best solution has a precise meaning.
Multiple Objectives
Practical problems often contain several objectives.
A delivery plan might try to:
- minimize distance;
- avoid late deliveries;
- balance driver workloads;
- reduce fuel use.
These objectives can conflict.
One approach is to combine them in a weighted score:
\[ \boxed{ Z=w_1f_1+w_2f_2+\cdots+w_kf_k }. \]The weights \(w_i\) reflect the relative importance assigned to the different performance measures.
Hard and Soft Constraints
A hard constraint must be satisfied.
Examples include:
- a legally required rest period;
- a machine capacity limit;
- a task precedence requirement.
A soft constraint is desirable but may be violated at a penalty.
Examples include:
- preferred shift times;
- preferred driver territories;
- desired workload balance.
Penalty Functions
Soft constraints can be incorporated using penalties.
Suppose route cost is \(C\) and each late delivery adds penalty \(p\).
If there are \(k\) late deliveries, a simple penalized objective is
\[ \boxed{Z=C+pk}. \]A larger penalty makes lateness more expensive relative to route cost.
Common Error: Optimizing Before Defining the Objective
A problem cannot be optimized until the performance measure is clear.
Saying
find the best route
is incomplete unless we know whether best means shortest, fastest, cheapest, safest, or something else.
Common Error: Ignoring Feasibility
A low-cost solution is useless if it violates a required constraint.
For example, a vehicle route that minimizes distance but exceeds vehicle capacity is not a feasible solution.
Optimization always occurs over the feasible set.
Common Error: Confusing Total Processing Time and Makespan
If several machines work in parallel, total work and elapsed completion time are different quantities.
Suppose two tasks take 5 hours each and are performed simultaneously by two workers.
Total processing time is
\[ 5+5=10\text{ worker-hours}. \]But the makespan is only
\[ \boxed{5\text{ hours}}. \]Common Error: Violating Precedence
A schedule may appear efficient but still be invalid if a successor begins before its predecessor finishes.
If
\[ A\prec B, \]then B cannot be scheduled before A is complete.
Common Error: Assigning One Job Twice
In a one-to-one assignment problem, each job must appear exactly once.
An arrangement such as
\[ A\rightarrow1,\qquad B\rightarrow1,\qquad C\rightarrow3 \]is not feasible because job 1 is assigned twice while job 2 is unassigned.
Common Error: Assuming the Cheapest Individual Assignments Form the Best Total Assignment
Choosing the cheapest entry in each row independently can create conflicts.
Two workers may both have their lowest cost in the same job column.
Because each job can usually be assigned only once, the assignment must be optimized as a complete matching rather than as isolated row decisions.
Common Error: Using a Shortest-Path Method with Negative Weights
Some shortest-path algorithms, including standard Dijkstra's algorithm, require nonnegative edge weights.
If negative edge weights are present, a different method may be required.
Algorithm assumptions are part of the mathematics, not optional implementation details.
Common Error: Treating a Heuristic Solution as Proven Optimal
A heuristic may produce an excellent route or schedule.
But unless the method provides an optimality guarantee or the result has been independently verified, we should not claim that the solution is optimal.
The correct language is often:
the heuristic produced a feasible solution with objective value \(Z\).
A Reliable Procedure for Scheduling Problems
- List the tasks.
- Record task durations.
- Identify available workers, machines, rooms, or processors.
- Record precedence constraints.
- Record release times, deadlines, or time windows when relevant.
- State the objective.
- Construct a feasible order or allocation.
- Calculate completion times, lateness, utilization, or makespan.
- Compare alternative schedules.
- Verify all constraints.
A Reliable Procedure for Assignment Problems
- Identify the two sets being matched.
- Construct the cost, time, score, or benefit matrix.
- Mark forbidden assignments.
- Determine whether the problem is balanced.
- State whether the objective is minimization or maximization.
- Generate or solve for feasible matchings.
- Calculate the total objective value.
- Compare alternatives.
- Verify that every required agent and task is matched correctly.
A Reliable Procedure for Routing Problems
- Identify the vertices or locations.
- Identify the allowed edges or connections.
- Attach the appropriate weights.
- State the origin and destination or required tour structure.
- Record capacity, time-window, or visit constraints.
- State the objective.
- Select an appropriate exact or heuristic method.
- Construct a feasible route.
- Calculate its total weight.
- Compare it with alternatives when possible.
- Verify all operational constraints.
Example: Full Scheduling Workflow
Four jobs have processing times
\[ 6,\ 2,\ 4,\ 3. \]Suppose the goal is to minimize average completion time on one machine and all jobs are available immediately.
Order the jobs from shortest to longest:
\[ 2,\ 3,\ 4,\ 6. \]The completion times are
\[ 2,\ 5,\ 9,\ 15. \]The average completion time is
\[ \frac{2+5+9+15}{4} =\frac{31}{4} =\boxed{7.75}. \]Example: Full Assignment Workflow
Suppose the assignment-cost matrix is
\[ \begin{bmatrix} 4 & 7 & 6\\ 8 & 5 & 9\\ 7 & 6 & 3 \end{bmatrix}. \]Consider the assignment
\[ A\rightarrow1,\qquad B\rightarrow2,\qquad C\rightarrow3. \]The total cost is
\[ 4+5+3=\boxed{12}. \]Checking the other five permutations confirms that this assignment is optimal for the given matrix.
Example: Full Routing Workflow
Suppose the available weighted edges are:
- A-B: 3;
- A-C: 8;
- B-C: 2;
- B-D: 7;
- C-D: 2;
Candidate routes from A to D include:
\[ A\rightarrow B\rightarrow D \]with cost
\[ 3+7=10, \]and
\[ A\rightarrow B\rightarrow C\rightarrow D \]with cost
\[ 3+2+2=\boxed{7}. \]Therefore, among these candidates, the second route is better.
Practice 1: Completion Times
Jobs A, B, and C have durations
\[ 5,\ 2,\ 4 \]and are performed in the order
\[ A\rightarrow B\rightarrow C. \]Find the completion time of each job.
Practice 2: Shortest Processing Time
Four jobs have durations
\[ 7,\ 3,\ 6,\ 2. \]Give the shortest-processing-time order.
Practice 3: Lateness
A job finishes at time \(11\) and has due date \(8\).
Find its lateness and tardiness.
Practice 4: Parallel Tasks
Tasks A and B can begin together. A takes 6 hours and B takes 4 hours. Task C requires both and takes 3 additional hours.
Find the project makespan.
Practice 5: Count Assignments
How many one-to-one assignments are possible between five workers and five jobs?
Practice 6: Assignment Cost
For the matrix
\[ \begin{bmatrix} 5 & 8 & 7\\ 6 & 4 & 9\\ 8 & 6 & 3 \end{bmatrix}, \]find the total cost of
\[ A\rightarrow1,\qquad B\rightarrow2,\qquad C\rightarrow3. \]Practice 7: Feasible Matching
Is the following a feasible one-to-one assignment?
\[ A\rightarrow2,\qquad B\rightarrow2,\qquad C\rightarrow1. \]Explain.
Practice 8: Route Weight
A route uses three edges with weights
\[ 4,\ 6,\ 3. \]Find the total route weight.
Practice 9: Compare Routes
Route A has edge weights
\[ 3,\ 5,\ 4. \]Route B has edge weights
\[ 2,\ 4,\ 7. \]Which route is shorter?
Practice 10: Capacity Constraint
A vehicle has capacity \(20\). A proposed route serves customers with demands
\[ 7,\ 6,\ 5,\ 4. \]Is the route feasible under the capacity constraint?
Practice Answers
Practice 1
Completion times accumulate:
\[ C_A=5, \] \[ C_B=5+2=7, \] \[ C_C=5+2+4=\boxed{11}. \]Practice 2
Sort the durations from least to greatest:
\[ \boxed{2,\ 3,\ 6,\ 7}. \]Practice 3
\[ L=11-8=\boxed{3}. \]Because lateness is positive,
\[ T=\max(0,3)=\boxed{3}. \]Practice 4
C must wait until both predecessors are complete, so it begins after
\[ \max(6,4)=6. \]Then
\[ 6+3=\boxed{9\text{ hours}}. \]Practice 5
\[ 5!=5\cdot4\cdot3\cdot2\cdot1=\boxed{120}. \]Practice 6
\[ 5+4+3=\boxed{12}. \]Practice 7
No. Job 2 is assigned to both A and B, while job 3 is unassigned.
Therefore, the assignment is not a feasible one-to-one matching.
Practice 8
\[ 4+6+3=\boxed{13}. \]Practice 9
Route A:
\[ 3+5+4=12. \]Route B:
\[ 2+4+7=13. \]Therefore,
\[ \boxed{\text{Route A is shorter}}. \]Practice 10
Total demand is
\[ 7+6+5+4=22. \]Since
\[ 22>20, \]the proposed route is not feasible under the capacity constraint.
What to Remember
Scheduling, assignment, and routing are closely related discrete optimization problems.
- scheduling arranges tasks in time;
- assignment matches resources to tasks;
- routing chooses paths through networks;
- constraints determine feasibility;
- objectives determine what counts as better;
- feasible and optimal do not mean the same thing;
- precedence graphs organize task dependencies;
- assignment matrices organize matching costs or benefits;
- weighted graphs organize route costs or distances;
- exact methods guarantee optimality when applicable;
- heuristics trade certainty of optimality for speed or simplicity.
The central habit is: define the choices, constraints, and objective before trying to optimize the arrangement.
Where We Go Next
Scheduling, assignment, and routing show how discrete structures support operational decisions involving time, matching, and movement. The same modeling habits extend naturally to collective-choice problems, where the challenge is no longer assigning jobs or choosing paths but converting individual preferences or population counts into group decisions.
The next lesson, Voting and Apportionment, examines methods for selecting winners, ranking alternatives, and allocating a fixed number of seats among competing groups.