分支限界法用于批处理作业调度。

简介：
#include #include using namespace std; class MinHeapNode { friend class Flowshop; public: bool operator<(const MinHeapNode &a) const { return a.bb < bb; } private: void Init(int); void NewNode(MinHeapNode, int, int, int, int); int s; // 已安排作业数 int f1; // 机器 1 上最后完成时间 int f2; // 机器 2 上最后完成时间 int sf2; // 当前机器 2 上的完成时间和下界时间（用于优化） int bb; // 当前完成时间和下界时间（用于优化）的最小值，用于堆排序。 它代表当前作业的当前完成时间和其下界时间。 这个值在堆中用于比较作业的优先级。 int *x; // 当前作业调度信息，存储每个作业在不同机器上的执行顺序和时间。 }; void MinHeapNode::Init(int n) { // 最小堆结点初始化函数，为每个节点分配内存空间。n 代表需要初始化的节点数量。这个函数负责为每个节点分配存储作业信息的内存块，以便后续进行作业调度和排序操作。 它初始化了 `x` 指向的数组，该数组用于存储每个作业在不同机器上的执行顺序和时间信息。 x = new int[n]; // 分配内存空间，用于存储每个节点的作业调度信息。 for (int i = 0; i < n; i++) { //循环遍历所有节点，为每个节点分配内存空间并初始化其数据成员。 x[i] = i; // 初始化每个节点的 `x` 数组元素为当前索引 `i`，表示该节点对应于第 `i` 个作业。这部分代码将 `x` 数组中的每个元素设置为当前索引 `i`，表明该节点对应于第 `i` 个作业的信息。 这通常用于在后续操作中识别与特定作业相关联的节点或数据项. } } void MinHeapNode::NewNode(MinHeapNode node, int s, int f1, int f2, int sf2) { // 新增结点函数，创建新的最小堆结点并设置其初始值. 参数包括已安排的作业数、机器1上的最后完成时间、机器2上的最后完成时间以及机器2上的当前完成时间和下界时间. 这个函数的作用是在现有最小堆的基础上创建一个新的最小堆结点，并设置其初始值（例如已安排的作业数、各机器上的最后完成时间等）。新结点将添加到最小堆中进行排序和维护. this->s = s; // 将已安排的作业数赋值给当前结点的 `s` 成员变量. 这表明该结点所代表的作业已经安排了 `s` 个单位的时间. 这个变量被用来跟踪已经安排好的任务数量. this->f1 = f1; // 将机器1上的最后完成时间赋值给当前结点的 `f1` 成员变量. 这表示该结点所代表的任务在机器1上执行完毕的时间点是 `f1`. 这个变量用于确定任务之间的依赖关系和调度顺序. this->f2 = f2; // 将机器2上的最后完成时间赋值给当前结点的 `f2` 成员变量. 这表示该结点所代表的任务在机器2上执行完毕的时间点是 `f2`. 这个变量与 `f1` 一起确定任务的执行顺序和资源利用率. this->sf2 = sf2;// 将机器2上当前的完成时间和下界时间的最小值赋值给当前结点的 sf2 成员变量. 这表示该结点所代表的任务在机器二上当前的执行时间和下界时间的最小值是sf2 . 下界时间的最小值保证了任务能够按时完成. 这个值对于优化调度策略至关重要. this->bb = bb;//将当前的下界时间的最小值赋值给当前的bb成员变量 . 下界的最小值保证了任务能够按时完成 . 这个值对于优化调度策略至关重要 . bb 代表当前时刻的最早可用的下一个任务可以开始执行的时间点 . 它反映了任务对其他任务的依赖关系以及资源约束条件 . 通过维护这些信息，可以有效地进行任务调度和资源分配 . }