[Feature] Enhance `ORToolsSolver` to Support Arrival Times and Deadlines

[Pabloo22]

This issue is reserved for: @NavidCOMSC

The Goal

We need to modify the ORToolsSolver's solve method so that it can optionally accept arrival_times and deadlines. These will be provided as 2D lists (Sequence[Sequence[int]]), where the first index corresponds to the job ID and the second to the operation's position within that job.

The logic for the solver should be updated as follows:

1. The solve method will accept two new optional arguments: arrival_times and deadlines.
2. If arrival_times are provided, the start time of each operation must be greater than or equal to its specified arrival time.
3. If deadlines are provided, the end time of each operation must be less than or equal to its specified deadline.
4. If these arguments are not provided, the solver should function exactly as it does now.

---

Implementation Steps

Here’s a clear path to get this done:

1. Update the solve and __call__ Method Signatures

In job_shop_lib/constraint_programming/_ortools_solver.py, modify the solve method to accept the new arguments. The __call__ method should also be updated to pass these arguments along to solve.

# In ORToolsSolver class

def __call__(
    self,
    instance: JobShopInstance,
    arrival_times: Sequence[Sequence[int]] | None = None,
    deadlines: Sequence[Sequence[int]] | None = None,
) -> Schedule:
    # This method should now pass the new arguments to self.solve
    return self.solve(instance, arrival_times=arrival_times, deadlines=deadlines)

def solve(
    self,
    instance: JobShopInstance,
    arrival_times: Sequence[Sequence[int]] | None = None,
    deadlines: Sequence[Sequence[int]] | None = None,
) -> Schedule:
    # ...

2. Pass Arguments to _initialize_model

Inside the updated solve method, pass arrival_times and deadlines to the _initialize_model call.

# In the solve method
def solve(...):
    self._initialize_model(instance, arrival_times=arrival_times, deadlines=deadlines)
    # ... rest of the method

This means you will also need to update the signature of _initialize_model to accept these new optional arguments and then pass them down to _create_variables.

# In ORToolsSolver class

def _initialize_model(
    self,
    instance: JobShopInstance,
    arrival_times: Sequence[Sequence[int]] | None = None,
    deadlines: Sequence[Sequence[int]] | None = None,
):
    # ...
    self._create_variables(instance, arrival_times=arrival_times, deadlines=deadlines)
    # ...

3. Apply Constraints in _create_variables

This is the most important step! You'll modify the _create_variables method to enforce the new constraints. Update its signature and then use the arguments to define the variable domains.

Here's a guide to help you implement the logic inside the method:

# In ORToolsSolver class

def _create_variables(
    self,
    instance: JobShopInstance,
    arrival_times: Sequence[Sequence[int]] | None = None,
    deadlines: Sequence[Sequence[int]] | None = None,
):
    for job in instance.jobs:
        for operation in job:
            # Default bounds
            lower_bound = 0
            upper_bound = instance.total_duration

            if arrival_times is not None:
                lower_bound = arrival_times[operation.job_id][operation.position_in_job]

            if deadlines is not None:
                op_deadline = deadlines[operation.job_id][operation.position_in_job]
                upper_bound = op_deadline

            start_var = self.model.NewIntVar(
                lower_bound, upper_bound, f"start_{operation}"
            )
            end_var = self.model.NewIntVar(
                lower_bound, upper_bound, f"end_{operation}"
            )

            self._operations_start[operation] = (start_var, end_var)
            self.model.Add(end_var == start_var + operation.duration)

4. Write Comprehensive Tests

Please add new tests to tests/cp_sat/test_ortools_solver.py. Your tests should cover:

• The solver works correctly when only arrival_times are passed to solve().
• The solver works correctly when only deadlines are passed to solve().
• The solver handles both arrival_times and deadlines at the same time.
• The solver raises a NoSolutionFoundError if the constraints make a solution impossible (e.g., an arrival time is later than a deadline).

You can create fixtures in tests/conftest.py with instances and corresponding arrival/deadline matrices to keep your tests clean.

---

Other Considerations

• Please follow the guidelines in our CONTRIBUTING.md file, including the instructions for commit messages.
• Create a new branch for your work from the main branch.
• Don't hesitate to ask for help! You can comment on the issue if you have any questions.

[NavidCOMSC]

@Pabloo22 Thanks for raising this issue. Please assign it to me at your end.