Job Scheduling Using Assignment Model

Goal: minimize total time (minutes).

      J1  J2  J3  J4
T1    12   7  11   8
T2     9  10   6   9
T3     8   9  12   7
T4    11   6   8  10

Step 1 — Row reduction

Row minima: T1=7, T2=6, T3=7, T4=6. Subtract:

      J1  J2  J3  J4
T1     5   0   4   1
T2     3   4   0   3
T3     1   2   5   0
T4     5   0   2   4

Step 2 — Column reduction

Column minima: J1=1, J2=0, J3=0, J4=0. Subtract:

      J1  J2  J3  J4
T1     4   0   4   1
T2     2   4   0   3
T3     0   2   5   0
T4     4   0   2   4

Step 3 — Independent zeros attempt

Zeros appear at (T1,J2), (T2,J3), (T3,J1), (T3,J4), (T4,J2). Column J2 is contested (T1 and T4 both depend on it), so we apply cover/adjust.

Step 4 — Cover all zeros with minimum lines

One minimum cover:

• Cover column J2
• Cover column J3
• Cover row T3

That’s 3 lines < 4 → adjust.

Step 5 — Adjustment

Uncovered cells are in rows T1,T2,T4 and columns J1,J4. Values: 4,1,2,3,4,4 → smallest uncovered is k=1.

Subtract k from uncovered cells; add k to intersections of two lines; others unchanged. Updated matrix:

      J1  J2  J3  J4
T1     3   0   4   0
T2     1   4   0   2
T3     0   3   6   0
T4     3   0   2   3

Step 6 — Select independent zeros

Pick one zero per row and column:

• T3 → J1
• T2 → J3
• T4 → J2
• T1 → J4

Final schedule (original times)

• T1 → J4 = 8
• T2 → J3 = 6
• T3 → J1 = 8
• T4 → J2 = 6

Minimum total time = 28.

Here c(i,j) is a penalty score (lower is better). Assign each nurse to one shift.

         S1  S2  S3  S4
N1        2   6   3   7
N2        4   2   5   6
N3        6   4   2   4
N4        5   7   6   2

Step 1 — Row reduction

Row minima are 2 for every row. Subtract 2 from each row:

         S1  S2  S3  S4
N1        0   4   1   5
N2        2   0   3   4
N3        4   2   0   2
N4        3   5   4   0

Step 2 — Column reduction

Each column already has a 0 minimum, so no changes.

Step 3 — Select independent zeros

There is a clean one-to-one set of zeros (diagonal):

• N1 → S1
• N2 → S2
• N3 → S3
• N4 → S4

Final schedule (original penalties)

• N1 → S1 penalty 2
• N2 → S2 penalty 2
• N3 → S3 penalty 2
• N4 → S4 penalty 2

Minimum total penalty = 8.

You have 4 employees but only 3 shifts (S1–S3). One employee must be OFF (idle). Add a dummy shift OFF so the matrix becomes 4×4.

Penalty matrix (OFF penalty = 0 means idling is acceptable):

         S1  S2  S3  OFF
E1        1   9   7    0
E2        6   4   3    0
E3        5   8   1    0
E4        7   6   9    0

Step 1 — Row reduction

Each row has a minimum of 0 (because OFF=0), so row reduction makes no change.

Step 2 — Column reduction

Column minima are: S1=1, S2=4, S3=1, OFF=0. Subtract them:

         S1  S2  S3  OFF
E1        0   5   6    0
E2        5   0   2    0
E3        4   4   0    0
E4        6   2   8    0

Step 3 — Select independent zeros

We must use OFF exactly once (one employee off). A conflict-free zero selection is:

• E1 → S1 (0)
• E2 → S2 (0)
• E3 → S3 (0)
• E4 → OFF (0)

Final schedule (original penalties)

• E1 → S1 penalty 1
• E2 → S2 penalty 4
• E3 → S3 penalty 1
• E4 → OFF penalty 0

Minimum total penalty = 6.

Job scheduling is exactly an assignment problem when the rules are one-to-one in the chosen planning horizon: every worker must be assigned to exactly one job/shift, and every job/shift must be covered by exactly one worker. Under those assumptions, the schedule is literally a perfect matching between workers and jobs.

The Hungarian algorithm is efficient because it exploits that strict structure. If your scheduling decisions violate any one-to-one rule (e.g., a worker does multiple jobs, or a job requires multiple workers), then you need a different model class.

Dummy penalties encode the tradeoff you are willing to make. A dummy cost of 0 means “idle/unfilled is free,” which is rarely true in operations unless you truly have excess capacity or the work is optional. If leaving a shift unfilled is expensive (service-level impact), dummy penalties should reflect that.

In many applications, dummy penalty is a composite: overtime replacement cost + service penalty + fairness penalty. The goal is not just mathematical feasibility; it’s to preserve the real meaning of the schedule.

Use Hungarian when the problem is one-to-one and costs depend only on the pair (worker, job). It is fast, stable, and interpretable.

Use ILP/MILP when you add realistic constraints: coverage, max nights per week, rest-time constraints, fairness as hard limits, multi-period planning, time windows, precedence, or any coupling between assignments. Start with how to model ILP.