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

柔性作业车间调度是一种复杂的问题，禁忌搜索算法可以用来寻找较优解。下面是一个简单的C语言实现，供参考：

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

#define N 5  // 作业数量
#define M 3  // 机器数量
#define L 10 // 时段数量

const int a[N][M] = { {2, 1, 3}, {4, 3, 5}, {5, 4, 6}, {3, 2, 3}, {1, 4, 2} }; // a[i][j]表示第i个作业在第j台机器上的加工时间

int p[N]; // p[i]表示第i个作业的加工顺序
int s[M][L]; // s[i][j]表示第i台机器在第j个时段是否空闲，1表示空闲，0表示占用

int f() // 计算当前方案的总加工时间
{
    int t[M][L] = { 0 }; // t[i][j]表示第i台机器在第j个时段加工的剩余时间
    int c[N][M] = { 0 }; // c[i][j]表示第i个作业在第j台机器上的完成时间
    int max = 0; // 记录总加工时间的最大值
    for (int i = 0; i < N; i++) // 遍历每个作业
    {
        int j = p[i]; // 第i个作业加工在第j台机器上
        int k = 0; // 记录可以开始加工的时段
        while (k < L && !s[j][k]) k++; // 找到第一个空闲时段
        if (k >= L) return 0x7fffffff; // 如果没有空闲时段，方案不可行
        c[i][j] = k + a[i][j]; // 计算完成时间
        t[j][k] = a[i][j]; // 更新加工时间
        for (int l = k + 1; l < c[i][j]; l++) s[j][l] = 0; // 标记占用的时段
        if (c[i][j] > max) max = c[i][j]; // 更新总加工时间的最大值
    }
    return max;
}

void swap(int i, int j) // 交换p数组中的两个元素
{
    int t = p[i];
    p[i] = p[j];
    p[j] = t;
}

int main()
{
    srand(time(NULL));
    for (int i = 0; i < N; i++) p[i] = i; // 初始化p数组为[0, 1, 2, ..., N-1]
    int best_f = f(); // 记录当前最优方案的总加工时间
    int tabu[N][N] = { 0 }; // tabu[i][j]表示上次交换p[i]和p[j]的迭代次数
    int max_iter = 1000; // 最大迭代次数
    int iter = 0; // 当前迭代次数
    while (iter < max_iter)
    {
        int i = rand() % N;
        int j = rand() % N;
        while (i == j) j = rand() % N;
        swap(i, j);
        int new_f = f();
        if (new_f < best_f)
        {
            best_f = new_f;
            tabu[i][j] = iter;
        }
        else
        {
            swap(i, j);
        }
        for (int k = 0; k < N; k++)
        {
            if (k != i && k != j && tabu[k][i] > iter - 5 && tabu[k][j] > iter - 5)
            {
                swap(i, j);
                break;
            }
        }
        iter++;
    }
    printf("最优方案的总加工时间：%d\n", best_f);
    printf("作业加工顺序：");
    for (int i = 0; i < N; i++) printf("%d ", p[i]);
    printf("\n");
    return 0;
}

该代码使用随机交换p数组中的两个元素来搜索解空间，同时使用禁忌表来避免陷入局部最优解。在搜索过程中，每次计算当前方案的总加工时间，并记录最优方案的总加工时间。当找到一个新的方案时，如果它比当前最优方案更优，则将它作为当前最优方案，并将交换的两个位置加入禁忌表；否则，如果它比当前方案更劣，则根据禁忌表来判断是否可以接受这个方案。在最终输出结果时，除了输出最优方案的总加工时间之外，还输出作业的加工顺序。