作业调度程序

期末考查 作业调度问题

班级 08通信一班 学号 姓名 成绩 分

一、设计目的

1. 掌握分枝-限界法算法的解题的基本思想和设计方法;

2. 理解分枝-限界法算法中的限界函数应遵循正确，准确，高效的设计原则; 3. 掌握先进先出分枝-限界算法思想（FIFOBB）解决带期限作业调度问题。

二、设计内容

给定一个带期限的作业排序问题 ,n=4,(p1,p2,p3,p4) =(5,10,6,3), (t1,t2,t3,t4)=(1,3,2,1), (d1,d2,d3,d4)= (1,2,1,1), 应用FIFOBB求使总罚款 数最小的可行作业集J, 要求:

1）阐述c’(X)和u(X)的设计思路，U的初始值;

2）针对解向量变长格式, 画出FIFOBB的生成的部分状态空间树, 按活节点生成顺序给节点编号，在各节点位置给出c(X)和U的值，给每条边标记选择的作业编号; 3）阐述c(X)=U的处理方案, 可行解的判断方案；

4）阐述你程序中的主要数据类型、数据变量和功能模块。

5）编成并上机实现FIFOBB程序, 实现对不同作业排序问题实例的求解，问题实例的输入数据存储在case.txt文件中

三、参考数据与子程序

1.typedef struct{

int time,date,parent,x; float u,c;

}TNODE;//定义队列结点结构体，其中time为结点需要的单位处理时间;date为结点的截止期限;parent为结点的父结点;u为结点的最小成本上界;c为结点的估计成本。 2.void FIFOBB(int T);//先进先出分枝-限界子函数 3.void cost(int m,int E);//求估计成本子函数 4.void insequense(int m,int E);//进队列子函数 5.void outsequense(int m,int E);//出队列子函数 6.int seqempty();//判断队列为空子数

四、

…..

附：程序模块的源代码

#include typedef struct{

int time,deadtime,parent,x; float u,c; }TNODE;

int d[10],t[10],rear,front,s,n; TNODE q[40],temp;

float p[10],tempu,tempcost,MAX=500,sum,U,e=0.5;

void main() {

void FIFOBB(int T); int i;

freopen(\"D:\\\\case1.txt\ scanf(\"%d\ for(i=0;iscanf(\"%f\ sum+=p[i]; }

for(i=0;iscanf(\"%d\ }

for(i=0;iscanf(\"%d\ }

q[0].time=0;q[0].deadtime=0;q[0].parent=-1;q[0].x=-1; q[0].u=sum; q[0].c=0; U=sum+e;rear=front=1; FIFOBB(0); }

void FIFOBB(int T) { int m,w;

void insequense(int k,int E); void cost(int m,int E); int outsequense(); int seqempty(); int E=T;

for(m=q[E].x+1;mtempu=q[E].u-p[m]; if(tempcostinsequense(m,E); }

if(seqempty()) {

printf(\"the least pay is : %.1f\\n\ int t=q[s].parent;

printf(\"%d,\

1

while(q[t].parent!=-1) { printf(\"%d,\ t=q[t].parent; } } else {

w=outsequense(); FIFOBB(w); } }

void cost(int m,int E) {

//(q[E].deadtime>d[m])?temp.deadtime=q[E].deadtime:temp.deadtime=d[m]; int i;

//printf(\"%d\\n\

if(q[E].deadtime>d[m]) temp.deadtime=q[E].deadtime; else

temp.deadtime=d[m];

if(t[m]+q[E].time>temp.deadtime) { tempcost=MAX; } else if((m-q[E].x)!=1) { tempcost=q[E].c; for( i=q[E].x+1;ielse { tempcost=q[E].c;

// printf(\"%d: %.0f\\n\ } }

void insequense(int m,int E) {

q[rear].c=tempcost;q[rear].time=t[m]+q[E].time; q[rear].parent=E;q[rear].deadtime=temp.deadtime;

2

q[rear].u=tempu;q[rear].x=m;

//printf(\"{% .0f,%d,%.0f }\\n\

if(q[rear].uU=q[rear].u+e;s=rear; // printf(\"%.1f\\n\ }

rear++;//printf(\"%d\\n\}

int outsequense() {

int sum1=front; front++; return sum1; }

int seqempty() {

if(front==rear) return 1; else return 0; }

3