变邻域搜索算法求解置换flow shop的python代码

以下是使用变邻域搜索算法求解置换flow shop问题的Python代码：

import random

def calculate_cmax(permutation, processing_times):
    n = len(processing_times[0])
    m = len(processing_times)
    cmax = [0] * n
    for j in range(n):
        if j == 0:
            cmax[0] = processing_times[permutation[0]][0]
        else:
            cmax[j] = cmax[j-1] + processing_times[permutation[0]][j]
        for i in range(1, m):
            if j == 0:
                cmax[j] += processing_times[permutation[i]][j]
            else:
                cmax[j] = max(cmax[j], cmax[j-1]) + processing_times[permutation[i]][j]
    return cmax[-1]

def generate_initial_solution(n):
    return list(range(n))

def swap(permutation, i, j):
    permutation[i], permutation[j] = permutation[j], permutation[i]

def neighborhood_1(permutation):
    neighborhood = []
    for i in range(len(permutation)):
        for j in range(i+1, len(permutation)):
            neighbor = list(permutation)
            swap(neighbor, i, j)
            neighborhood.append(neighbor)
    return neighborhood

def neighborhood_2(permutation):
    neighborhood = []
    for i in range(len(permutation)):
        for j in range(i+2, len(permutation)):
            neighbor = list(permutation)
            neighbor[i+1:j+1] = reversed(neighbor[i+1:j+1])
            neighborhood.append(neighbor)
    return neighborhood

def variable_neighborhood_search(processing_times, max_iterations):
    current_solution = generate_initial_solution(len(processing_times))
    best_solution = list(current_solution)
    for i in range(max_iterations):
        neighborhood = neighborhood_1(current_solution) + neighborhood_2(current_solution)
        random.shuffle(neighborhood)
        for neighbor in neighborhood:
            if calculate_cmax(neighbor, processing_times) < calculate_cmax(current_solution, processing_times):
                current_solution = list(neighbor)
                if calculate_cmax(current_solution, processing_times) < calculate_cmax(best_solution, processing_times):
                    best_solution = list(current_solution)
                break
    return best_solution

# Example usage
processing_times = [[2, 7, 3], [9, 2, 8], [6, 4, 5]]
solution = variable_neighborhood_search(processing_times, 1000)
print("Best solution:", solution)
print("Cmax:", calculate_cmax(solution, processing_times))

在此示例中，`processing_times` 是一个 $m \times n$ 的二维列表，其中 $m$ 是作业数，$n$ 是机器数，表示每个作业在每个机器上的加工时间。`variable_neighborhood_search` 函数接受 `processing_times` 和 `max_iterations` 两个参数，返回一个包含最佳解的置换。`calculate_cmax` 函数接受一个置换和 `processing_times`，返回在该置换下的最大完工时间 `Cmax`。`generate_initial_solution` 函数返回一个初始解，`swap` 函数交换置换中两个元素的位置，`neighborhood_1` 和 `neighborhood_2` 分别生成大小为 $n(n-1)/2$ 和 $n(n-3)/2$ 的两个邻域。最后，我们使用 `processing_times` 和 `solution` 调用 `calculate_cmax` 函数来计算最佳解的 `Cmax`。