智能调度作业的算法

Ⅰ np-hard问题 可以用遗传算法求解吗

np-hard问题 可以用遗传算法求解
由于遗传算法的整体搜索策略和优化搜索方法在计算时不依赖于梯度信息或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于许多科学，下面我们将介绍遗传算法的一些主要应用领域： 随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP问题非常有效。例如遗传算法已经在求解旅行商问题、 背包问题、装箱问题、图形划分问题等方面得到成功的应用。
此外，GA也在生产调度问题、自动控制、机器人学、图象处理、人工生命、遗传编码和机器学习等方面获得了广泛的运用。 车间调度问题是一个典型的NP-Hard问题，遗传算法作为一种经典的智能算法广泛用于车间调度中，很多学者都致力于用遗传算法解决车间调度问题，现今也取得了十分丰硕的成果。从最初的传统车间调度（JSP）问题到柔性作业车间调度问题（FJSP），遗传算法都有优异的表现，在很多算例中都得到了最优或近优解。

Ⅱ 调度算法的调度算法

在操作系统中调度是指一种资源分配，因而调度算法是指：根据系统的资源分配策略所规定的资源分配算法。对于不同的的系统和系统目标，通常采用不同的调度算法，例如，在批处理系统中，为了照顾为数众多的段作业，应采用短作业优先的调度算法；又如在分时系统中，为了保证系统具有合理的响应时间，应当采用轮转法进行调度。目前存在的多种调度算法中，有的算法适用于作业调度，有的算法适用于进程调度；但也有些调度算法既可以用于作业调度，也可以用于进程调度。
通常将作业或进程归入各种就绪或阻塞队列。
调度算法要求：高资源利用率、高吞吐量、用户满意等原则。
进程调度所采用的算法是与整个系统的设计目标相一致的：
1.批处理系统：增加系统吞吐量和提高系统资源的利用率;
2.分时系统：保证每个分时用户能容忍的响应时间。
3.实时系统：保证对随机发生的外部事件做出实时响应。

Ⅲ 作业调度算法的选择原则有哪几个

批处理作业的调度算法主要有以下几种：
①先来先服务算法。原则上按照作业进入输入井的次序调度，如果作业的资源得不到满足，将会推迟调度，它的资源得到满足的时候会优先被调度进来。
优点：具有一定的公平性。
缺点：系统的吞吐率低，平均周转时间长，有大作业到来的时，许多小作业推迟调度。
②计算时间短的作业优先．优先调度计算时间短的作业进行调度，资源不满足的情况下推迟调度。在这种调度算法下，要求用户要对作业的计算时间预先有一个估计，调度以此为依据。
优点：由于被选中的作业计算时间，所以不能尽快地完成并退出系统，降低了作业的平均等待时间，提高了系统的吞吐率。
缺点：大作业会不满意，而且极限情况下使得某些大作业始终得不到调度。
③响应比高者优先算法。该算法考虑了计算时间等待时间，既考虑了计算时间短的作业优先，又考虑了大作业长期等待的问题。所谓响应比是按照以下公式来定义的：
响应比R=等待时间/计算时间
这里的计算时间是估计的作业计算时间，从公式看，计算时间越短，响应比越高；而另一方面，大作业等待时间越长，响应比也会越大。一个作业完成以后，需要重新计算一下在输入井中的各个作业的响应比，最高的将优先调度。
④优先数调度算法。为每一个作业指定一个优先数，优先数高的作业先被调度。对于优先数相等的作业采用先来先服务的策略。优先数的制定原则是：作业的缓急程序，估计的计算时间，作业的等待时间，资源申请情况等因素综合考虑。
⑤均衡调度算法。使用不同资源的进程同时执行，减少作业等待同类设备而耗费的时间，加快作业的执行。

Ⅳ 作业调度的功能是什么作业调度算法应考虑的主要因素是什么

1、作业调度的主要功能是：

根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执行。

2、主要考虑因素：

要考虑数据结构的设计、程序执行时间、数据的状态、是否使得I / O 设备得以充分利用等因素。

通常情况下，对于简单的时间触发式调度器来说，待命任务列表的数据结构的设计要尽可能缩短；最坏情况下，程序在调度器关键部分的执行时间，以防止其他任务一直在待命列表中，无法及时执行。

