算法设计实验报告题目：独立任务最优调度问题
年月日
一、实验题目
独立任务最优调度问题
二、实验目的
问题描述：用2 台处理机A和B处理n个作业。

设第i个作业交给机器A 处理时需要时间a i，若由机器B来处理，则需要时间b i。

由于各作业的特点和机
器的性能关系，很可能对于某些i，有a i=>b i，而对于某些 j，j≠i，有a j<b j。

既不能将一个作业分开由 2 台机器处理，也没有一台机器能同时处理2 个作业。

设计一个动态规划算法，使得这2台机器处理完这n个作业的时间最短(从任何一台机器开工到最后一台机器停工的总时间)。

研究一个实例：(a1,a2,a3,a4,a5,a6)＝(2,5,7,10,5,2)；(b1,b2,b3,b4,b5,b6)＝(3,8,4,11,3,4)。

三、实验内容
算法设计：对于给定的两台处理机A和B处理n个作业，找出一个最优调度方案使两台机器处理完这n个作业的时间最短。

数据输入：由文件input.txt提供输入数据。

文件的第一行是一个正整数n，表示要处理n个作业。

在接下来的2行中，每行n个正整数，分别表示处理机A和B处理第个作业需要的处理时间。

结果输出:将计算出的最短处理时间输出到文件output.txt。

输入文件示例输出文件示例
input.txt output.txt
6 15
2 5 7 10 5 2
3 8
4 11 3 4
四、实验原理
首先要注意每个作业仅需要处理一次就行，不需要被机器A和B各处理一遍
采用动态规划;定义t[i][j]为：表示完成i个作业且机器A花费j时间的条件下机器B所花费时间的最小值，那么t[i][j] = min{t[i-1][j] + b[i], t[i-1][j-a[i]]}。

假设前i-1件已经被处理了，那么第 i 件作业由谁来处理可以分两种情况：
1）由机器A处理i，则机器B的时间为 t[i-1][j-a[i]];
2）由机器B处理i，则机器B的时间为 t[i-1][j]+b[i];
3）特殊情况，如果j < a[i],则不可能由机器A来完成，此时t[i][j] = t[i-1][j]+b[i]；
最终t[i][j] 选择1）和2）中较小的一个，即t[i][j] = min{t[i-
1][j]+b[i], t[i-1][j-a[i]]}。

五、实验步骤
1）实验环境：Microsoft Visual Studio 2010
2）编写代码，在程序文件夹下建立input.txt，output.txt，输入题目，不断调试运行。

3）实验代码
#include<stdio.h>
#define N 100
int main()
{
int i,j,n;
int sum=0;
int a[N]={0},b[N]={0},t[N][N]={0};
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d",&n);
for(i=0;i<n;i++) {
scanf("%d",&a[i]);
sum+=a[i];
}
for(j=0;j<n;j++) {
scanf("%d",&b[j]);
}
for(i=1;i<=n;i++) {
for(j=0;j<=sum;j++) {
if(j<a[i-1]) //此时交给B
t[i][j]=t[i-1][j]+b[i-1];
else if(t[i-1][j-a[i-1]]>t[i-1][j]+b[i-1])
t[i][j]=t[i-1][j]+b[i-1];
else
t[i][j]=t[i-1][j-a[i-1]];
}
}
int min=1000000;
for(i=0;i<=sum;i++) {
j=t[n][i]>i?t[n][i]:i;
if(min>j) {
min=j;
}
}
printf("%d\n",min);
return 0;
}
六、实验结果分析
本次实验采用动态规划法完成，由于两机器可以同时工作，A的运行对B的运行没有影响，确定了第i件任务由谁来完成，B花的时间最短，然后再从A和B中取得最晚的停机时间，就可以确定A和B完成任务的最短时间。

所以问题满足最优子结构性质。

算法复杂度：由于对于每个任务，需要遍历A所花的所有时间，设任务有n
个，A花费时间总和为m，计算t[i][j]花费的时间为常数级别，所以时间复杂度为O(nm),空间复杂度就是一个二维数组nm。

运行结果如下：。