SA and HCS Optimization Project

一个使用模拟退火算法和登山算法解决流水车间调度问题的最优化实验。

基于C++ 17标准库。

简介

• 本项目来源于最优化方法课程的大作业。

• 本项目实现了使用HCS（登山算法）和SA（模拟退火算法）解决流水车间调度问题。

• 仅使用C++17标准库，可直接编译运行。

• 代码重要处均附有注释，易于复现和修改。

项目结构

• Optimization.h为项目头文件，包含解决方案类声明，算法参数格式声明和随机数生成器。
• Optimization.cpp为项目解决方案文件，包含SA算法，HCS算法的实现及文件预处理方法。
• main.cpp为主文件，包含项目入口main函数和调用算法的cal_func函数。

选择数据集

• 本项目使用给出的数据集flowshop-test-10-student.txt，包含11组原始数据。
• 执行程序时，需输入数字0-10选择要处理的数据组。
• 或调用程序时直接输入数字参数。

简易的复现

直接运行

• 本项目已使用默认参数（SA算法，起始温度=250,温度阈值=5,退火速度=0.95,允许相同数=2），重复20次, 构建了exe可执行文件（Windows平台），可在project目录下，打开cmd命令行窗口，输入.\project.exe运行程序。

使用CMake构建（建议）

• 使用项目内CMakeLists.txt配置文件即可。

使用GNU-g++

• 使用g++编译文件。

g++ main.cpp Optimization.cpp -O3 -std=c++17 -o Test.exe

• 将生成的Test.exe置入项目的project目录下，并在project目录下打开命令行窗口，输入.\Test.exe运行程序。

计算结果

• 程序会打印每次算出的最优（最短时间）结果，仅需查看最后一次输出的结果即可。
• 输出结果格式如下（以第0组数据为例）：

7038
7,4,8,2,6,1,0,3,10,9,5,
Time:59

• 第一行为计算出的最短时间，即工件最优顺序的总加工时间为7038。
• 第二行为此时间对应的工件加工顺序。工件编号按原始数据顺序。从0号开始。
• 第三行为此次计算所耗费的时间，单位为毫秒（ms）。

修改算法和参数

• 若需修改每次执行程序时算法的执行次数，只需修改main.cpp中的main函数：

    for (int i = 0; i < 20; ++i) {
        Solution s(sol);//复制构造Solution对象
        last_ans = cal_func(move(s), last_ans);//计算
    }

• 将i < 20中的20修改为需要的值即可。

---

• 若需修改使用的算法或参数，只需修改main.cpp中的cal_func函数：

    int ans = s.SA(make_tuple(250, 5, 0.95, 25));//SA算法,参数设置分别为起始温度,温度阈值,退火速度和允许相同数
    //int ans = s.HCS();//HCS算法

• 若需修改SA算法的参数，修改make_tuple()内的四个参数即可。
• 若需使用HCS算法，将s.SA所在行注释掉，并解除s.HCS所在行注释即可。