回溯法之流水作业调度问题
1.问题：流水作业调度问题：每一个作业Ji都有两项任务分别在2台机器上完成。每个作业必须先有机器1处理，然后再由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理时间。则所有作业在机器2上完成处理时间和f=F2i，称为该作业调度的完成时间和。
| 作业编号 | 1 | 2 | 3 | 4 |
| M1 | 5 | 12 | 4 | 8 |
| M2 | 6 | 2 | 14 | 7 |
2.设计思路：每一个作业需要先在M1(机器1)上进行求解，M1上的时间是连续的，也就是每一个作业在M1上的执行不需要等待；而作业在M2(机器2)上的执行时间需要判断是否进行等待：如果作业j在M1上的执行时间<作业i在M2上的执行时间，也就是说作业j在M1上执行完成了，而作业i还在使用M2，此时需要等待；否则直接在M2上执行作业j,Max(f1,f2[i])+b[x[i]];其中f1是当前作业在M1上的执行时间，f2数组是作业在M2上的执行时间，所有的时间都是包括前面作业的执行时间，数组a是作业在M1上的执行时间，数组b是作业在M2上的执行时间，如上图；每遍历完一个解空间就要回溯，也就是撤销对当前作业的选择，以便再选择其他作业：
3.代码;
/*回溯法之流水作业调度问题*/
#include
#include
#define MAX 1000
#define max(x,y) ((x)>(y)? (x):(y)) //自定义max函数，求解x,y中的最大值
int n=4; //作业数
int a[MAX]={0,5,12,4,8} ; //作业在M1上的执行时间，从数组下标1开始
int b[MAX]={0,6,2,14,7} ; //作业在M2上的执行时间，从数组下标1开始
int bestf; //存放最优的调度时间
int f1;
int f2[MAX];
int x[MAX]; //当前的调度方案
int bestx[MAX]; //存放当前作业的最优调度方案
void swap(int &x,int &y) //交换x,y
{int temp=x;x=y;y=temp;}
void dfs(int i) //从第i层开始使用深度优先遍历
{if(i>n) //达到叶子节点，产生一种调度方案 {if(f2[n] 4.运行结果：
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！