production line next product

Hi all,

In my scheduling model, I would to determine the next production chunk (successor) for a given chunk on a production line. However, due to multiple valid successors, the model sometimes selects chunks that start later, rather than the immediate next chunk in the sequence.

Ultimately, I want to ensure that the next product selected is the immediately adjacent scheduled product (i.e., the one with the lowest start time among those starting after the current chunk).

Generalized Example of the Issue

We have three chunks scheduled on a generic production line X.

Next product after B is C, starts at 6 on line X
Next product after A is C, starts at 6 on line X
Next product after A is B, starts at 5 on line X

Problem:

• A should only be followed by B, but it also has C_Chunk1 as a successor.
• We need to restrict the next product to the nearest scheduled chunk.

This misalignment occurs because our constraints currently allow multiple valid successors. However, we only want the immediate next chunk in the production sequence. If I limit the next_product to 1 then it selects at random or the last in line instead of the one with lowest start time.

Code block 1:Validating Successor Existence and Eliminating Last Chunks

# 6. Ensure every chunk (except the last one) has at least one valid successor
for l in lines:
    # Get all chunks for this production line: line1, line2, or line3
    line_chunks = [chunk for chunk in all_chunks if
                   (chunk.split("_")[0] in products_line1 and l == "line1") or
                   (chunk.split("_")[0] in products_line2 and l == "line2") or
                   (chunk.split("_")[0] in products_line3 and l == "line3")]
    
    for chunk1 in line_chunks:
        successors = [chunk2 for chunk2 in line_chunks if chunk1 != chunk2]  # All potential successors

        # (1) For every chunk (if it isn’t the last), at least one successor must be selected.
        if successors:
            model.addConstr(
                gp.quicksum(x[chunk1, chunk2, l] for chunk2 in successors) >= 1 - is_last_chunk[chunk1, l],
                name=f"Ensure_AtLeastOnePossibleSuccessor_{chunk1}_{l}"
            )

        # (2) Eliminate last chunks from being considered as successors.
        for chunk2 in successors:
            model.addConstr(
                x[chunk1, chunk2, l] <= 1 - is_last_chunk[chunk1, l],
                name=f"Eliminate_LastChunk_AsSuccessor_{chunk1}_{chunk2}_{l}"
            )

Purpose:
This block ensures that for each production chunk (except those marked as the last chunk on the line), there is at least one valid successor.

What It Does:
1. Line Selection: It selects the chunks relevant to the production line (line1, line2, or line3).
2. Successor Check: For each chunk1, it collects all other chunks (chunk2) as potential successors.
3. Existence Constraint: It forces the sum of x[chunk1, chunk2, l] (the sequencing decision variable) over all potential successors to be at least 1 (unless the chunk is the last one).
4. Elimination Constraint: It ensures that if chunk1 is marked as the last chunk, then no successor (x) is allowed.


Code block 2: Enforcing Order Using Delta

delta = model.addVars(all_chunks, all_chunks, lines, vtype=GRB.BINARY, name="Delta_S_Comparison")

for l in lines:
    # Select all chunks for this production line
    line_chunks = [chunk for chunk in all_chunks if
                   (chunk.split("_")[0] in products_line1 and l == "line1") or
                   (chunk.split("_")[0] in products_line2 and l == "line2") or
                   (chunk.split("_")[0] in products_line3 and l == "line3")]
    for chunk1 in line_chunks:
        for chunk2 in line_chunks:
            if chunk1 != chunk2:
                # (1) Enforce delta = 1 when S[chunk1] < S[chunk2]:
                model.addConstr(
                    S[chunk1, l] + 1 <= S[chunk2, l] + M * (1 - delta[chunk1, chunk2, l]),
                    name=f"Delta_Enforce_If_S1_Less_S2_{chunk1}_{chunk2}_{l}"
                )
                # (2) Enforce delta = 0 when S[chunk1] >= S[chunk2]:
                model.addConstr(
                    S[chunk1, l] >= S[chunk2, l] - M * delta[chunk1, chunk2, l],
                    name=f"Delta_Enforce_If_S1_GreaterOrEqual_S2_{chunk1}_{chunk2}_{l}"
                )

