【算法设计与设计】流水作业调度问题

做一个柔情的程序猿 2020-09-30

1448

读书

流水作业调度问题

● ○ ●

Flow Job Scheduling Problem

● ○ ●

“加工顺序问题”又被称为“批处理作业调度问题”。

应如何在两机器上安排生产，使得第一个工件从在M1上加工开始到最后一个工件在M2上加工完所需的总加工时间最短？关于此（类）问题的回溯法求解被作为经典案例在很多教材或参考文献中出现，现要求设计求解此问题的动态规划算法。

❉❉❉❉❉❉❉❉❉❉

问题

有n个作业，需要在由2台机器M1和M2组成的流水线上进行加工，每个作业的顺序都是先在M1上加工，然后在M2上加工，M1和M2加工作业i所需要的时间分别为a[i]和b[i]。可以合理地安排作业的执行顺序，使得从第1个作业在M1上加工开始，到最后一个作业在M2上加工完成为止，所用的总时间最少，求这个最少时间。

问题描述

背景条件：两台机器，分别为机器1和机器2，多个作业，每个作业必须在机器1完成的基础上，才能在机器2加工。根据机器和作业分别有以下结论：

结论1：针对机器，在作业未完成的条件下，机器1的状态是连续工作，但机器2的状态可以是空闲和工作;

结论2：针对作业，n个作业，则有n！种排列可能；

结论3：作业的加工时间，是最后一个作业在机器2上的完成时间。

分析问题

根据问题概述所得的3个结论，有以下需要实现：

1.需要获得每个作业的在2台机器上所需的工作时间

2.对每一种可能进行穷举，以实现所有的可能

3.建立每一种可能的工作流程和时间计算模型

4.打印所有的可能，并对所有的可能所得的结果进行筛选，获得最优结果

解决策略

1. 将作业分为F和G两部分，F中的作业满足a[i] < b[i]，G中的作用满足a[i]>=b[i]

2. 将F中的作业按a排升序，G中的作业按b排降序

3. 依次执行F和G中的作业，花费的总时间最少

解决问题

根据前面的分析，具体化问题，假设题目如下：

对以上的几点，其中1，2，4点：

1和4 只是简单的逻辑处理，

2可以通过调用全排列函数进行实现，则有(1,2,3)、(1,3,2)、(2,1,3)、(2,3,1)、(3,1,2)、(3,2,1)共3！=6种可能；

在第3点中，需要建立计算模型：

定义两个变量sum_m1,sum_m2，分别用于存储机器1和机器2的工作记录，

取其中一种可能(1,2,3),其中，作业1在M1的时间为HK1_M1,在M2的时间为HK1_M2,

定义两个列表，f1和f2,f1[i],f2[i]分别代表作业i在机器1，机器2的完成的那刻的时间（时间刻度），以此类推;

情景模拟开始，有如下图

将作业1投入到机器M1时，则sum_m1 = HK1_M1=2，f1[1]=2

根据之前结论，机器2有空闲和工作两种状态：

这里是机器2是空闲的状态，所以sum_m2=sum_m1+HK1_M2=3,f2[1]=3

但是如果机器2不是空闲的状态的话，则需要等待，如下，当作业1在机器M1完成时，机器M2正在工作，所以需要等待

所以可以有以下结论：

当sum_m1>=sum_m2时，sum_m2=sum_m1+HK[i]_M2

否则，即机器2正在工作，已在机器M1完成的作业需要等待机器M2

sum_m2=sum_m2+HK[i]_M2,f2[i]=sum_m2

代码实现

#include <bits/stdc++.h>
using namespace std;
struct st {int a, b;}t;
vector<st> f, g;
int n, ans1, ans2;
bool cmp1(st x, st y) {
    return x.a < y.a;
}
bool cmp2(st x, st y) {
    return x.b > y.b;
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> t.a >> t.b;
        if (t.a < t.b)
            f.push_back(t);
        else
            g.push_back(t);
    }
    sort(f.begin(), f.end(), cmp1);
    sort(g.begin(), g.end(), cmp2);
    for (auto i : f) {
        ans1 += i.a;
        ans2 = max(ans1,ans2) + i.b;
    }
    for (auto i : g) {
        ans1 += i.a;
        ans2 = max(ans1,ans2) + i.b;
    }
    cout << ans2 << endl;
    return 0;
}