因此，在这种调度器中，应尽可能避免抢占式任务，甚至应该关闭调度器之外的所有中断。当然，待命任务列表的数据结构也应根据这个系统需要的最大任务数量做进一步的优化。

(4)智能调度作业的算法扩展阅读

调度算法应该做到：

1 、在单位时间内运行尽可能多的作业。

2 、作业调度时应使处理机保持忙碌的状态。

3 、使 I / O 设备得以充分利用。为适应一个进程在不同时间段的运行特点，I/O完成时，提高优先级；时间片用完时，降低优先级。

4 、对所有作业公平合理。

5、仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。

Ⅳ 单道批处理系统作业调度算法有哪几种

批处理系统常用调度算法：
①、先来先服务：FCFS
②、最短作业优先
③、最短剩余时间优先
④、响应比最高者优先
分时系统调度算法：
①、轮转调度
②、优先级调度
③、多级队列调度
④、彩票调度
实时系统调度算法：
①、单比率调度
②、限期调度
③、最少裕度法

Ⅵ 作业调度的算法都有哪些

作业调度的算法有：算法有先来先服务、最短作业优先算法、最高响应比优先算法、基于优先数调度算法。

1、算法有先来先服务

最简单的调度算法，按作业的先后顺序进行调度，只考虑每个作业的等待时间而未考虑执行时间的长短。

2、最短作业优先算法

最短作业优先算法是对先来先服务算法的改进，其目标是减少平均周转时间。对预计执行时间短的作业优先分派处理机。通常后来的短作业不抢先正在执行的作业。 只考虑执行时间而未考虑等待时间的长短。

3、最高响应比优先算法

最高响应比优先算法是对先来先服务方式和最短作业优先算法方式的一种综合平衡。最高响应比优先法调度策略同时考虑每个作业的等待时间的长短和估计需要的执行时间长短，从中选出相应比最高的作业投入执行。

4、基于优先数调度算法

优先数调度算法常用于批处理系统中。在进程调度中，每次调度时，系统把处理机分配给就绪队列中优先数最高的进程。它又分为两种：非抢占式优先数算法和抢占式优先数算法。

(6)智能调度作业的算法扩展阅读：

作业调度是指按照时间周期(年、月、日、时、分、秒等)对作业进行分割，并根据业务需求、作业长度、存储管理及依赖性关系对作业的执行方式加以调度。主要任务是从作业后备队列中选择作业进入主存运行。作业调度的功能主要有以下几方面：

1、记录各作业在系统中的状态；

2、从后备队列中挑选一部分作业投入运行；

3、从被选中的作业做好执行前的准备工作；

4、在作业执行结束时，做善后处理工作。

进行作业调度有很多作业调度算法，这些作业调度算法要实现的目标是：

1、调度对所有作业都是公平合理的；

2、应使设备有较高的利用率（提供系统利用率）；

3、每次运行尽可能多的作业（提高系统吞吐量）；

4、较快的相应时间。

Ⅶ 什么是作业,常见的作业调度算法有哪些

作业由三部分构成：程序、数据和作业说明书；是用户在完成一项任务过程中要求计算机系统所做工作的集合.
先来先服务
时间片轮转
最短作业优先
多级反馈队列
优先级法
最高响应比优先

Ⅷ 作业调度的算法有哪些

作业调度的算法有：算法有先来先服务、最短作业优先算法、最高响应比优先算法、基于优先数调度算法。

1、算法有先来先服务

最简单的调度算法，按作业的先后顺序进行调度，只考虑每个作业的等待时间而未考虑执行时间的长短。

2、最短作业优先算法

最短作业优先算法是对先来先服务算法的改进，其目标是减少平均周转时间。对预计执行时间短的作业优先分派处理机。通常后来的短作业不抢先正在执行的作业。 只考虑执行时间而未考虑等待时间的长短。

3、最高响应比优先算法

最高响应比优先算法是对先来先服务方式和最短作业优先算法方式的一种综合平衡。最高响应比优先法调度策略同时考虑每个作业的等待时间的长短和估计需要的执行时间长短，从中选出相应比最高的作业投入执行。

