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)

is_allocated(task: Task, unary_resource: Station) → bool[source]

Check if a task is allocated to a given station.

is_present(task: Task) → bool[source]

Tell whether the task is present in the solution.

For allocation problem, default to “at least one unary resource has been allocated to the task”. To be overriden in child classes for problem having tasks present without allocation.

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)