discrete_optimization.alb package

Subpackages

Module contents

class discrete_optimization.alb.BaseALBProblem(tasks_data: List[TaskData], precedences: List[Tuple[Task, Task]], stations: List[Station])[source]

Bases: PrecedenceProblem[Task], AllocationProblem[Task, Station], SchedulingProblem[Task], Generic[Task, Station]

Base class for all Assembly Line Balancing Problems.

Combines three standard mixins: - PrecedenceProblem: handles precedence constraints and graph - AllocationProblem: handles task-to-station assignment - SchedulingProblem: handles timing and makespan

All ALB variants extend this base with additional constraints (cycle time, resources, learning effects, etc.).

tasks_data

List of TaskData objects (or subclass) for each task

task_times

Dict mapping task_id -> processing_time (for convenience)

precedences

List of (predecessor, successor) pairs

tasks

Sorted list of task identifiers

stations

List of workstation identifiers

nb_tasks

Number of tasks

nb_stations

Number of stations

check_precedence_violation_stations(pred_station: Station, succ_station: Station) → bool[source]

Check if assigning predecessor to pred_station and successor to succ_station violates precedence at the station level.

In ALB, precedence means predecessor must be assigned to an earlier or equal station (by index in stations list).

Parameters:

  • pred_station – Station assigned to predecessor task

  • succ_station – Station assigned to successor task

Returns:

True if this assignment violates precedence, False otherwise

correct_allocation_to_station_precedence(allocation_to_station: list[int]) → bool[source]
evaluate(solution: Solution) → Dict[str, float][source]

Default evaluate implementation using base constraints.

Subclasses should override this to add problem-specific objectives and constraints. They can call super().evaluate() or use evaluate_base_constraints() to get common penalties.

Returns:

Dictionary with evaluation metrics

evaluate_base_constraints(solution: BaseALBSolution[Task, Station]) → Dict[str, float][source]

Evaluate base constraints common to all ALB problems.

Uses the new solution time helper methods for clean precedence checking.

Returns:

  • penalty_precedence: Number of precedence violations

  • penalty_unscheduled: Number of tasks without assignment or schedule

Return type:

Dictionary with

Subclasses should call this and add their specific penalties.

get_first_tasks() → List[Task][source]

Get tasks with no predecessors (source nodes).

Returns:

List of tasks that have no predecessor constraints

get_last_tasks() → List[Task][source]

Get tasks with no successors (sink nodes).

Returns:

List of tasks that are not predecessors to any other task

get_makespan_upper_bound() → int[source]

Return an upper bound on the makespan.

Worst case: all tasks executed sequentially.

Returns:

Sum of all task processing times

get_precedence_constraints() → Dict[Task, Iterable[Task]][source]

Map each task to its successors.

Required by PrecedenceProblem mixin.

Returns:

Dictionary mapping task -> list of successor tasks

get_predecessors() → Dict[Task, List[Task]][source]

Get predecessor mapping (inverse of successors).

Returns:

Dictionary mapping task -> list of predecessor tasks

get_successors() → Dict[Task, List[Task]][source]

Get successor mapping.

Returns:

Dictionary mapping task -> list of successor tasks

get_task_data(task_id: Task) → TaskData[source]

Get TaskData object for a given task.

Parameters:

task_id – Task identifier

Returns:

TaskData object (or subclass) for this task

satisfy(solution: Solution) → bool[source]

Base satisfaction check: all penalties must be zero.

Subclasses should override evaluate() to add specific constraints.

Parameters:

solution – Solution to check

Returns:

True if solution satisfies all constraints

property tasks_list: List[Task]

Return the list of all tasks.

property unary_resources_list: List[Station]

Return the list of all stations (unary resources).

In ALB problems, stations are the unary resources for allocation.

class discrete_optimization.alb.BaseALBSolution(problem: Problem)[source]

Bases: SchedulingSolution[Task], AllocationSolution[Task, Station], Generic[Task, Station]

Base solution class for Assembly Line Balancing problems.

Provides time-related helper methods that work for all ALB variants: - get_start_time_in_cycle(task): Start time within the cycle - get_absolute_start_time(task): “Unfolded” absolute time - get_station_index(task): Index of assigned station

Subclasses must implement: - task_assignment: Dict[Task, Station] mapping - Either task_schedule OR compute schedule on demand - cycle_time attribute

get_absolute_end_time(task: Task) → int[source]

Get the “unfolded” absolute end time of a task.

Returns:

Absolute end time in unfolded timeline

get_absolute_start_time(task: Task) → int[source]

Get the “unfolded” absolute start time of a task.

This is useful for precedence checking and visualization. Formula: station_index * cycle_time + start_time_in_cycle

Returns:

Absolute start time in unfolded timeline

get_end_time_in_cycle(task: Task) → int[source]

Get the end time of a task within its cycle.

Returns:

End time within the cycle

get_start_time_in_cycle(task: Task) → int[source]

Get the start time of a task within its cycle.

For problems with explicit scheduling (RC-ALBP), this returns task_schedule[task]. For problems without scheduling (SALBP), this computes it using greedy scheduling.

Returns:

Start time within the cycle [0, cycle_time)

get_station_index(task: Task) → int[source]

Get the index of the station where task is assigned.

Returns:

Station index (0-based)

problem: BaseALBProblem[Task, Station]
class discrete_optimization.alb.ResourceTaskData(task_id: Hashable, processing_time: int, resource_consumption: Dict[Hashable, int] = None)[source]

Bases: TaskData

Task data with resource requirements for resource-constrained ALB problems.

Extends TaskData with resource consumption information.

task_id

Unique identifier for the task

processing_time

Duration to execute the task

resource_consumption

Dict mapping resource_name -> consumption amount

get_resource_consumption(resource: Hashable) → int[source]

Get resource consumption for a given resource.

Parameters:

resource – Resource identifier

Returns:

Consumption amount (0 if not specified)

class discrete_optimization.alb.TaskData(task_id: Hashable, processing_time: int)[source]

Bases: object

Base class for task data in ALB problems.

This class is designed to be subclassed to add domain-specific attributes like resource requirements, zone constraints, etc.

task_id

Unique identifier for the task

processing_time

Duration to execute the task (in base conditions)