流水线作业调度最小时间问题
实验名称:流水线作业调度问题
n个作业{1、2、…、n},要在3台机器上处理。每个作业必须先由机器1处理,再由机器2处理,最后由机器3处理。问如何确定这n个作业的调度次序,使得所需时间最少?设计一个回溯算法。
算法设计思想:
因为每个作业必须保证:先在机器1上处理,再在机器2上处理,最后在机器3上处理。即该批处理作业调度问题称为流水线调度问题更合适,要从n个作业的所有排列中找出有最小完成时间的作业调度,所以该批处理作业调度问题的解空间树是一颗排列树。
按照回溯法搜索排列树的算法框架,设开始时x=[1,2, … , n]是所给的n个作业,则相应的排列树由x[1:n]的所有排列(所有的调度序列)构成。
二维数组M是输入作业的处理时间,bestf记录当前最小完成时间,bestx记录相应的当前最佳作业调度。
设置一个递归函数Backtrack:
当i>n时,算法搜索至叶子结点,得到一个新的作业调度方案。此时算法适时更新当前最优值和相应的当前最佳调度。
当i<n时,当前扩展结点位于排列树的第(i-1)层,此时算法选择下一个要安排的作业,以深度优先方式递归的对相应的子树进行搜索,对不满足上界约束的结点,则剪去相应的子树。
#include<iostream>
using namespace std;
int x[100]; //当前作业调度————其中一种排列顺序
int bestx[100]; //当前最优作业调度
int m[100][100];各作业所需的处理时间
//M[j][i]代表第j个作业在第i台机器上的处理时间
int f1=0;//机器1完成处理时间
int f2=0;//机器2完成处理时间
int f3=0;// 机器3完成处理时间
int cf=0;//完成时间和
int bestf=10000;//当前最优值,即最优的处理时间和
int n;//作业数
void swap(int &a,int &b)
{ int temp=a;
a=b;
b=temp;
}
void Backtrack(int t)
{ //t用来指示到达的层数(第几步,从0开始),同时也指示当前执行完第几个任务/作业
int tempf,j;
int tempf3;
if(t>n) //到达叶子结点,搜索到最底部
{
if(cf<bestf)
{
for(int i=1; i<=n; i++)
bestx[i]=x[i];//更新最优调度序列
bestf=cf;//更新最优目标值
}
}
else //非叶子结点
{
for(j=t; j<=n; j++) //j用来指示选择了哪个任务/作业(也就是执行顺序)
{
f1+=m[x[j]][1];//选择第x[j]个任务在机器1上执行,作为当前的任务
tempf=f2;//保存上一个作业在机器2的完成时间
f2=(f1>f2?f1:f2)+m[x[j]][2];//保存当前作业在机器2的完成时间
tempf3=f3;//保存上一个作业在机器2的完成时间
f3=(f2>f3?f2:f3)+m[x[j]][3];//保存当前作业在机器2的完成时间
cf=f3;
//如果该作业处理完之后,总时间已经超过最优时间,就直接回溯。
//剪枝函数
if(cf<bestf) //总时间小于最优时间
{ swap(x[t],x[j]); //交换两个作业的位置,把选择出的原来在x[j]位置上的任务调到当前执行的位置x[t]
Backtrack(t+1); //深度搜索解空间树,进入下一层
swap(x[t],x[j]); //进行回溯,还原,执行该层的下一个任务 //如果是叶子节点返回上一层
}
//回溯需要还原各个值
f1-=m[x[j]][1];
f2=tempf;
f3=tempf3;
cf-=f3;
} }}
int main()
{
int i,j;
cout<<"请输入作业数:"<<endl;
cin>>n;
cout<<"请输入在各机器上的处理时间"<<endl;
for(i=1; i<=3; i++) //i从1开始
for(j=1; j<=n; j++)
cin>>m[j][i];//第j个作业,第i台机器的时间值
for(i=1; i<=n; i++)
x[i]=i;//初始化当前作业调度的一种排列顺序
Backtrack(1);
cout<<"调度作业顺序:"<<endl;
for(i=1; i<=n; i++)
cout<<bestx[i]<<" ";
cout<<endl;
cout<<"最小的处理时间:"<<endl;
cout<<bestf;
return 0;
}
/*
测试数据:
4
3 5 2 6
4 2 5 1
2 1 2 1
4
5 3 2 6
4 2 5 1
2 1 2 1
4
5 3 2 1
4 2 5 1
2 1 2 1
*/