一个更快的带有期限的作业排序问题

#include

#include

#include

int FIND(int *parent,int i)

{//查找含有元素i的树根，使用压缩规则去压缩由i到根j的所有结点int j,k,t;

j=i;

while(parent[j]> 0) j=parent[j];//找根

k=i;

while(k!=j){//压缩由i到根j的结点

t=parent[k];

parent[k]=j;

k=t;

}

return j;

}

void UNION(int *parent,int i,int j)

{//使用加权规则合并根为i和j的两个集合

int x;

x=parent[i]+parent[j];

if(parent[i]> parent[j]){//i的结点少

parent[i]=j;

parent[j]=x;

}

else{//j的结点少

parent[j]=i;

parent[i]=x;

}

}

int MIN(int n,int m)

{//求n和m的最小值

if(n> m) return m;

else return n;

}

int FJS(int *D,int n,int b,int *J,int *Q)

{//找J(n)的最优解，并返回最优解的个数

int i,*F,*p,j,l,m,k;

F=(int *)malloc((b+1)*sizeof(int));

p=(int *)malloc((b+1)*sizeof(int));

for(i=0;i <=b;i++){//将树置初值

F[i]=i;

p[i]=-1;

}

k=0;//初始化J

for(i=1;i <=n;i++)

{//使用贪心规则

j=FIND(p,MIN(n,D[i]));

if(F[j]!=0)

{//选择作业i

k=k+1;

J[k]=i;

Q[F[j]]=i;

m=F[j];

l=FIND(p,F[j]-1);

UNION(p,l,j);

F[j]=F[l];

}

}

return k;//返回最优解的个数

}

int MAXMUM(int i,int j)

{//求i和j的最大值

if(i> j) return i;

else return j;

}

int MAX(int *D,int i, int j)

