三班制排班优化问题：基于员工可用性实现每班次员工数量最大化

Alright, let's break down how to solve this 3-shift scheduling problem where we need to maximize the number of employees per shift, while sticking to the given constraints. I've dealt with similar scheduling optimization problems before, so here's a structured approach that works:

1. First, Let's Categorize Employees #

To make this easier to handle, split your workforce into groups based on their eligibility and shift limits:

• Single-shift only workers: Employees who only want 1 shift (like your Employee 1, eligible for 2/3, max 1 shift). These folks can be assigned to any eligible shift, and we'll use them to fill gaps later.
• Consecutive multi-shift workers: Employees who can work 2+ shifts, but only consecutive ones. Valid consecutive combinations here are [1,2], [2,3], or all three [1,2,3] (since 1 and 3 aren't consecutive, that split is strictly off-limits).
• Edge case workers: If someone says they can do shifts 1 and 3 but only want 2 shifts—sorry, that's a non-starter per your constraints. They have to be treated as single-shift workers (either 1 or 3, not both).

2. Prioritize High-Impact Assignments First #

The key to maximizing per-shift counts is to use employees who can cover multiple consecutive shifts first—they boost two (or three) shifts at once, which is way more efficient than assigning single-shift workers one by one.

Step 1: Assign 3-shift eligible workers #

If you have employees who can do all three shifts and are willing to work 3 shifts, assign them to all three immediately. Each of these workers adds +1 to every shift, which is the highest possible impact.

For those who can do all three but only want 2 shifts: pick the pair of consecutive shifts that currently have the lowest total count. For example, if shift 1 has 2 people, shift 2 has 2, shift 3 has 1—assign them to [2,3] to bring those two shifts into balance.

Step 2: Assign 2-consecutive-shift eligible workers #

Next, handle employees who can only do a specific consecutive pair (like [1,2] or [2,3]). Assign them to their full eligible pair if their max shift count allows it. This will bump up both shifts in the pair at once.

Step 3: Fill gaps with single-shift workers #

Once all multi-shift workers are assigned, look at which shift has the lowest headcount. Grab any single-shift worker who's eligible for that shift and assign them there. Repeat this until you've either assigned all single-shift workers or all shifts are as balanced (and full) as possible.

3. Example Walkthrough #

Let's use your sample employees plus a couple more to see how this works:

• Employee 1: Eligible for 2/3, max 1 shift (single-shift)
• Employee 2: Eligible for 1/2/3, max 2 shifts (multi-shift)
• Employee 3: Eligible for 1/2, max 2 shifts (multi-shift)
• Employee 4: Eligible for 2/3, max 1 shift (single-shift)

1. Assign Employee 2: Since shifts start at 0, we pick the pair that will balance things most—let's go with [1,2]. Now shifts 1=1, 2=1, 3=0.
2. Assign Employee 3: They can do [1,2], so assign both shifts. Now shifts 1=2, 2=2, 3=0.
3. Fill shift 3 gaps: Assign Employee 1 and Employee 4 to shift 3. Now shifts 1=2, 2=2, 3=2.

Perfect—all shifts are maxed out evenly, and every employee is working within their limits and constraints.

4. Quick Pseudocode for Automation #

If you want to code this up, here's a simplified outline to get you started:

# Pre-sort employees into groups
single_shift = [{"eligible": [2,3], "max":1}, ...]
double_consec = [{"pair": (1,2), "max":2}, ...]
triple_eligible = [{"max":2}, {"max":3}, ...]

# Track shift counts
shift_counts = {1:0, 2:0, 3:0}

# Step 1: Handle triple-eligible workers
for worker in triple_eligible:
    if worker["max"] >=3:
        shift_counts[1] +=1
        shift_counts[2] +=1
        shift_counts[3] +=1
    elif worker["max"] ==2:
        # Choose the consecutive pair with lower total count
        pair1_total = shift_counts[1] + shift_counts[2]
        pair2_total = shift_counts[2] + shift_counts[3]
        if pair1_total <= pair2_total:
            shift_counts[1] +=1
            shift_counts[2] +=1
        else:
            shift_counts[2] +=1
            shift_counts[3] +=1

# Step 2: Handle double-consecutive workers
for worker in double_consec:
    s1, s2 = worker["pair"]
    shift_counts[s1] +=1
    shift_counts[s2] +=1

# Step 3: Fill gaps with single-shift workers
while single_shift:
    # Find the shift with the lowest count
    lowest_shift = min(shift_counts, key=lambda x: shift_counts[x])
    # Find eligible workers for this shift
    eligible = [w for w in single_shift if lowest_shift in w["eligible"]]
    if not eligible:
        # Try the next lowest shift
        sorted_shifts = sorted(shift_counts.items(), key=lambda x: x[1])
        lowest_shift = sorted_shifts[1][0]
        eligible = [w for w in single_shift if lowest_shift in w["eligible"]]
        if not eligible:
            break
    # Assign the first eligible worker
    assigned = eligible[0]
    shift_counts[lowest_shift] +=1
    single_shift.remove(assigned)

print(shift_counts)

5. Key Things to Remember #

• Never assign a worker to non-consecutive shifts (1 and 3) even if they say they're eligible—this violates your core constraint.
• If a worker's max shift count is higher than the number of consecutive shifts they can do (e.g., eligible for [1,2] but max 3 shifts), their effective limit is 2 shifts—you can't add a third non-consecutive shift.
• Always prioritize balancing shifts as you go—this ensures you don't end up with one shift overstaffed while others are understaffed.

内容的提问来源于stack exchange，提问作者hm8