I’m trying to implement a local search algorithm. I’ve made some progress, but there’s still a problem. I need the solutions to respect the predecessors and successors constraint, and I’m not sure how to do that since I’m new to Python. Could you please help me ?

Thank you!

import random

# Example list of starting times and durations
StartingTime = [0,5,10,15,20,10,0]
p = [0,15,20,5,10,7,0]  # Durations of each task
nPrecs = 5;
pred = [1,1,2,3,5]; #predecessors
succ = [3,4,5,4,6]; #successors


# Objective function: minimize makespan (total time to complete all tasks)
def objective_function(start_times, durations):
    end_times = [start_times[i] + durations[i] for i in range(len(start_times))]
    return max(end_times)  # The makespan is the maximum end time


# Generate neighbors: create new schedules by swapping starting times of tasks
def generate_neighbors(start_times):
    neighbors = []
    for i in range(len(start_times)):
        for j in range(i + 1, len(start_times)):
            new_start_times = start_times[:]
            new_start_times[i], new_start_times[j] = new_start_times[j], new_start_times[i]
            neighbors.append(new_start_times)
    return neighbors

# Local search algorithm (hill climbing) with swapping method
def local_search(start_times, durations):
    current_solution = start_times
    current_value = objective_function(current_solution, durations)

    while True:
        neighbors = generate_neighbors(current_solution)
        next_solution = None
        next_value = float('inf')

        print(f"Evaluating neighbors of solution: {current_solution} with objective value {current_value}")
        for neighbor in neighbors:
            value = objective_function(neighbor, durations)
            print(f"Neighbor solution: {neighbor} with objective value {value}")
            if value < next_value:
                next_solution = neighbor
                next_value = value

        if next_value >= current_value:
            break  # No better neighbor found, local optimum reached

        current_solution = next_solution
        current_value = next_value
        print(f"Improved solution: {current_solution} with objective value {current_value}")

    return current_solution, current_value


# Generate initial solution by randomly swapping starting times
def generate_initial_solution(start_times):
    initial_solution = start_times[:]
    random.shuffle(initial_solution)
    return initial_solution


# Running the local search algorithm
initial_solution = generate_initial_solution(StartingTime)
print(f"Initial solution: {initial_solution}")

best_solution, best_value = local_search(initial_solution, p)
print(f"Best solution: {best_solution} with objective value {best_value}")

i try to implement a function for this but it’s not working.