Code block 3: Enforcing the Next Product Selection (S_next)

Purpose:
The variable delta[chunk1, chunk2, l] is a binary indicator that is meant to be 1 if and only if the start time of chunk1 is strictly less than that of chunk2.

What It Does:
1. Lower Bound Constraint: If delta = 1, then the constraint forces S[chunk1] + 1 <= S[chunk2] (ensuring a strict increase).
2. Upper Bound Constraint: If delta = 0, then S[chunk1] must be at least S[chunk2] (preventing an invalid ordering).

Block 3: Enforcing S_next to Reflect the Chosen Successor
for l in lines:
    # Select all chunks for this production line
    line_chunks = [chunk for chunk in all_chunks if
                   (chunk.split("_")[0] in products_line1 and l == "line1") or
                   (chunk.split("_")[0] in products_line2 and l == "line2") or
                   (chunk.split("_")[0] in products_line3 and l == "line3")]
    for chunk1 in line_chunks:
        for chunk2 in line_chunks:
            if chunk1 != chunk2:
                # (1) Ensure S_next is at least S[chunk2] when x = 1 and delta = 1
                model.addConstr(
                    S_next[chunk1, chunk2, l] >= S[chunk2, l] - M * (1 - x[chunk1, chunk2, l]) - M * (1 - delta[chunk1, chunk2, l]),
                    name=f"Ensure_Snext_MatchesX_{chunk1}_{chunk2}_{l}"
                )
                # (2) Ensure S_next does not exceed S[chunk2] when x = 1 and delta = 1
                model.addConstr(
                    S_next[chunk1, chunk2, l] <= S[chunk2, l] + M * (1 - x[chunk1, chunk2, l]) + M * (1 - delta[chunk1, chunk2, l]),
                    name=f"Ensure_Snext_DoesNotExceed_{chunk1}_{chunk2}_{l}"
                )
                # (3) Ensure S_next is exactly 0 when x = 0
                model.addConstr(
                    S_next[chunk1, chunk2, l] <= M * x[chunk1, chunk2, l],
                    name=f"Ensure_Snext_ZeroWhenXIsZero_{chunk1}_{chunk2}_{l}"
                )

Purpose:
The variable S_next[chunk1, chunk2, l] is intended to capture the start time of a successor chunk (chunk2) if it is selected (i.e., if x[chunk1, chunk2, l] = 1 and the order is valid, as indicated by delta = 1).

What It Does:
1. Lower Bound Constraint: When both x and delta equal 1, S_next is forced to be at least S[chunk2].
2. Upper Bound Constraint: Similarly, it is forced to be no more than S[chunk2] when x = 1 and delta = 1.
3. Zero Constraint: If x = 0 (meaning the pair isn’t chosen), then S_next is forced to 0.


I've tried a couple of things:
A. S_next Constraints (Basic Next Chunk Selection).

Issue:

• This allowed multiple successors (more than one next product per chunk).
• The model couldn't distinguish the nearest next chunk.

B. S_next_min (Selecting the Smallest Next Start Time)

Issue:

• This approach still relied on pairwise constraints, which did not consistently enforce a unique smallest next product.
• We couldn't guarantee that only the nearest chunk was chosen.

C. Nothing_in_between (Ensuring No Gaps)

To check whether another chunk is scheduled between two chunks, we introduced nothing_in_between[chunk1, chunk3, l].
The idea: Sum all active scheduling decisions (u) between chunk1 and chunk3. If no chunks exist in between, the sum should match the presence of chunk1 and chunk3 only.

Issue:

• Missed enforcing a strict "next product" rule, as it still allowed multiple next chunks.

Thanks a lot for your consideration.