禁忌搜索算法的柔性作业车间调度用C语言实现

禁忌搜索算法（Tabu Search）是一种常见的优化算法，可以用于求解各种组合优化问题，包括柔性作业车间调度问题。下面是一个简单的禁忌搜索算法的柔性作业车间调度的C语言实现：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_JOBS 20
#define MAX_MACHINES 5
#define MAX_ITERATIONS 1000
#define MAX_TABU_SIZE 10

int jobs[MAX_JOBS][MAX_MACHINES];
int machines[MAX_JOBS][MAX_MACHINES];
int durations[MAX_JOBS][MAX_MACHINES];
int tabu_list[MAX_TABU_SIZE][2];
int best_solution[MAX_JOBS];
int current_solution[MAX_JOBS];
int best_cost, current_cost;
int n_jobs, n_machines;

void read_input_data() {
    printf("Number of jobs: ");
    scanf("%d", &n_jobs);
    printf("Number of machines: ");
    scanf("%d", &n_machines);

    printf("Enter job durations:\n");
    for (int i = 0; i < n_jobs; i++) {
        for (int j = 0; j < n_machines; j++) {
            scanf("%d", &durations[i][j]);
        }
    }
}

void initialize() {
    srand(time(NULL));
    for (int i = 0; i < n_jobs; i++) {
        for (int j = 0; j < n_machines; j++) {
            jobs[i][j] = i;
            machines[i][j] = j;
        }
    }
    for (int i = 0; i < n_jobs; i++) {
        for (int j = 0; j < n_machines - 1; j++) {
            int k = rand() % (n_machines - j) + j;
            int temp = machines[i][j];
            machines[i][j] = machines[i][k];
            machines[i][k] = temp;
        }
    }
    for (int i = 0; i < MAX_TABU_SIZE; i++) {
        tabu_list[i][0] = -1;
        tabu_list[i][1] = -1;
    }
    for (int i = 0; i < n_jobs; i++) {
        current_solution[i] = i;
    }
    best_cost = current_cost = calculate_cost(current_solution);
    for (int i = 0; i < n_jobs; i++) {
        best_solution[i] = current_solution[i];
    }
}

int calculate_cost(int* solution) {
    int cost = 0;
    int finish_times[MAX_MACHINES] = {0};
    for (int i = 0; i < n_jobs; i++) {
        int job = solution[i];
        int machine = machines[job][0];
        int duration = durations[job][machine];
        for (int j = 1; j < n_machines; j++) {
            int next_machine = machines[job][j];
            int next_duration = durations[job][next_machine];
            if (finish_times[machine] > finish_times[next_machine]) {
                machine = next_machine;
                duration = next_duration;
            } else {
                duration = finish_times[machine] - finish_times[next_machine] + next_duration;
            }
        }
        finish_times[machine] += duration;
        cost += finish_times[machine];
    }
    return cost;
}

void update_tabu_list(int machine1, int machine2) {
    for (int i = 0; i < MAX_TABU_SIZE; i++) {
        if (tabu_list[i][0] == -1 && tabu_list[i][1] == -1) {
            tabu_list[i][0] = machine1;
            tabu_list[i][1] = machine2;
            return;
        }
    }
    for (int i = 0; i < MAX_TABU_SIZE - 1; i++) {
        tabu_list[i][0] = tabu_list[i+1][0];
        tabu_list[i][1] = tabu_list[i+1][1];
    }
    tabu_list[MAX_TABU_SIZE-1][0] = machine1;
    tabu_list[MAX_TABU_SIZE-1][1] = machine2;
}

int is_tabu(int machine1, int machine2) {
    for (int i = 0; i < MAX_TABU_SIZE; i++) {
        if (tabu_list[i][0] == machine1 && tabu_list[i][1] == machine2) {
            return 1;
        }
    }
    return 0;
}

void search() {
    int iterations = 0;
    while (iterations < MAX_ITERATIONS) {
        int best_i = -1, best_j = -1, best_cost = 0x7fffffff;
        for (int i = 0; i < n_jobs; i++) {
            for (int j = i+1; j < n_jobs; j++) {
                int temp = machines[current_solution[i]][0];
                machines[current_solution[i]][0] = machines[current_solution[j]][0];
                machines[current_solution[j]][0] = temp;
                int cost = calculate_cost(current_solution);
                if (cost < best_cost && !is_tabu(i, j)) {
                    best_i = i;
                    best_j = j;
                    best_cost = cost;
                }
                temp = machines[current_solution[i]][0];
                machines[current_solution[i]][0] = machines[current_solution[j]][0];
                machines[current_solution[j]][0] = temp;
            }
        }
        if (best_i == -1 && best_j == -1) {
            break;
        }
        int temp = machines[current_solution[best_i]][0];
        machines[current_solution[best_i]][0] = machines[current_solution[best_j]][0];
        machines[current_solution[best_j]][0] = temp;
        update_tabu_list(best_i, best_j);
        for (int i = 0; i < n_jobs; i++) {
            current_solution[i] = best_solution[i];
        }
        current_cost = best_cost;
        if (current_cost < best_cost) {
            best_cost = current_cost;
            for (int i = 0; i < n_jobs; i++) {
                best_solution[i] = current_solution[i];
            }
        }
        iterations++;
    }
}

void print_results() {
    printf("Best solution: ");
    for (int i = 0; i < n_jobs; i++) {
        printf("%d ", best_solution[i]);
    }
    printf("\n");
    printf("Best cost: %d\n", best_cost);
}

int main() {
    read_input_data();
    initialize();
    search();
    print_results();
    return 0;
}

其中，`read_input_data()`函数用于读入输入数据，`initialize()`函数用于初始化算法参数和随机生成初始解，`calculate_cost()`函数用于计算解的目标函数值，`update_tabu_list()`函数用于更新禁忌列表，`is_tabu()`函数用于判断某个解是否在禁忌列表中，`search()`函数是实现禁忌搜索算法的核心部分，`print_results()`函数用于输出结果。

在这个实现中，我们使用了一个`machines`数组来表示每个工件在不同机器上的加工顺序，使用一个`tabu_list`数组来表示禁忌列表，其中每个元素是一个长度为2的数组，表示交换了哪两个工件。我们随机生成了一个初始解，并使用禁忌搜索算法来不断改进该解，直到达到最大迭代次数或者找到最优解为止。