{//D(1:n)是含有n个元素数组，求出D(i,j)中的最大值并返回int max,mid,max1,max2;

if(i==j) max=D[i];

else

if(i==j-1)

if(D[i]

else max=D[i];

else{

mid=(i+j)/2;

max1=MAX(D,i,mid);

max2=MAX(D,mid+1,j);

max=MAXMUM(max1,max2);

}

return max;

}

void Insertionsort(int *D,int n)

{//将D中的元素按非增次序分类

int j,item,i;

D[0]=65525; //设置监视哨

for(j=2;j <=n;j++){

item=D[j];

i=j-1;

while(item> D[i]){

D[i+1]=D[i];

i=i-1;

}

D[i+1]=item;

}

}

int main()

{

int *D,*J,*Q,*p,n,b,i,k;

cout<<" 用贪心法解决带有限期的作业排序问题"<

cout<< "请输入作业的数目: ";

cin>>n;

D=(int*)malloc((n+1)*sizeof(int));

p=(int*)malloc((n+1)*sizeof(int));

cout<<"请输入每个作业的效益值"<

for(i=1;i <=n;i++)

cin>>p[i];

Insertionsort(p,n);

cout<<"按效益值非增排序后各作业为: "<

cout<<"作业序号效益值"<

for(i=1;i <=n;i++)

cout<<" "<

cout<< "请输入按效益值非增排序后各作业的截止时间: "<

for(i=1;i <=n;i++)

cin>>D[i];

b=MIN(n,MAX(D,1,n));

J=(int*)malloc((b+1)*sizeof(int));

Q=(int*)malloc((b+1)*sizeof(int));

for(i=1;i <=b;i++)

Q[i]=-1;

k=FJS(D,n,b,J,Q);

cout<< "-----------------------------本问题的最优解---------------------------------"<

for(i=1;i <=k;i++)

cout<

cout<< "-----------------------------各作业的执行次序-------------------------------"<

for(i=1;i <=b;i++)

if(Q[i]!=-1)

cout<

return 0;

}

一个更快的带有期限的作业排序问题

#include #include #include int FIND(int *parent,int i) {//查找含有元素i的树根，使用压缩规则去压缩由i到根j的所有结点int j,k,t; j=i; while(parent[j]> 0) j=parent[j];//找根 k=i; while(k!=j){//压缩由i到根j的结点 t=parent[k]; parent[k]=j; k=t; } return j; } void UNION(int *parent,int i,int j) {//使用加权规则合并根为i和j的两个集合 int x; x=parent[i]+parent[j]; if(parent[i]> parent[j]){//i的结点少 parent[i]=j; parent[j]=x; } else{//j的结点少 parent[j]=i; parent[i]=x; } } int MIN(int n,int m) {//求n和m的最小值 if(n> m) return m; else return n; } int FJS(int *D,int n,int b,int *J,int *Q) {//找J(n)的最优解，并返回最优解的个数 int i,*F,*p,j,l,m,k; F=(int *)malloc((b+1)*sizeof(int)); p=(int *)malloc((b+1)*sizeof(int));

for(i=0;i <=b;i++){//将树置初值 F[i]=i; p[i]=-1; } k=0;//初始化J for(i=1;i <=n;i++) {//使用贪心规则 j=FIND(p,MIN(n,D[i])); if(F[j]!=0) {//选择作业i k=k+1; J[k]=i; Q[F[j]]=i; m=F[j]; l=FIND(p,F[j]-1); UNION(p,l,j); F[j]=F[l]; } } return k;//返回最优解的个数 } int MAXMUM(int i,int j) {//求i和j的最大值 if(i> j) return i; else return j; } int MAX(int *D,int i, int j) {//D(1:n)是含有n个元素数组，求出D(i,j)中的最大值并返回int max,mid,max1,max2; if(i==j) max=D[i]; else if(i==j-1) if(D[i]

排序作业答案

10.2设待排序的关键字序列为(15， 21， 6， 30， 23， 6′， 20， 17)，试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次比较。(1) 直接插入排序(2) 希尔排序(增量为5，2，1) (3) 起泡排序(4) 快速排序(5) 直接选择排序(7) 堆排序(8)二路归并排序 (9)基数排序 【解答】(1) 直接插入排序 初始关键字序列： 15，21，6，30，23，6′，20，17 第一趟直接插入排序：【15，21】 第二趟直接插入排序：【6，15，21】 第三趟直接插入排序：【6，15，21，30】 第四趟直接插入排序：【6，15，21，23，30】 第五趟直接插入排序：【6，6′，15，21，23，30】 第六趟直接插入排序：【6，6′，15，20，21，23，30】 第七趟直接插入排序：【6，6′，15，17，20，21，23，30】 (2) 希尔排序(增量为5，2，1) 初始关键字序列： 15，21，6，30，23，6′，20，17 第一趟希尔排序： 6′，20，6，30，23，15，21，17 第二趟希尔排序： 6′，15，6，17，21，20，23，30 第三趟希尔排序： 6′，6，15，17，20，21，23，30 (3) 起泡排序 初始关键字序列：15，21，6，30，23，6′，20，17 第一趟起泡排序：15，6，21，23，6′，20，17，30 第二趟起泡排序：6，15，21，6′，20，17，23，30 第三趟起泡排序：6，15，6′，20，17，21，23，30 第四趟起泡排序：6，6′，15，17，20，21，30，23 第五趟起泡排序：6，6′，15，17，20，21，30，23 (4) 快速排序 初始关键字序列： 15，21，6，30，23，6′，20，17 第一趟快速排序：【6′，6】15【30，23，21，20，17】 第二趟快速排序： 6′，6， 15【17，23，21，20】30 第三趟快速排序： 6′，6， 15，17【23，21，20】30 第四趟快速排序： 6′，6， 15，17，【20，21】23，30 第五趟快速排序： 6，6′，15，17，20，21，30，23 (5) 直接选择排序 初始关键字序列： 15，21，6，30，23，6′，20，17 第一趟直接选择排序： 6，21，15，30，23，6′，20，17 第二趟直接选择排序： 6，6′，15，30，23，21，20，17 第三趟直接选择排序： 6，6′，15，30，23，21，20，17 第四趟直接选择排序： 6，6′，15，17，23，21，20，30 第五趟直接选择排序： 6，6′，15，17，20，21，23，30 第六趟直接选择排序： 6，6′，15，17，20，21，23，30 第七趟直接选择排序： 6，6′，15，17，20，21，23，30 (7) 堆排序 初始关键字序列：15，21，6，30，23，6′，20，17 初始堆： 6，17，6’，21，23，15，20，30

带期限的作业调度问题的算法与实现

2010-2011 第二学期08通信专业 期末考查带期限的作业调度问题的算法与实现班级08通信一班学号14082300939姓名XXXX成绩分 一、设计目的 1.掌握FIFO和LIFO宽度优先检索原理； 2.掌握LC,FIFO分枝界限法； 3.进一步掌握分枝界限法的基本思想和算法设计方法； 二、设计内容 1．任务描述 （1）给定一个带期限的作业排序问题, n=5, (p1,p2,p3,p4,p5)=(6,3,4,8,5), (t1,t2,t3,t4,t5)=(2,1,2,1,1), (d1,d2,d3,d4,d5)= (3,1,4,2,4), 应用FIFOBB求使总罚款数最小的可行作业集J. 要求: ( 2 ）设计任务简介 a）阐述c’(X)和u(X)的设计思路，U的初始值; b）针对解向量变长格式, 画出FIFOBB的生成的部分状态空间树, 按活节点生成顺序给节点编号，在各节点位置给出c’(X)和U的值，给每条边标记选择的作业编号; c）阐述c’(X)=U的处理方案, 可行解的判断方案； d）阐述你程序中的主要数据类型、数据变量和功能模块。 e）、编成并上机实现FIFOBB程序, 实现对不同作业排序问题实例的求解，问题实例的输入数据存储在case.txt文件中，其格式为： 第一行问题规模（最多10个作业） 第二行各作业的罚款数，数据项之间用一个空格分隔 第三行各作业的截止期限，数据项之间用一个空格分隔 第四行各作业所需的运行时间，数据项之间用一个空格分隔 例如： 4 5 10 6 3 1 3 2 1 1 2 1 1 从屏幕直接输出最优作业集的序号，数据项之间用逗号分隔。 2.任务简答 （1）阐述c’(X)和u(X)的设计思路，U的初始值; c’(X)：为当前未选的作业的罚款数。 设计思路：定义一个估计罚款数c;用来记录当前估计数，当再有一个作业分配时，看分配过程中是否有损失的效益；如果有则将其损失值与父亲节点中的c相加记录在当前分配作业的节点c 中去；如果没有损失效益则当前的节点c还是为其父节点的c。 u(X)：在当前所选作业中还有可能得到的罚款数的上限值。

调度例题

1、在一个单道的程序设计系统中，有3个作业A、B、C，它们分别在7：50、8：00和8：30达到输入井，它们需要执行的时间是1.5小时、1小时和0.4小时。系统在9：00开始按响应比高者优先算法对它们进行调度。请回答下列问题： （1）作业被选中执行的次序是什么？ （2）三个作业被选中时的响应比分别是什么？ 1、解：在9：00时，ra=1+70/90，rb=1+60/60,rc=1+30/24 Rc最大，故调度C开始执行。 在9：24时，C运行结束，此时ra=1+94/90,rb=1+84/60 Rb>ra 调度B开始执行 10：24时，B运行结束，ra=1+154/90,调度开始执行 （1）因此调度次序为：C、B、A （2）响应比为：1+30/24，1+84/60，1+154/90 4、假定在单CPU条件下有下列要执行的作业： 作业运行时间优先级 1 10 3 2 1 1 3 2 3 4 1 4 5 5 2 作业到来的时间是按作业编号顺序进行的（即后面作业依次比前一个作业迟到一个时间单位）。 （1）若采用FCFS算法，各个作业的周转时间是多少？平均周转时间是多少？（6分）（2）若采用非抢占式优先级算法，各个作业的周转时间是多少？平均周转时间是多少？（6分） 6、设一个系统中有5个进程，他们的到达时间和服务时间如下表所示，忽略I/O以及其他开销时间，若分别按先来先服务（FCFS）、非抢占短进程优先（SPF）、高响应比优先（HRRN）、时间片轮转（RR，时间片=1）、多级反馈队列（FB，第i级队列的时间片=2i-1）调度算法进行CPU调度，请给出各进程的完成时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间 进程到达时间服务时间 A 0 3 B 2 6 C 4 4 D 6 5

作业排序与车间作业计划(pdf 64页)

1 第九章作业排序与车间作业计划 机密

2 等待是日常生活的一部分 机密

3 本章要点 ?排序工作对资源进行分配，以在一段时间实现某一组织的任务?排序工作以生产能力计划为起点?当MRP 生成的生产作业计划以订单形式下达到生产车间时，我们要对其进行生产作业控制，包括订单的核准，排序，调度和车间控制机

机 本章主要内容 ?基本概念 ?车间排序作业 ?服务业中的作业排序 4

机 第一节基本概念 ?车间作业计划是安排零部件（作业，活动）的产出数 量，设备以及人工使用，投入时间及产出时间 ?生产控制是以生产计划和作业计划为依据，检查，落 实计划执行情况，发现偏差即采取纠正措施，保证各 项计划目标的实现 ?“编制作业计划”是加工制造发生之前的活动 ?“调度”是作业计划编制后实施生产控制所采取的一切行 动， 5

6 一、车间作业控制的内容 目的： —控制生产作业在执行中不偏离MPS/MRP 计划；—出现偏离时，采取措施，纠正偏差，若无法纠正，则反馈到计划层；—报告生产作业执行结果。 目的：—控制生产作业在执行中不偏离MPS/MRP 计划；—出现偏离时，采取措施，纠正偏差，若无法纠正，则反馈到计划层；—报告生产作业执行结果。内容： —控制加工设备完好,人员出勤；—控制加工件在工作中心加工按排定的工序加工；—保持物流稳定,控制投入和产出的工作量;—控制加工成本，结清定单，完成库存事务处理。 内容：—控制加工设备完好,人员出勤；—控制加工件在工作中心加工按排定的工序加工；—保持物流稳定,控制投入和产出的工作量;—控制加工成本，结清定单，完成库存事务处理。机

带时限的作业排序问题

#include #include int FIND(int *parent,int i) {//查找含有元素i的树根，使用压缩规则去压缩由i到根j的所有结点int j,k,t; j=i; while(parent[j]>0) j=parent[j];//找根 k=i; while(k!=j){//压缩由i到根j的结点 t=parent[k]; parent[k]=j; k=t; } return j; } void UNION(int *parent,int i,int j) {//使用加权规则合并根为i和j的两个集合 int x; x=parent[i]+parent[j]; if(parent[i]>parent[j]){//i的结点少 parent[i]=j; parent[j]=x; } else{//j的结点少 parent[j]=i; parent[i]=x; } } int MIN(int n,int m) {//求n和m的最小值 if(n>m) return m; else return n; } int FJS(int *D,int n,int b,int *J,int *Q) {//找J(n)的最优解，并返回最优解的个数 int i,*F,*p,j,l,m,k; F=(int *)malloc((b+1)*sizeof(int)); p=(int *)malloc((b+1)*sizeof(int)); for(i=0;i<=b;i++){//将树置初值 F[i]=i;

p[i]=-1; } k=0;//初始化J for(i=1;i<=n;i++) {//使用贪心规则 j=FIND(p,MIN(n,D[i])); if(F[j]!=0) {//选择作业i k=k+1; J[k]=i; Q[F[j]]=i; m=F[j]; l=FIND(p,F[j]-1); UNION(p,l,j); F[j]=F[l]; } } return k;//返回最优解的个数 } int MAXMUM(int i,int j) {//求i和j的最大值 if(i>j) return i; else return j; } int MAX(int *D,int i, int j) {//D(1:n)是含有n个元素数组，求出D(i,j)中的最大值并返回int max,mid,max1,max2; if(i==j) max=D[i]; else if(i==j-1) if(D[i]

作业调度

作业调度实验报告 1、实验目的 作业管理是用户与操作系统的接口。作业调度的主要功能是检查系统是否能满足用户作业的资源要求以及按照一定的算法选取作业。 本实验的目的是通过模拟作业调度算法的设计加深对作业管理基本原理的理解。 2 实验用具 个人电脑 3、实验内容 ⑴在后备作业队列中，输入5个作业的名称、状态、就绪时间、服务时间及存储空间。 ①按先来先服务的原则进行调度，输出作业调度的顺序及等待的时间。 ②按最短作业（即运行时间最短）优先的原则进行调度，输出作业调度的顺序及等待时间。

4 实习步骤 第一步：首先对整个题目进行分析，包括对作业、主存的定义类型。 第二步：对流程图进行分析，分析一些细节代码。 第三步：根据程序流程图写代码并调节一些细节错误。 第四步：运行看结果，这里主要看内存根据作业的要求对分配情况。 4.1 需求分析 本次实验是在预输入五道作业的基础上初始化，并通过作业的需求更改主存的输出显示情况，首先是输入5道作业，分别使用先来先服务算法和最短时间优先算法分配内存，最后进行内存的回收。

4.2 数据结构设计与说明 定义作业中的变量-资源需求： typedef struct source { int size; //资源要求大小 int tape_count; //资源要求磁带数 }src; 定义作业： typedef struct jobwork { char username[10]; //用户名 char jobname[10]; //作业名 char state[5]; //运行状态 int runtime; //运行时间 src source; //资源需求（结构体类型见上） struct jobwork *next; //下一个指针 }job; 定义内存： typedef struct memory { int size; //内存大小 int tape_count; //内存磁带数 char jobname[10]; //内存中存在的作业名（首次为空） char username[10]; //内存中作业的用户名char state[5]; //内存中作业的状态 int job_count; //内存中作业个数struct memory *next; //内存下一个指针}mem; 4.3 算法设计 第一部分：初始化作业表

各类作业调度算法

实验二作业调度实验 一. 目的要求： 用高级语言编写和调试一个或多个作业调度的模拟程序，以加深对作业调度算法的理解。 二. 例题：为单道批处理系统设计一个作业调度程序。 由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的 CPU时限等因素。 作业调度算法：采用先来先服务（FCFS）调度算法，即按作业提交的先后次序进行调度。总是首先调度在系统中等待时间最长的作业。 每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。 作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。 各个等待的作业按照提交时刻的先后次序排队，总是首先调度等待队列中队首的作业。 每个作业完成后要打印该作业的开始运行时刻、完成时刻、周转时间和带权周转时间，这一组作业完成后要计算并打印这组作业的平均周转时间、带权平均周转时间。 调度算法的流程图如下图所示。

三 . 实习题： 1、编写并调试一个单道处理系统的作业等待模拟程序。 作业等待算法：分别采用先来先服务（FCFS），最短作业优先（SJF）、响应比高者优先（HRN）的调度算法。 对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间，以比较各种算法的优缺点。 2、编写并调度一个多道程序系统的作业调度模拟程序。

作业调度算法：采用基于先来先服务的调度算法。可以参考课本中的方法进行设计。 对于多道程序系统，要假定系统中具有的各种资源及数量、调度作业时必须考虑到每个作业的资源要求。 3、编写并调试一个多道程序系统的作业调度模拟程序。 作业调度算法：采用基于优先级的作业调度。 可以参考课本中的例子自行设计。 三 . 实验过程： 1、编写并调试一个单道处理系统的作业等待模拟程序。 先来先服务（FCFS）： main.cpp: /* **先来先服作业调度算法模拟 */ #include #include #define MAX_SOURCE 1000 //资源总数（对于单通道的作业调度可以忽略系统资源问题） using namespace std; struct jobCB { string name; double subtime;//提交时间 double runtime;//运行时间 double source;//资源 char state;//进程状态 struct jobCB *next; //链指针 }*ready,*rail,*p; int length; double maxsource; double now_source; double allTi;//总周转时间 double allWi;//总带权周转时间 double time;//时钟 void init()

作业调度方案

作业调度方案 问题编号:7 题目描述 我们现在要利用m台机器加工n个工件，每个工件都有m道工序，每道工序都在不同的指定的机器上完成。每个工件的每道工序都有指定的加工时间。每个工件的每个工序称为一个操作，我们用记号j-k表示一个操作，其中j为1到n中的某个数字，为工件号；k为1到m中的某个数字，为工序号，例如2-4表示第2个工件第4道工序的这个操作。在本题中，我们还给定对于各操作的一个安排顺序。 例如，当n=3，m=2时，“1-1，1-2，2-1，3-1，3-2，2-2”就是一个给定的安排顺序，即先安排第1个工件的第1个工序，再安排第1个工件的第2个工序，然后再安排第2个工件的第1个工序，等等。 一方面，每个操作的安排都要满足以下的两个约束条件。 (1) 对同一个工件，每道工序必须在它前面的工序完成后才能开始； (2) 同一时刻每一台机器至多只能加工一个工件。 另一方面，在安排后面的操作时，不能改动前面已安排的操作的工作状态。 由于同一工件都是按工序的顺序安排的，因此，只按原顺序给出工件号，仍可得到同样的安排顺序，于是，在输入数据中，我们将这个安排顺序简写为“1 1 2 3 3 2”。 还要注意，“安排顺序”只要求按照给定的顺序安排每个操作。不一定是各机器上的实际操作顺序。在具体实施时，有可能排在后面的某个操作比前面的某个操作先完成。 例如，取n=3,m=2，已知数据如下： 工件号机器号/加工时间 工序1 工序2 1 1/3 2/2 2 1/2 2/5 3 2/2 1/4 则对于安排顺序“1 1 2 3 3 2”，下图中的两个实施方案都是正确的。但所需要的总时间分别是10与12。 当一个操作插入到某台机器的某个空档时（机器上最后的尚未安排操作的部分也可以看作一个空档），可以靠前插入，也可以靠后或居中插入。为了使问题简单一些，我们约定：在保证约束条件（1）（2）的条件下，尽量靠前插入。并且，我们还约定，如果有多个空档可以插入，就在保证约束条件（1）（2）的条件下，插入到最前面的一个空档。于是，在这些约定下，上例中的方案一是正确的，而方案二是不正确的。显然，在这些约定下，对于给定的安排顺序，符合该安排顺序的实施方案是唯一的，请你计算出该方案完成全部任务所需的总时间。 输入格式 输入文件的第1行为两个正整数，用一个空格隔开：m n （其中m（<20）表示机器数，n（<20）表示工件数） 第2行：m*n个用空格隔开的数，为给定的安排顺序。 接下来的2n行，每行都是用空格隔开的m个正整数，每个数不超过20。其中前n行依次表示每个工件的每个工序所使用的机器号，第1个数为第1个工序的机器号，第2个数为第2个工序机器号，等等。后n行依次表示每个工件的每个工序的加工时间。 可以保证，以上各数据都是正确的，不必检验。 输出格式 输出文件只有一个正整数，为最少的加工时间。

各类作业调度算法

各类作业调度算法 一. 目的要求： 用高级语言编写和调试一个或多个作业调度的模拟程序，以加深对作业调度算法的理 解。 二. 例题：为单道批处理系统设计一个作业调度程序。 由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业完成 为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的 CPU时限等因素。 作业调度算法：采用先来先服务（FCFS）调度算法，即按作业提交的先后次序进行调度。总是首先调度在系统中等待时间最长的作业。 每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所 需的运行时间、所需的资源、作业状态、链指针等等。 作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作 业的最初状态总是等待W。 各个等待的作业按照提交时刻的先后次序排队，总是首先调度等待队列中队首的作业。 每个作业完成后要打印该作业的开始运行时刻、完成时刻、周转时间和带权周转时间， 这一组作业完成后要计算并打印这组作业的平均周转时间、带权平均周转时间。 调度算法的流程图如下图所示。

三 . 实习题： 1、编写并调试一个单道处理系统的作业等待模拟程序。 作业等待算法：分别采用先来先服务（FCFS），最短作业优先（SJF）、响应比高者优先（HRN）的调度算法。 对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间，以比较各种算法的优缺点。 2、编写并调度一个多道程序系统的作业调度模拟程序。 作业调度算法：采用基于先来先服务的调度算法。可以参考课本中的方法进行设计。

操作系统作业题(含问题详解)

1、有三道程序A、B、C在一个系统中运行，该系统有输入、输出设备各1台。三道程序 A、B、C构成如下： A：输入32秒，计算8秒，输出5秒 B：输入21秒，计算14秒，输出35秒 C：输入12秒，计算32秒，输出15秒 问：（1）三道程序顺序执行的总时间是多少？ （2）充分发挥各设备的效能，并行执行上述三道程序，最短需多少时间（不计系统开销）？并给出相应的示意图。 作业一解答过程： 1、（1）三道程序顺序执行的总时间是：32+8+5+21+14+35+12+32+15=174秒。 （2）充分发挥各设备的效能，并行执行上述三道程序，最短需90秒（按BCA顺序执行），示意图如下： 注：按ABC执行需117s，按ACB执行需126s，按BAC执行需112s，按BCA执行需90s，按CAB执行114s，按CBA执行需99s。

1、有以下5条语句，请画出这5条语句的前趋图。（PPT第3章） S1：y=x+1 R(x) W(y) S2：c=f-w R(f,w) W(c) S3：d=r-y R(r,y) W(d) S4：x=a+b R(a,b) W(x) S5：r=c+y R(c,y) W(r) 2、设有k个进程共享一临界区，对于下述情况，请说明信号量的初值、含义，并用P，V 操作写出有关互斥算法。 （1）一次只允许一个进程进入临界区； （2）一次允许m（m V(s) 信号量s的变化范围为[-(k-1) ,…,-1,0,1]。其中，s=1表示有1个空闲且可用的临界资源，且没有进程进入类名为s的临界区；s=0表示有1个进程在临界区中（该临界资源已被某进程占用），但无等待使用该临界资源的进程；s=-n(1≤n≤k-1，n为整数)表示有1个进程在临界区中，且有n个进程等待使用该临界资源。 （2）一次允许m（m

作业调度问题

流水作业调度问题（不能直接使用动态规划法的例子） 流水作业调度的定义： 设有n个作业，每一个作业i均被分解为m项任务: T i1, T i2, ┅ , T im(1≤i≤n，故共有n×m个任务)， 要把这些任务安排到m台机器上进行加工。 如果任务的安排满足下列3个条件， 则称该安排为流水作业调度： 1. 每个作业i的第j项任务T ij (1≤i≤n, 1≤j≤m) 只能安排在机器P j上进行加工； 2. 作业i的第j项任务T ij(1≤i≤n, 2≤j≤m)的开始加工时间 均安排在第j-1项任务T i,j-1加工完毕之后； (任何一个作业的任务必须依次完成，前一项任务完成之后才能开始着手下一项任务) 3. 任何一台机器在任何一个时刻最多只能承担一项任务。 最优流水作业调度： 设任务T ij在机器P j上进行加工需要的时间为t ij。 如果所有的t ij (1≤i≤n, 1≤j≤m)均已给出， 要找出一种安排任务的方法， 使得完成这n个作业的加工时间为最少。 这个安排称之为最优流水作业调度。 完成n个作业的加工时间： 从安排的第一个任务开始加工, 到最后一个任务加工完毕， 其间所需要的时间。

优先调度： 允许优先级较低的任务在执行过程中被中断， 转而去执行优先级较高的任务。 非优先调度： 任何任务一旦开始加工，就不允许被中断， 直到该任务被完成。 流水作业调度一般均指的是非优先调度。 非优先调度可看成是特殊的优先调度： 所有任务的优先级均相同。 7 5 8 e.g. （t ij）= 2 2 6 0 7 4 注意：t ij为0表示作业i无须在机器P j上进行加工、 即该道工序可以省略。 已经证明，当机器数(或称工序数)m≥3时， 流水作业调度问题是一个NP-hard问题（e.g分布式任务调度）。（粗糙地说，即该问题至少在目前 基本上没有可能找到多项式时间的算法。） ∴只有当m=2时，该问题可有多项式时间的算法。 为方便起见，记t i1为a i（作业i在P1上加工所需时间）， t i2为b i（作业i在P2上加工所需时间）。

带精确时间延迟的排序问题

带精确时间延迟的排序问题 文章主要研究带精确延迟时间的排序问题，目标是极小化加权总完工时间，分别给出了单台机和两台流水作业的最优算法。 标签：排序问题；最优算法；延迟 引言 精确时间延迟排序问题按机器数量分为单机问题和两台机流水作业问题。用三参数分别表示为1|exact lj|Cmax，F2|exact lj|Cmax。本文主要研究带精确时间延迟的单机排序问题和两台机流水作业排序问题。每个工件Jj（j=1，2，…，n）有两道工序aj、bj，第一道工序先于第二道工序加工，第一道工序的完工时间c 与第二道工序的开始时间S之间存在一个精确的延迟时间，即S=c+lj。所有工序操作时间都相等aj=bj=a，且精确延误时间是工序操作时间的整数倍lj=ka（k∈N+）。 现有文献考虑的目标函数大多是以最小化时间表长（makespan）为目标函数.本文所考虑的目标函数是最小化加权总完工时间（？撞wjCj）。 1 预备结果 下面先给出相关的定义以及一些初步的结论。 定义1.1 将k个工件的第一道工序连续加工，再按照第一道工序的加工顺序连续加工这k个工件的第二道工序。 当第k个工件的第一道工序ak的完工时间与第一个工件的第二道工序b1的最早开工时间之间存在被迫空闲时，我们称之为被迫不连续加工（图1）。 图1 被迫不连续加工 引理1.1 最优排序中，只存在被迫不连续加工和？资+1-连续加工这两种加工方式，即不存在m（m>k+1或mk+1时，精确延迟时间大于ka；当mk+1或mk+1三種情况。 情形一：当m+nk+1时，将这两组工件放在一起加工，变为一组k+1-连续加工工件和一组被迫不连续加工工件；这组被迫不连续加工的工件个数为m+n-k-1个。 这m+n个工件的总完工时间为 比较这两个总完工时间知

4.6 独立作业最优调度问题

4.6 独立作业最优调度问题 算法设计思想： (1) 动态规划法 用数组*A 和*B 分别存放作业由处理机A 和B 处理需要的时间，预处理得到所有作业均由机器A 处理所需的时间A_total 和均由B 处理的时间B_total 。 构造布尔型三维数组***p ，p[i][j][k]=true 表示前k 个作业能够在机器A 用时不超过i 时间、机器B 不超过j 时间内完成。这样，对于任意一个状态p[i][j][k]=true ，第k 个任务可能由机器A 或机器B 完成，对应的前一状态分别为p[i-A[k-1]][j][k-1]和p[i][j-B[k-1]][k-1]。显然，对任意的i 、j ，有p[i][j][0]。 初始令p[i][j][k]=false ，可以得到动态规划的状态转移方程： [][][][[1]][][1]|[][[1]][1],0_,0_,1[][][0],0_,0_p i j k p i A k j k p i j B k k i A total j B total k n p i j true i A total j B total =------≤≤≤≤≤≤?? =≤≤≤≤? 计算出所有的状态后，得到最优解（最短处理时间）为： 0_,0_,[][][]= min {max(,)}i A total j B total p i j n true minimum i j ≤≤≤≤= 另外，构造整型三维数组***c ，表示p[i][j][k]=true 时第k 个作业的调度情况。初始c[i][j][k]均为0，c[i][j][k]=1表示由机器A 处理，c[i][j][k]=2表示由机器B 处理，c[i][j][k]=3表示机器A 、B 都能处理。在计算状态时，如果p[i-A[k-1]][j][k-1]=true ，则c[i][j][k]=1；如果p[i][j-B[k-1]][k-1]=true ，则c[i][j][k]=2；如果都都满足，则c[i][j][k]=3。从每一个p[i][j][n]=true 且max(i,j)=minimun 的c[i][j][n]反推，即可构造所有可能的最优调度方案。 (2) 二叉树思想输出 二叉树思想输出所有最优解：如果不存在c[i][j][k]=3的情况，则反推c[i][j][n]即可得到所有可能的最优调度方案。但是，解空间中c[i][j][k]=3实际上是二叉树中含有两个儿子的情况，因此必须采用二叉树的遍历算法，才能不漏掉所有的最优方案。想到上学期的数据结构这门课中学到的二叉树结构，通过二叉树的后序遍历算法，即可输出所需叶子节点的路径。 采用动态数组，注意了三维动态数组的申请和释放，这样做节省了内存，使程序变得灵活，可以处理大规模数据。 除此之外，程序对鲁棒性做了增强，对非法输入和文件错误进行了检测。 程序设计代码： /*头文件 作业调度问题.h*/ #ifndef KNAP_H #define KNAP_H

带有限期的作业排序

带有限期的作业排序 问题的描述： 带有期限的作业排序要解决的是操作系统中单机、无资源约束且每个作业可在等量的时间内完成的作业调度问题。把这个问题形式化描述为： ①要在一台机器上处理n个作业，每个作业可以在单位时间内完成 ②每个作业i都有一个期限值d i，d i>0 ③当作业在它规定的期限值前完成，就可以获得的效益p i，p i>0 问题求解的目标是：问题的可行解是这n个作业的一个子集合J。J中的每个作业都能在各自的截止期限前完成后，产生一个作业效益之和。我们的目标就是找到一个子集J，J中的每个作业都能在各 自的截止期限前完成，并且使得作业效益值的和最大。这个作业的一个子集合J就是所求的最优解。 带有期限的作业排序的一个例子： 例3.2 n=4，(p1,p2,p3,p4)=(100,10,15,20)，(d1,d2,d3,d4)=(2,1,2,1)。这个问题的最优解为第7个，所允许的处理顺序是：先处理作业4，在处理作业1。在时间0开始处理作业4而在时间2完成对作业1的处理。 可行解处理顺序效益值 1 {1} 1 100 2 {2} 2 10 3 {3} 3 15 4 {4} 4 20 5 {1，2} 2，1 110 6 {1，3} 1，3或3，1 115 7 {1，4} 4，1 120 8 {2，3} 2，3 25 9 {3，4} 4，3 35 带有期限的作业排序贪心算法度量标准的选取： 我们的目标是作业效益值的和最大，因此首先把目标函数作为度量标准。首先把作业按照它们的效益值作一个非增次序的排序。以例3.2来说，作业根据效益值排序后为作业1、4、3、2。求解时首先把作业1计入J，由于作业1的期限值是2，所以J={1}是一个可行解。接下来计入作业4。由于作业4的期限值是1而作业1的期限值是2，可以先完成作业4后再完成作业1，所以J={1, 4}是一个可行的解。然后考虑作业3，但是作业3的期限值是2，计入J后就没有办法保证J中的每一个作业都在期限值内完成，因此计入作业3后不能构成一个可行解。同理计入2后也不能构成一个可行解。由分析可知，把目标函数作为度量标准能够得到问题的最优解。 作业排序算法的概略描述： 算法3.3 procedure GREEDY-JOB(D,J,n) //作业按照p1≥p2≥…≥pn的次序输入，它们的期限值D(i) ≥1, 1≤i≤n, n≥1。J是在它们的截止期限前完成的作业集合。 J←{1} For i←2 to n do If J∪{i}的所有作业都能在它们的截止期限前完成

带期限的作业排序问题

带期限的作业排序问题 (1) 答：c`(x)的设计思路:当x=1时，c`(x)为所有作业的罚款金额总和,某节点m的估计值为c`(x)，并对其进行扩展时，其有效的子节点a的c`(x)为m的c`(x)-a的罚款金额。 对于u(x)初始时为作业罚款金额总和。之后，若队列中的某一节点b的c`(x)最小且小于u(x),则使u(x) =b. c`(x) (2) (3)当某节点的已经被罚款项即c(x)>U，则封杀此节点。 (4)当从根开始到当前要加入的节点这条路径中，共花费时间costtime ,最大截止期限为maxdeadtime，若maxdeadtime #include using namespace std; struct node

流水作业调度问题

一、 问题描述 给定n 个作业，每个作业有两道工序，分别在两台机器上处理。一台机器一次只能处 理一道工序，并且一道工序一旦开始就必须进行下去直到完成。一个作业只有在机器1上的处理完成以后才能由机器2处理。假设已知作业i 在机器j 上需要的处理时间为t[i,j]。流水作业调度问题就是要求确定一个作业的处理顺序使得尽快完成这n 个作业。 二、 算法分析 n 个作业{1,2,…,n}要在由2台机器1M 和2M 组成的流水线上完成加工。每个作业加工 的顺序都是先在1M 上加工，然后在2M 上加工。1M 和2M 加工作业i 所需要的时间分别为t[i,1]和t[i,2], n i ≤≤1.流水作业调度问题要求确定这n 个作业的最优加工顺序，使得从第一个作业在机器1M 上开始加工，到最后一个作业在机器2M 上加工完成所需的时间最少。 从直观上我们可以看到，一个最优调度应使机器1M 没有空闲时间，且机器2M 的空闲 时间是最少。在一般情况下，机器2M 上会有机器空闲和作业积压两种情况。 设全部作业的集合为},....,2,1{n N =。N S ?是N 的作业子集。在一般情况下，机器 1M 开始加工S 中作业时，机器2M 还在加工其他作业，要等时间t 后才能利用。将这种情况下完成S 中作业所需的最短时间计为),(t S T 。流水作业调度问题的最优解为)0,(N T 。 1. 证明流水作业调度问题具有最优子结构 设a 是所给n 个流水作业的一个最优调度，它所需要的加工时间为']1),1([T a t +。 其中，' T 是在机器2M 的等待时间为]2),1([a t 时，安排作业)(),......,3(),2(n a a a 所需 的时间。 记)}1({a N S -=，则我们可以得到])2),1([,('a t S T T =。

资源与运营管理作业问题答案

资源与运营管理作业1 指导： 你可以把在本单元内学习的内容与自己的实际工作结合起来，思考与整个招聘和就职过程 相关的问题： (1)设想你的团队中有两名成员因为个人的原因要离职，那么，他们所承担的工作怎么办? 你是否需要马上向人事部f1报告你的招聘计划? (2)假设主管经理告诉你，她无法保证这两个离开的人都能由新员工来接替。园为公司当前需要压缩人员编制，裁员是肯定的，要么在你的团队，要么是别的团队。在这种情况下，你能向她提供什么信息，以帮助她决定你的团队是否需要重新招聘人员? (3)你可以试着为空缺职位准备工作描述。．工作描述应包括以下内容： 该项工作的主要目的： 该项工作的主要任务； 该项工作的范围。 (4)接下来，请准备人员规范。你既可以利用基于资格的方法制定人员规范，也可以列出基本能力和优先能力。 (5)根据你制定的人员规范，列出在面试时要问的问题。记住，你需要寻找证据来证明应聘者能够胜任这份工作。 (6)然后，为新团队成员工作第一周的就职过程作计划。计划中应包括他们要做什么、什么时间做、谁要参与等。 (7)下一步，制定你的行动计划，该计划将监督新团队成员前3个月的工作情况，以确保他们能尽快适应工作。记住，你需要定期进行回顾，以保证一切按计划进行。 (8)以3个月为期限，召开绩效管理会议。会议上你可以设定绩效目标，听取反馈意见，并讨论进一步发展的需求。 (9)你需要准备一份备忘录，备忘录的内容可以有： 你多长时间与团队成员进行一次谈话； 你怎样核查培训效果： 什么时候你会提高团队成员的目标； 是否让其他团队成员扮演指导伙伴的角色。 总结： 这个大作业可以帮助你利用自己的工作环境作为背景，完整地思考整个招聘过程及引导新员工就职过程中的所有问题。这样的练习有助于你掌握招聘新员工，引导新员工就职以及留住有用人才的方法，并切实提高相应的技能。 答: 个人招聘方案 一、现状调查 出现问题：本部门有两名员工提出离职 处理意见：评估本部门整体的需求，需要做如下的工作： 1．了解本部门工作的紧张程度； 2．保持工作效率和服务水平需要面临的问题； 3．维持现有的工作效率是否需要开展轮班制度；

流水线作业排序问题

流水线作业排序问题 https://www.wendangku.net/doc/176570061.html,/productioncontrol/200908091604.html 流水作业排序问题的基本特征是每个工件的加工路线都一致。在流水生产线上制造不同的零件，遇到的就是流水作业排序问题。我们说加工路线一致，是指工件的流向一致，并不要求每个工件必须经过加工路线上每台机器加工。如果某些工件不经某些机器加工，则设相应的加工时间为零。 一般说来，对于流水作业排序问题，工件在不同机器上的加工顺序不尽一致。但本节要讨论的是一种特殊情况，即所有工件在各台机器上的加工顺序都相同的情况。这就是排列排序问题。流水作业排列排序问题常被称作“同顺序”排序问题。对于一般情形，排列排序问题的最优解不一定是相应的流水作业排序问题的最优解，但一般是比较好的解；对于仅有2台和3台机器的特殊情况，可以证明，排列排序问题下的最优解一定是相应流水作业排序问题的最优解。 这里只讨论排列排序问题。但对于2台机器的排序问题，实际上不限于排列排序问题。一、最长流程时间Fmax的计算 这里所讨论的是n／m／P /Fmax，问题，其中n为工件数，m为机器数，P表示流水线作业排列排序问题，Fmax为目标函数。目标函数是使最长流程时间最短，最长流程时间又称作加工周期，它是从第一个工件在第一台机器开始加工时算起，到最后一个工件在最后一台机器上完成加工时为止所经过的时间。由于假设所有工件的到达时间都为零(ri=0，i= 1，2，…，n)，所以Fmax等于排在末位加工的工件在车间的停留时间，也等于一批工件的最长完工时间Cmax。 设n个工件的加工顺序为S＝(S1，S2，S3，…，Sn)，其中Si为第i位加工的工件的代号。以表示工件Si在机器M k上的完工时间, 表示工件Si在Mk上的加工时间，k= 1，2，…，m；i=1，2，…，n，则可按以下公式计算： 在熟悉以上计算公式之后，可直接在加工时间矩阵上从左向右计算完工时间。下面以一例说明。 例9．4 有一个6／4／p／F max问题，其加工时间如表9—6所示。当按顺序S=(6，1，5，2，4，3)加工时，求Fmax 。