洛谷：P1065：作业调度方案


洛谷：P1065：作业调度方案

Table of Contents

题目

P1065：作业调度方案

分析

按照洛谷上相应的说明，这道题还是有难度的。我试了一下，确实如此——我也看了一些题解，试图理解思路。不过，最后我觉得，可能还是因为两个原因：

  1. 这道题目的说明有点“模糊”，它将一个可以封装在结构（或者说“对象”）中的数据给打散了，于是也就破坏了数据内在的关系。
  2. 很多题解也因此完全“模拟”了数据输入，并同时声明了大量必要的辅助数组来处理。也同样因此，这些辅助数组也很凌乱，只能依靠程序员强大的能力加以关联。

我的题解会借助AI，但我也会思考并给予指令，并在此基础上给出最人类的题解。

类声明

按照题意，这里有不少“对象”——或者严格说，类——需要声明或者说“设计”。类的设计没有最好的方法，我比较喜欢的，是从输入、输出、题目分析出发，从上到下来设计。

粗粗一看，这里就有好几个类：

工序

工序（Process）记录某个工件：在哪个机器上用多长时间完成。另外，为了方便记录时间，还可以加上起始、终止时间。

class Process
{
   public:
    int machine_id;  // 使用的机器ID
    int duration;    // 加工时间
    int start_time;  // 开始时间
    int end_time;    // 结束时间

    Process(int m_id = 0, int dur = 0)
        : machine_id(m_id), duration(dur), start_time(0), end_time(0)
    {
    }
};

这个类不复杂。

工件

工件也是一个很自然而然要声明的类。我们需要记录的是：工件号，有哪些工序，以及现在在哪道工序。

class Component
{
   public:
    int id;                     // 工件ID
    vector<Process> processes;  // 工序列表
    int current_process_index;  // 当前处理到哪道工序

    // 略去一些成员函数声明
};

看，这里就用到了上面声明的“工序”类。

机器

机器这个类非常复杂。因为它是将工件（和工序）连接起来的地方，也是最终调度要发生的地方。

我们需要记录的信息至少有：哪台机器，以及空闲/使用时间表。同时，它要完成如下几个和机器相关的工作：

  1. findEarliestAvailableTime：根据相应信息，找到可能使用该机器的最早的时间点。这个也是本题的核心算法。
  2. occupyTimeRange：标记某段时间内该机器已经被使用。
class Machine
{
   public:
    int id;                      // 机器ID
    vector<bool> time_occupied;  // 时间占用情况

    //... 
    // 找到最早可用的时间点
    int findEarliestAvailableTime(int earliest_possible_start, int duration)
    {
        int start_time = earliest_possible_start;
        while (true)
        {
            bool can_process = true;
            for (int t = start_time + 1; t <= start_time + duration; t++)
            {
                if (time_occupied[t])
                {
                    can_process = false;
                    start_time = t;
                    break;
                }
            }
            if (can_process)
            {
                return start_time;
            }
        }
    }

    // 标记时间段为已占用
    void occupyTimeRange(int start, int end)
    {
        // ...
    }
};

以下两点是显然的：

  1. 如果某段时间（从start_time+1开始，到start_time+duration为止）可行，那么这段时间上，该机器的时间段都不能是已被占用（或者说都要是“空”的）。
  2. 如果在这个时间段中，发现到某个t的时候，机器是被占用了的，那么start_time就调整到这个点，继续搜索。
调度员

最后一个需要完成的，是“调度员”这个类。我们可以不用声明这个类，但从纯粹OOP的角度来看，声明这个类会很有用，也很有趣。

这个类来完成的工作有：输入数据并初始化以上各个类的实例，以及作为核心功能的调度工作。

有了OOP的支持，我们在输入数据和初始化的时候，会很有“条理”，比如：

        // 读取每个工件的每道工序的机器编号
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                int machine_id;
                cin >> machine_id;
                components[i].processes[j].machine_id = machine_id;
            }
        }

        // 读取每个工件的每道工序的加工时间
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                int duration;
                cin >> duration;
                components[i].processes[j].duration = duration;
            }
        }

我们通过这个方法，将原本零散的数据进行了“结构”化。而核心的调度过程基本就是一个模拟过程：

flowchart TD A["获取当前的工件"]--> B["移动到下一个工序，获取工序号、机器、耗时"]--> C["找到该工件上个工序的结束时间"]--> D["据此找出该机器上最早的起始时间"]--> E["标记占用、更新工序的起讫时间"]--> F["更新最后的完成时间"]--> G["循环结束，返回最终的结束时间"] F-->|循环|A

答案

Solution

思考

本题设计很精妙，并同时经过了大量简化，让我们集中在“模拟”的过程。

从编程结果看，OOP的代码长度肯定是长的，但更清晰，也不会太影响执行速度。我比较喜欢。

上一篇 下一篇