discrete_optimization.alb.rcalbp package

Subpackages

• discrete_optimization.alb.rcalbp.solvers package
  • Submodules
  • discrete_optimization.alb.rcalbp.solvers.cpsat module
    • CpSatRcAlbpSolver
      • CpSatRcAlbpSolver.create_allocation()
      • CpSatRcAlbpSolver.get_resource_consumption_intervals()
      • CpSatRcAlbpSolver.get_task_start_or_end_variable()
      • CpSatRcAlbpSolver.get_task_unary_resource_is_present_variable()
      • CpSatRcAlbpSolver.hyperparameters
      • CpSatRcAlbpSolver.init_model()
      • CpSatRcAlbpSolver.init_model_calendar()
      • CpSatRcAlbpSolver.init_model_folded()
      • CpSatRcAlbpSolver.problem
      • CpSatRcAlbpSolver.retrieve_solution()
    • ModelingShared
      • ModelingShared.CALENDAR
      • ModelingShared.FOLDED
  • Module contents

Submodules

discrete_optimization.alb.rcalbp.problem module

Resource-Constrained Assembly Line Balancing Problem (RC-ALBP)

This problem combines elements from: - SALBP (Simple Assembly Line Balancing): Task assignment and precedence - Resource constraints at workstations

Problem Definition:

Given: - A fixed number of workstations (stations) - A set of tasks with processing times, precedence constraints, and resource requirements - Multiple resource types with two allocation models:

1. STATION-SPECIFIC RESOURCES: - Shared taxonomy/names across all stations (e.g., “Workbench”, “Robot_Arm”) - Tasks consume resources by name (e.g., Task_A needs 1 “Workbench”) - Each station has its own CAPACITY for each resource type - Example: Station_1 has 2 Workbenches, Station_2 has 1 Workbench - A task can only execute at a station with sufficient resource capacity

2. SHARED/GLOBAL RESOURCES (optional): - Global pool shared across ALL stations (e.g., “AGV”, “Quality_Inspector”) - Tasks consume from the global capacity pool - Total concurrent demand across all stations must not exceed global capacity

Decision Variables: - Assignment of tasks to workstations - Start time of each task within the cycle

Objective: - Minimize the cycle time (makespan)

Constraints: 1. Precedence: Predecessor tasks must finish before successors (or be assigned to earlier stations) 2. Station-specific Resource Capacity: At each station, cumulative resource consumption cannot

exceed that station’s capacity for each resource type (tasks CAN overlap if total demand fits)

3. Shared Resource Capacity: Across ALL stations simultaneously, cumulative resource consumption cannot exceed global capacity for each shared resource

class discrete_optimization.alb.rcalbp.problem.RCALBPProblem(tasks_data: List[ResourceTaskData], precedences: List[Tuple[Hashable, Hashable]], stations: List[Hashable], resources: List[Hashable] = None, station_resources: Dict[Hashable, Dict[Hashable, int]] = None, shared_resources: Set[Hashable] = None, shared_resource_capacities: Dict[Hashable, int] = None)

Bases: BaseALBProblem[Hashable, Hashable]

Resource-Constrained Assembly Line Balancing Problem.

Extends BaseALBProblem with cumulative resource constraints. Supports both station-specific and shared/global resources.

Inherits from: - BaseALBProblem: Provides precedence, allocation, and scheduling foundations

Attributes (in addition to BaseALBProblem):

resources: List of station-specific resource names (shared taxonomy) station_resources: Capacity per station {station: {resource: capacity}} shared_resources: Set of shared resource names (global pool) shared_resource_capacities: Global capacity {resource: capacity} nb_resources: Total count (station-specific + shared)

evaluate(solution: RCALBPSolution) → Dict[str, float]

Evaluate the solution quality and constraint satisfaction.

Uses base class for precedence checking (via absolute times) and adds RC-ALBP-specific resource constraint validation.

Returns:

• cycle_time: Maximum makespan across all stations

• penalty_precedence: Number of precedence violations (from base)

• penalty_resource_station: Amount of station-specific resource over-consumption

• penalty_resource_shared: Amount of shared resource over-consumption

Return type:

Dictionary with

get_all_resources() → Set[Hashable]

Get all resources (station-specific + shared).

get_attribute_register() → EncodingRegister

Register for vectorized encoding (enables GA/metaheuristics).

Solution is encoded as a list of integers (station assignments). allocation_to_station[i] = station index for task i

get_dummy_solution() → RCALBPSolution

Create a trivial dummy solution (likely infeasible). Assigns all tasks to the first station sequentially.

get_objective_register() → ObjectiveRegister

Define objectives and penalties.

Primary objective: Minimize cycle time Penalties: Precedence violations, resource capacity violations (station + shared)

get_resource_availabilities(resource: Hashable) → list[tuple[int, int, int]]

get_shared_capacity(resource: Hashable) → int

Get global capacity for a shared resource (0 if not specified).

get_solution_type() → type[Solution]

Return the solution class type.

get_station_capacity(station: Hashable, resource: Hashable) → int

Get resource capacity at a station (0 if not specified).

get_station_specific_resources() → Set[Hashable]

Get only station-specific resources.

get_task_demand(task: Hashable, resource: Hashable) → int

Get resource demand for a task (0 if not specified).