4、基于优先数调度算法

优先数调度算法常用于批处理系统中。在进程调度中，每次调度时，系统把处理机分配给就绪队列中优先数最高的进程。它又分为两种：非抢占式优先数算法和抢占式优先数算法。

(8)智能调度作业的算法扩展阅读：

作业调度是指按照时间周期(年、月、日、时、分、秒等)对作业进行分割，并根据业务需求、作业长度、存储管理及依赖性关系对作业的执行方式加以调度。主要任务是从作业后备队列中选择作业进入主存运行。作业调度的功能主要有以下几方面：

1、记录各作业在系统中的状态；

2、从后备队列中挑选一部分作业投入运行；

3、从被选中的作业做好执行前的准备工作；

4、在作业执行结束时，做善后处理工作。

进行作业调度有很多作业调度算法，这些作业调度算法要实现的目标是：

1、调度对所有作业都是公平合理的；

2、应使设备有较高的利用率（提供系统利用率）；

3、每次运行尽可能多的作业（提高系统吞吐量）；

4、较快的相应时间。

Ⅸ 实时操作系统常用任务调度算法有哪些

实时操作系统常用任务调度算法有哪些
操作系统常用的批处理作业调度算法
1．先来先服务调度算法
先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。
2．短作业(进程)优先调度算法

Ⅹ 编写代码实现作业的三种调度算法

#include<windows.h>
#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;
const int maxnum=100;
int N; /*进程数*/
double start[maxnum],endtime[maxnum],arrive[maxnum],runtime[maxnum],zhou[maxnum];
double averagezhou; // 平均周转时间
double average_zhou; //平均带权周转时间
char name; //进程名
double dqzhou[maxnum]; //带权周转时间
typedef struct node
{
char name[10]; //进程名
int round; //进程时间轮转时间片
int cputime; //进程占用CPU时间
int needtime; //进程到完成还要的时间
char state; //进程的状态
struct node *next; //链指针
}PCB;
PCB *finish,*ready,*tail,*run; /*队列指针*/

void firstin() /*将就绪队列中的第一个进程投入运行*/
{
run=ready; /*就绪队列头指针赋值给运行头指针*/
run->state='R'; /*进程状态变为运行态*/
ready=ready->next; /*就绪对列头指针后移到下一进程*/
}
void print1(PCB *q) /*进程PCB输出*/
{
printf("进程名 已运行时间 还需要时间 时间片 状态\n");
printf(" %-10s%-15d%-10d%-10d %-c\n",q->name,q->cputime,q->needtime,q->round,q->state);
}
void print() /*输出函数*/
{
PCB *p;
if(run!=NULL) /*如果运行指针不空*/
print1(run); /*输出当前正在运行的PCB*/
p=ready; /*输出就绪队列PCB*/
while(p!=NULL)
{
print1(p);
p=p->next;
}
p=finish; /*输出完成队列的PCB*/
while(p!=NULL)
{
print1(p);
p=p->next;
}
}
void insert(PCB *p2) //轮转法插入函数
{
tail->next=p2; //将新的PCB插入在当前就绪队列的尾
tail=p2;
p2->next=NULL;
}
void create() /*创建进程PCB*/
{
PCB *p;
int i,time;
char na[10];
ready=NULL;
finish=NULL;
run=NULL;
printf("请输入进程名称和所需要CPU的时间:\n");
for(i=1;i<=N;i++)
{
p=(PCB *)malloc(sizeof(PCB));
scanf("%s",na);
scanf("%d",&time);
strcpy(p->name,na);
p->cputime=0;
p->needtime=time;
if(i==1)
p->state='R';
else
p->state='W';
p->round=1; /*时间片*/
if(ready!=NULL)
insert(p);
else
{
p->next=ready;
ready=p;
tail=p;
}
}
printf("------------------------------------------------------------------\n");
print(); /*输出进程PCB信息*/
run=ready; /*将就绪队列的第一个进程投入运行*/
ready=ready->next;
run->state='R';
}
void RR() //时间片轮转调度
{
while(run!=NULL)
{
run->cputime=run->cputime+1;
run->needtime=run->needtime-1;
if(run->needtime==0) /*运行完将其变为完成态，插入完成队列*/
{
run->next=finish;
finish=run;
run->state='F';
run=NULL;
if(ready!=NULL)
firstin(); /*就绪对列不空，将第一个进程投入运行*/
}
else
if(ready!=NULL) /*如就绪队列不空*/
{
run->state='W'; /*将进程插入到就绪队列中等待轮转*/
insert(run);
firstin(); /*将就绪对列的第一个进程投入运行*/
}
printf("------------------------------------------------------------------\n");
print(); /*输出进程信息*/
}
}

