动态规划问题 - 流水作业调度问题实验报告 - 《算法分析与设计》

定义
最优解结构性质
递归计算最优值
对递归式的分析
算法描述
代码实现

班级 : 计科1804 姓名 : 李珮钰学号 : 2018234060401

定义

N = {1, ,2 ...... n}全部作业的集合为
S 包含于 N ,即 S为N的子作业集合
T(S,t) 为机器M1开始加工S中作业时, 即可M2还在加工其他作业 , 从当前时刻等待t后M2空闲 , 的最优解

最优解结构性质

若π是T(N,0) 下的最优调度顺序 , 则所需要加工时间为a + T
设 : S = N - π(1) , 若T(S,b)是子问题的最优解对应的时间
- 假设 T(S,b) < T
- 则原问题最优解 a + T > a + T(S,b) , 使得a + T 是原问题的最优解矛盾
故原问题的最优解 , 就是子问题的最优解, 具有最优子结构的性质

递归计算最优值

T(S,t) = min{ a + T( S - {i} , bi + max{t - a , 0 } ) }
- max{t - a , 0 } 表示
- 如果当前作业在M1上的工作时间 , 大于当前M2上的作业时间 , 则当前在M1的作业完成之后无需等待直接进入M2
- 如果小于当前M2上的作业时间 , 还需要等待t - a 的时间

对递归式的分析

设π是T(N,0) 下的最优调度顺序
设i , j 分别是当前最优调度顺序下的第一个, 第二个作业, 即 π(1) = i , π(2) = j
T(S,t) = a + T( S - {i} , bi + max{t - a , 0 } )
= a + a + T( S - { i , j } , b + max{ b , max{t - a , 0 } - a } )
- 设 t = b + max{ b + max{ t - a , 0 } - a , 0 }
- 分析t
  t = b + max{ b + max{ t - a , 0 } - a , 0 }
```
 = b +   b - a +  max{ max{ t - a , 0 }   , a -  b   }
 =  b +   b - a - a + max{ max{ t , a  }   , a + a -  b   }
 = b +   b - a - a + max{  t , a     , a + a -  b   }
```
如果交换i, j的顺序 , 即 π(1) = j , π(2) = i
- 对应的t = b + b - a - a + max{ t , a , a + a - b }
由于当π(1) = i , π(2) = j 是最优调度顺序的前两个作业 , 交换 i , j 的调度顺序之后 , 作业时间一定大于等于之前的最优调度时间
即 t >= t

b + b - a - a + max{ t , a , a + a - b } >= b + b - a - a + max{ t , a , a + a - b } max{ t , a , a + a - b } >= max{ t , a , a + a - b } max{ a , a + a - b } >= max{ a , a + a - b } -ai - aj max{ -a , -b } >= max{ -a , -b } min{ a , b } >= min{ a , b }

min{ a , b } >= min{ a , b } , 表明对于一个最优的调度顺序
- 处于前边位置的作业在M1上的作业时间小于在M2上的作业时间 , 且按照在M1上作业时间从小到大执行
- 处于后边位置的作业在M1上的作业时间大于在M2上的作业时间 , 且按照在M2上作业时间从大到小执行

证明以上作业顺序满足 min{ a , b } >= min{ a , b } 该不等式

对于靠前的作业x,y 有 x在y之前执行

ax < bx , ay < by , ax < ay x= min{by,ax}

对于前后交接上的作业x,y 有 x在y之前执行

ax=by ,x = min{by,ax}

对于靠后的作业x,y 有 x在y之前执行

ax>bx , ay > by , bx > by , x = min{by,ax}

算法描述

对于输入的数据如果在M1上工作时间小于等于在M2上的工作时间 , 将作业放入sortedJob1作业数组中 , 否则放入sortedJob2 作业数组中
对sortedJob1中的作业按照M1上工作时间从小到大排序
对sortedJob2中的作业按照M2上工作时间从大到小排序
按照顺序执行sortedJob1中的作业 , 然后顺序执行sortedJob2 中的作业
- 定义 now1 , now2 分别为M1 , M2 最早空闲的时刻 , 初始化为0
- 首先让作业1执行
  - now1 = job1.a
  - now2 = job1.a + job1.b
- 然后循环执行1 , 2 类作业 , 对于jobx
  - now1 += jobx.a
    - 解释 : 在机器1上工作, 无需等待
  - now2 = now1 >= now2 ? now1 + sortedJob2[i].b : now2 + sortedJob2[i].b;
    - 解释 : M2已经空闲 M2不空闲等到now2M2空闲时候开始进入M2
所有作业执行完毕后now2 就是完成所有作业的最少时间

代码实现

/*
输入作业数n
输入n个作业的a,b    [在M1上的时间, 在M2上的时间]
- 对于a<=b 的作业放在前边
    对a从小到大排序

- a>b 的作业放到后边
    对b从大到小排序
*/
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const int N = 10;//作业数量
const int MAXTIME = 20;//在机器上工作的最大时间
typedef struct
{
    int a;//在M1上的工作时间
    int b;//在M2上的工作时间
    int type;//a<=b -> 1   , a>b = 2
}JOB;
bool cmp1(JOB x, JOB y) {//一类按a从小到大排序
    return x.a < y.a;
}
bool cmp2(JOB x, JOB y) {//二类按b从大到小排序
    return x.b > y.b;
}
int main()
{
    JOB jobs[N];
    JOB sortedJob1[N];
    JOB sortedJob2[N];
    int job1count = 0;
    int job2count = 0;
    srand(time(NULL));

    //生成数据
    for (int i = 0; i < N; i++) {
        jobs[i].a = rand() % 10 + 1;
        jobs[i].b = rand() % 10 + 1;
        jobs[i].type = jobs[i].a <= jobs[i].b ? 1 : 2;
        if (jobs[i].type == 1) {
            sortedJob1[job1count++] = jobs[i];
        }
        else {
            sortedJob2[job2count++] = jobs[i];
        }
    }

    //对数据排序
    sort(sortedJob1, sortedJob1 + job1count, cmp1);
    sort(sortedJob2, sortedJob2 + job2count, cmp2);

    //计算完成时间
    int now1 = 0, now2 = 0;
    now1 = sortedJob1[0].a;
    now2 = now1 + sortedJob1[0].b;
    for (int i = 1; i < job1count; i++) {//一类作业
        now1 += sortedJob1[i].a;//在机器1上工作, 无需等待
        now2 = now1 >= now2 ? now1 + sortedJob2[i].b : now2 + sortedJob2[i].b;
        //                      M2已经空闲                  M2不空闲等到now2M2空闲时候开始进入M2
    }
    for (int i = 0; i < job2count; i++) {//二类作业
        now1 += sortedJob1[i].a;//在机器1上工作, 无需等待
        now2 = now1 >= now2 ? now1 + sortedJob2[i].b : now2 + sortedJob2[i].b;
        //                      M2已经空闲                  M2不空闲等到now2M2空闲时候开始进入M2
    }

    printf("作业最优调度时间为 : %d", now2);
    return 0;
}