运筹学中的排序问题算法

Question

工件按时间在线到达，即一个工件只有被释放之后才能知道它的一切信息，就是时间在线排序中的在线LPT算法，求算法代码及每一步步骤说明，并举例

Answer 1

引自免费微信小程序：皆我百晓生

在线LPT（Longest Processing Time First）算法是一种解决在线排序问题的方法，其基本思想是每次选择剩余加工时间最长的工件进行处理。以下是C++实现在线LPT算法的代码及其详细的步骤说明。

首先，我们需要定义一个结构体或类来表示工件，包含工件的ID、到达时间和加工时间。

struct Job {
    int id; // 工件ID
    int arrival_time; // 到达时间
    int processing_time; // 加工时间
};

接下来，我们编写一个函数来执行在线LPT算法。

#include <iostream>
#include <vector>
#include <algorithm>

std::vector<int> online_LPT(std::vector<Job>& jobs) {
    std::vector<int> schedule; // 用于存储调度结果
    std::priority_queue<Job, std::vector<Job>, std::greater<Job>> pq; // 使用优先队列按照剩余加工时间降序排列

    for (const auto& job : jobs) {
        // 当前工件到达，将其加入到优先队列中
        pq.push(job);

        // 如果当前时间大于等于工件的到达时间，则可以开始加工
        while (!pq.empty() && pq.top().arrival_time <= schedule.size()) {
            // 添加当前正在加工的工件ID到调度结果中
            schedule.push_back(pq.top().id);
            // 减少当前正在加工的工件的剩余加工时间
            pq.top().processing_time -= 1;
            // 如果加工完成，则移除该工件
            if (pq.top().processing_time == 0) {
                pq.pop();
            } else {
                // 否则，更新优先级队列
                pq.update pq.top();
            }
        }
    }

    return schedule;
}

下面是算法的详细步骤：

1. 初始化：创建一个空调度列表schedule和一个优先队列pq，其中优先队列按照剩余加工时间降序排列。
2. 遍历每个工件： a. 将新到达的工件添加到优先队列中。 b. 检查优先队列顶部的工件是否可以在当前时间开始加工（即其到达时间是否小于或等于当前已安排的工作数）。如果是，则执行以下操作：
   • 将顶部工件的ID添加到调度列表schedule中。
   • 减少顶部工件的剩余加工时间。
   • 如果顶部工件的剩余加工时间变为0，则从优先队列中移除该工件；否则，更新优先队列。
3. 完成遍历后，返回调度列表schedule。

例如，考虑以下工件序列：

• 工件1：ID=1, 到达时间=1, 加工时间=5
• 工件2：ID=2, 到达时间=3, 加工时间=3
• 工件3：ID=3, 到达时间=4, 加工时间=4

应用在线LPT算法，得到的调度顺序为：[1, 3, 1, 2, 1, 3]。解释如下：

• 第1时刻，工件1到达，添加到优先队列：[1(5)]
• 第2时刻，无新工件，继续加工工件1：[1]
• 第3时刻，工件2到达，添加到优先队列：[1(4), 2(3)]
• 第4时刻，工件3到达，添加到优先队列：[1(3), 2(3), 3(4)]
• 第5时刻，开始加工工件3：[1(3), 2(3)]
• 第6时刻，继续加工工件3：[1(3), 2(2)]
• 第7时刻，完成工件3，开始加工工件1：[1, 2(2)]
• 第8时刻，继续加工工件1：[1, 2(1)]
• 第9时刻，完成工件1，开始加工工件2：[1, 2]
• 第10时刻，完成工件2，此时所有工件都已完成。