Uses ResourceTaskData if available, otherwise falls back to empty demand.

Parameters:

• task – Task identifier

• resource – Resource identifier

Returns:

Consumption amount (0 if not specified)

is_resource_shared(resource: Hashable) → bool

Check if a resource is shared (global pool) or station-specific.

property renewable_resources_list: list[Hashable]

class discrete_optimization.alb.rcalbp.problem.RCALBPSolution(problem: RCALBPProblem, allocation_to_station: List[int] | None = None, task_assignment: Dict[Hashable, Hashable] | None = None, task_schedule: Dict[Hashable, int] | None = None, cycle_time: int | None = None)

Bases: BaseALBSolution[Hashable, Hashable]

Solution for RC-ALBP problem.

RC-ALBP has explicit scheduling (task_schedule) since resource constraints require knowing exact start times within the cycle.

Uses vectorized representation for task assignments (like SALBP): - allocation_to_station[i] = station index for task i - task_assignment property builds dict on-demand

problem

Reference to the problem instance

Type:

discrete_optimization.alb.rcalbp.problem.RCALBPProblem

allocation_to_station

List[int] where index i = task i, value = station index

task_schedule

Dict mapping each task to its start time within cycle

cycle_time

The computed cycle time (max end time across all stations)

change_problem(new_problem: Problem) → Solution

Change the problem instance.

copy() → RCALBPSolution

Create a deep copy of the solution.

get_end_time(task: Hashable) → int

Return the end time of a task within cycle.

get_renewable_resource_consumption(resource: Hashable, task: Hashable) → int

get_start_time(task: Hashable) → int

Return the start time of a task within cycle.

get_start_time_in_cycle(task: Hashable) → int

Get start time within cycle.

If explicit schedule exists, use it. Otherwise, compute greedy schedule from task assignments.

get_station_index(task: Hashable) → int

Get the index of the station where task is assigned.

is_allocated(task: Hashable, unary_resource: UnaryResource) → bool

Check if a task is allocated to a given station.

problem: RCALBPProblem

property task_assignment: Dict[Hashable, Hashable]

Build task_assignment dict from vectorized representation on-demand.

This allows backward compatibility with code expecting dict.

discrete_optimization.alb.rcalbp.utils module

Utility functions for RC-ALBP-Problem Provides helpers for: - Creating problem instances (from rcpsp) - Visualizing solutions - Computing lower bounds

discrete_optimization.alb.rcalbp.utils.create_from_rcpsp(rcpsp_problem: RcpspProblem, nb_stations: int = 3, seed: int = 42) → RCALBPProblem

Create a realistic RC-ALBP instance from an RCPSP problem.

This converts a project scheduling problem into an assembly line balancing problem by: - Using RCPSP tasks, durations, and precedences - Splitting RCPSP global resources across stations - Using RCPSP resource consumption per task

Parameters:

• rcpsp_problem – RCPSP problem instance

• nb_stations – Number of assembly line stations

• seed – Random seed for resource allocation

Returns:

RCALBPProblem instance

discrete_optimization.alb.rcalbp.utils.create_large_shared_resource_instance(base_instance_name: str, nb_stations: int, shared_ratio: float = 0.25) → RCALBPProblem

Create a large instance with shared resources from an RCPSP instance.

Parameters:

• base_instance_name – Name of RCPSP instance to load

• nb_stations – Number of stations

• shared_ratio – Fraction of resources that should be shared (default 0.25 = 25%)

Returns:

RCALBPProblem instance with both station-specific and shared resources

discrete_optimization.alb.rcalbp.utils.create_shared_resource_example() → RCALBPProblem

Create a small example with both station-specific and shared resources.

Resources: - R1, R2: Station-specific (different capacity per station) - R_AGV: Shared mobile robot (capacity = 2 across all stations)

Returns:

RCALBPProblem instance with shared resources

discrete_optimization.alb.rcalbp.utils.load_rcpsp_as_albp(instance_name: str = 'j301_1', nb_stations: int = 3, seed: int = 42) → RCALBPProblem

Load an RCPSP instance from PSPLib and convert to RC-ALBP.

Parameters:

• instance_name – Name of RCPSP instance (e.g., “j301_1”)

• nb_stations – Number of assembly line stations

• seed – Random seed for resource allocation

Returns:

RCALBPProblem instance

discrete_optimization.alb.rcalbp.utils.print_solution_info(problem: RCALBPProblem, solution: RCALBPSolution)

Print detailed information about a solution.

Parameters:

• problem – Problem instance

• solution – Solution to analyze

discrete_optimization.alb.rcalbp.utils.visualize_interactive_flow(problem: RCALBPProblem, solution: RCALBPSolution)

Create an interactive visualization of assembly line flow with time slider.

Shows: - Aircraft/product flow through stations over time - Active tasks at each station - Resource usage tracking per station - Constraint violation warnings

Parameters:

• problem – Problem instance

• solution – Solution to visualize

discrete_optimization.alb.rcalbp.utils.visualize_solution(problem: RCALBPProblem, solution: RCALBPSolution, show: bool = True) → Figure

Visualize the assembly line solution as a Gantt chart with stacked tasks.

Parameters:

• problem – Problem instance

• solution – Solution to visualize

• show – Whether to display the plot

Returns:

Matplotlib figure

Module contents