void FCFS(double *arrive,double *runtime,double n) //先来先服务调度算法
{
start[0]=arrive[0]; //开始执行时间=到达时间
endtime[0]=start[0]+runtime[0]; //完成时间=开始时间+服务时间
zhou[0]=endtime[0]-arrive[0]; //周转时间=完成时间-到达时间
dqzhou[0]=zhou[0]/runtime[0];
for(int i=0;i<n;i++)
{
if(endtime[i-1]>arrive[i]||endtime[i-1]==arrive[i])
endtime[i]=endtime[i-1]+runtime[i];
else
endtime[i]=arrive[i]+runtime[i];
zhou[i]=endtime[i]-arrive[i];
dqzhou[i]=zhou[i]/runtime[i];
averagezhou+=zhou[i];
average_zhou+=dqzhou[i];
}
averagezhou=averagezhou/n;
average_zhou=average_zhou/n;
cout<<"完成时间为:"<<endl;
for(int j=0;j<n;j++)
cout<<endtime[j]<<" "<<endl;
cout<<"周转时间为:"<<endl;
for(int k=0;k<n;k++)
cout<<zhou[k]<<" "<<endl;
cout<<"带权周转时间为:"<<endl;
for(int m=0;m<n;m++)
cout<<dqzhou[m]<<" "<<endl;
cout<<"平均周转时间为:"<<endl;
cout<<averagezhou<<" "<<endl;
cout<<"平均带权周转时间为:"<<endl;
cout<<average_zhou<<" "<<endl;
}

void SJF(double *arrive,double *runtime,double n) //短作业优先调度算法
{
int end[maxnum]; //用于标记进程是否已经执行，应经执行end[i]=1,否则为0;
for(int k=0;k<n;k++)
end[k]=0;
int temp,now=0,next=1,p=1; //now表示刚执行完的进程号，next表示下一个要执行的进程号
start[0]=arrive[0]; //开始执行时间=到达时间
endtime[0]=start[0]+runtime[0]; //完成时间=开始时间+服务时间
zhou[0]=endtime[0]-arrive[0]; //周转时间=完成时间-到达时间
dqzhou[0]=zhou[0]/runtime[0]; //带权周转时间=周转时间/服务时间
averagezhou=zhou[0];
average_zhou=dqzhou[0];
end[now]=1; //执行完的进程设置为1；
for(int i=1;i<n;i++)
{
int j;
for(j=1;j<n;)
{
if(arrive[j]<endtime[now]||arrive[j]==endtime[now])
j++;
else
break;
}
temp=j;
int min=p;
for(j=1;j<=temp;j++)
{
if(runtime[min]>runtime[j] && end[j]==0)
min=j;
}
next=min;
endtime[next]=endtime[now]+runtime[next];
zhou[next]=endtime[next]-arrive[next];
dqzhou[next]=zhou[next]/runtime[next];
averagezhou+=zhou[next];
average_zhou+=dqzhou[next];
end[next]=1;
now=next;
next=p;
while(end[p]!=0)
p++;
}
averagezhou=averagezhou/n;
average_zhou=average_zhou/n;
cout<<"完成时间为:"<<endl;
for(int j=0;j<n;j++)
cout<<endtime[j]<<" "<<endl;
cout<<"周转时间为:"<<endl;
for(k=0;k<n;k++)
cout<<zhou[k]<<" "<<endl;
cout<<"带权周转时间为:"<<endl;
for(int m=0;m<n;m++)
cout<<dqzhou[m]<<" "<<endl;
cout<<"平均周转时间为:"<<endl;
cout<<averagezhou<<" "<<endl;
cout<<"平均带权周转时间为:"<<endl;
cout<<average_zhou<<" "<<endl;
}

