-->
当前位置:首页 > 题库 > 正文内容

程序填空题:流水作业调度问题(分支限界法)

Luz4年前 (2021-05-10)题库1724
有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

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。