程序填空题:流水作业调度问题(分支限界法)
有n个作业(编号为1~n)要在由两台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工,然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi(1≤i≤n)。
流水作业调度问题要求确定这n个作业的最优加工顺序,使得从第一个作业在机器M1上开始加工,到最后一个作业在机器M2上加工完成所需的时间最少。可以假定任何作业一旦开始加工,就不允许被中断,直到该作业被完成,即非优先调度。
### 输入格式:
第一行输入作业数n,接着的n行分别为在M1和M2加工各作业所需的时间。
### 输出格式:
先输出所需加工时间,再输入最优调度方案。
### 输入样例1:
```in
4
5 6
12 2
4 14
8 7
```
### 输出样例1:
```out
33
3 1 4 2
```
```c++
#include
#include
#include
#include
using namespace std;
#define max(x,y) ((x)>(y)?(x):(y))
#define INF 0x3f3f3f3f //定义∞
#define MAX 21
int n; //作业数
int a[MAX]={0}; //M1上的执行时间,不用下标0的元素
int b[MAX]={0}; //M2上的执行时间,不用下标0的元素
int bestf=INF; //存放最优调度时间
int bestx[MAX]; //存放当前作业最佳调度
int total=1; //结点个数累计
struct NodeType //队列结点类型
{
int no; //结点编号
int x[MAX]; //x[i]表示第i步分配作业编号
int y[MAX]; //y[i]=1表示编号为i的作业已经分配
int i; //步骤编号
int f1; //已经分配作业M1的执行时间
int f2; //已经分配作业M2的执行时间
int lb; //下界
bool operator<(const NodeType &s) const //重载<关系函数
{
return lb>s.lb; //lb越小越优先出队
}
};
void bound(NodeType &e); //求结点e的限界值
void bfs(); //求解流水作业调度问题
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i]>>b[i];
bfs();
printf("%d\n",bestf);
for (int k=1;k<=n;k++)
printf("%d ",bestx[k]);
return 0;
}
void bound(NodeType &e) //求结点e的限界值
{
int sum=0;
for (int i=1;i<=n;i++) //扫描所有作业
if (e.y[i]==0) sum+=b[i]; //仅累计e.x中还没有分配的作业的b时间
e.lb=e.f1+sum;
}
void bfs() //求解流水作业调度问题
{
NodeType e,e1;
priority_queue qu;
memset(e.x,0,sizeof(e.x)); //初始化根结点的x
memset(e.y,0,sizeof(e.y)); //初始化根结点的y
e.i=0; //根结点
e.f1=0;
e.f2=0;
bound(e);
e.no=total++;
qu.push(e); //根结点进队列
while (!qu.empty())
{
e=qu.top(); qu.pop(); //出队结点e
e1.i=e.i+1; //扩展分配下一个步骤的作业,对应结点e1
for (int j=1;j<=n;j++) //考虑n个作业
{
if (e.y[j]==1) continue; //作业j是否已分配,若已分配,跳过
for (int i1=1;i1<=n;i1++) //复制e.x得到e1.x
e1.x[i1]=e.x[i1];
for (int i2=1;i2<=n;i2++) //复制e.y得到e1.y
e1.y[i2]=e.y[i2];
e1.x[e1.i]=j; //为第i步分配作业j
e1.y[j]=1; //表示作业j已经分配
e1.f1=;
e1.f2=;
bound(e1);
if () //达到叶子结点
{
if () //比较求最优解
{
bestf=e1.f2;
for (int j1=1;j1<=n;j1++)
bestx[j1]=e1.x[j1];
return; //找到一个解后结束
}
}
if () //剪枝
{
e1.no=total++; //结点编号增加1
qu.push(e1);
}
}
}
}
```
答案:
第1空:e.f1+a[j]
第2空:max(e.f2,e1.f1)+b[j]
第3空:e1.i==n
第4空:e1.f2
第5空:e1.f2<=bestf
流水作业调度问题要求确定这n个作业的最优加工顺序,使得从第一个作业在机器M1上开始加工,到最后一个作业在机器M2上加工完成所需的时间最少。可以假定任何作业一旦开始加工,就不允许被中断,直到该作业被完成,即非优先调度。
### 输入格式:
第一行输入作业数n,接着的n行分别为在M1和M2加工各作业所需的时间。
### 输出格式:
先输出所需加工时间,再输入最优调度方案。
### 输入样例1:
```in
4
5 6
12 2
4 14
8 7
```
### 输出样例1:
```out
33
3 1 4 2
```
```c++
#include
#include
#include
#include
using namespace std;
#define max(x,y) ((x)>(y)?(x):(y))
#define INF 0x3f3f3f3f //定义∞
#define MAX 21
int n; //作业数
int a[MAX]={0}; //M1上的执行时间,不用下标0的元素
int b[MAX]={0}; //M2上的执行时间,不用下标0的元素
int bestf=INF; //存放最优调度时间
int bestx[MAX]; //存放当前作业最佳调度
int total=1; //结点个数累计
struct NodeType //队列结点类型
{
int no; //结点编号
int x[MAX]; //x[i]表示第i步分配作业编号
int y[MAX]; //y[i]=1表示编号为i的作业已经分配
int i; //步骤编号
int f1; //已经分配作业M1的执行时间
int f2; //已经分配作业M2的执行时间
int lb; //下界
bool operator<(const NodeType &s) const //重载<关系函数
{
return lb>s.lb; //lb越小越优先出队
}
};
void bound(NodeType &e); //求结点e的限界值
void bfs(); //求解流水作业调度问题
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i]>>b[i];
bfs();
printf("%d\n",bestf);
for (int k=1;k<=n;k++)
printf("%d ",bestx[k]);
return 0;
}
void bound(NodeType &e) //求结点e的限界值
{
int sum=0;
for (int i=1;i<=n;i++) //扫描所有作业
if (e.y[i]==0) sum+=b[i]; //仅累计e.x中还没有分配的作业的b时间
e.lb=e.f1+sum;
}
void bfs() //求解流水作业调度问题
{
NodeType e,e1;
priority_queue
memset(e.x,0,sizeof(e.x)); //初始化根结点的x
memset(e.y,0,sizeof(e.y)); //初始化根结点的y
e.i=0; //根结点
e.f1=0;
e.f2=0;
bound(e);
e.no=total++;
qu.push(e); //根结点进队列
while (!qu.empty())
{
e=qu.top(); qu.pop(); //出队结点e
e1.i=e.i+1; //扩展分配下一个步骤的作业,对应结点e1
for (int j=1;j<=n;j++) //考虑n个作业
{
if (e.y[j]==1) continue; //作业j是否已分配,若已分配,跳过
for (int i1=1;i1<=n;i1++) //复制e.x得到e1.x
e1.x[i1]=e.x[i1];
for (int i2=1;i2<=n;i2++) //复制e.y得到e1.y
e1.y[i2]=e.y[i2];
e1.x[e1.i]=j; //为第i步分配作业j
e1.y[j]=1; //表示作业j已经分配
e1.f1=;
e1.f2=;
bound(e1);
if () //达到叶子结点
{
if () //比较求最优解
{
bestf=e1.f2;
for (int j1=1;j1<=n;j1++)
bestx[j1]=e1.x[j1];
return; //找到一个解后结束
}
}
if () //剪枝
{
e1.no=total++; //结点编号增加1
qu.push(e1);
}
}
}
}
```
答案:
第1空:e.f1+a[j]
第2空:max(e.f2,e1.f1)+b[j]
第3空:e1.i==n
第4空:e1.f2
第5空:e1.f2<=bestf