int EDF() //最早截止时间的调度算法
{
int arrive_A,arrive_B; //标记进程A,进程B的到达时间
int zhouqi_A,zhouqi_B,serve_A,serve_B; //进程的周期时间和服务时间
int i,j,a=0,b=0,ka=0,kb=0; //ka,kb为开关,i,j,a,b为进程下标
int num_a=0,num_b=0; //服务累计时间
printf("输入进程A的周期时间,服务时间: ");
scanf("%d%d",&zhouqi_A,&serve_A);
printf("输入进程B的周期时间,服务时间: ");
scanf("%d%d",&zhouqi_B,&serve_B);
for(int T=0;T<=100;T++)
{
if(num_a==serve_A) //进程A完成
{
num_a=serve_A+1;
printf("当T=%d时",T);
printf("进程A%d结束\n",a);
if(num_b<serve_B)
{
printf(" 调用进程B%d\n",b);
kb=1;
}
ka=0;
}
if(num_b==serve_B)
{
num_b=serve_B+1;
printf("当T=%d时",T);
printf("进程B%d结束\n",b);
if(num_a<serve_A)
{
printf(" 调用进程A%d\n",a);
ka=1;
}
kb=0;
}
if(T%zhouqi_A==0 && T%zhouqi_B==0)
{
arrive_A=arrive_B=T;
j=++a;
i=++b;
printf("当T=%d时,进程A%d和进程B%d同时产生，此时，",T,j,i);
if(zhouqi_A<=zhouqi_B)
{
printf("调用进程A%d，阻塞进程B%d\n",j,i);
ka=1;
kb=0;
}
else
{
printf("调用进程B%d，阻塞进程A%d\n",i,j);
ka=0;
kb=1;
}
num_a=num_b=0;
}
if(T%zhouqi_A==0&&T%zhouqi_B!=0)
{
arrive_A=T;
printf("当T=%d时",T);
printf("进程A%d产生 ",++a); //不可能与进程A竞争处理器
num_a=0;
if(num_b<serve_B) //进程B没有完成
if(arrive_B+zhouqi_B>arrive_A+zhouqi_A) //若进程B最早截止时间大于进程A的,则执行进程A
{
printf("进程A%d执行。\n",a);
ka=1;
kb=0;
}
else //若进程B最早截止时间小于等于进程A的
printf("进程B%d继续执行。\n",b);
else //进程B完成
{
printf("进程A%d执行。\n",a);
ka=1;
}
}
if(T%zhouqi_A!=0 && T%zhouqi_B==0)
{
arrive_B=T;
printf("当T=%d时",T);
printf("进程B%d产生，",++b); //不可能与进程B竞争处理器
num_b=0;
if(num_a<serve_A) //进程A没有完成
if(arrive_B+zhouqi_B>=arrive_A+zhouqi_A) //进程A的最早截止时间不小于B
printf("进程A%d继续执行。\n",a);
else
{
printf("进程B%d执行。\n",b);
kb=1;
ka=0;
}

else //进程A完成
{
printf("进程B%d执行。\n",b);
kb=1;
}
}
if(ka)
num_a++;
if(kb)
num_b++;
}
return 1;
}

int main()
{
system("color 0b"); //设置颜色
cout<<"最早截止时间的调度算法如下: "<<endl<<endl;
EDF();
int n;
cout<<endl;
cout<<"请输入进程的数目: ";
cin>>n;
cout<<"请按进程到达时间从小到大依次输入n个进程的到达时间: "<<endl;
for(int i=0;i<n;i++)
cin>>arrive[i];
cout<<"请按上面进程的顺序依次输入n个进程的服务时间: "<<endl;
for(int j=0;j<n;j++)
cin>>runtime[j];
cout<<"先来先服务调度算法如下: "<<endl;
FCFS(arrive,runtime,n);
cout<<endl<<endl;
cout<<"短作业优先调度算法如下: "<<endl;
SJF(arrive,runtime,n);
cout<<endl<<endl;
printf("轮转调度算法如下:\n\n");
printf("输入创建进程的数目:\n");
scanf("%d",&N);
create();
RR();
return 0；
}