贪心算法多机调度问题c程序

实验内容：多机调度问题

设有n项独立的作业{1,2,…, n},由m台相同的机器加工处理。作业i所需要的处理时间为台相同的机器加工处理。设有n项独立的作业由ti。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分成更小的子作业。多机调度问题要求给出一种调度方案，能拆分成更小的子作业。多机调度问题要求给出一种调度方案，使所给的n个作业在尽可台机器处理完。利用贪心策略，设计贪心算法解决多机调度问题，能短的时间内由m台机器处理完。利用贪心策略，设计贪心算法解决多机调度问题，并计算其时间复杂度。

多机调度问题的一个实例：

多机调度问题的一个实例：项独立的作业{1,2,3,4,5,6,7}，要由三台机器M1, M2 ,M3处理。各个作业所需处理。各个作业所需例如设有7项独立的作业，要的处理时间分别为{2,14,4,16,6,5,3}。利用你设计的贪心算法，要的处理时间分别为。利用你设计的贪心算法，安排作业的处理顺序使得机器处理作业的时间最短。器处理作业的时间最短。

#include

using namespace std;

void Greedy(int t[],int n,int m);

int main() {

int n=7,m=3,t[]={2,14,4,16,6,5,3};//待分配的工作

Greedy(t,n,m);

return 0; }

void Greedy(int t[],int n,int m)

{ int flagn,flagm; int M[]={0,0,0,0,0,0,0,0};

for(int i=0;i

{ int max=0,min=10000;

flagn=0;

flagm=0;

for(int j=0;j

{ if(max

for(j=0;j

{

if(M[flagm]>M[j])

{flagm=j;}

}

M[flagm]=M[flagm]+t[flagn]; t[flagn]=0; //被选择过的机器时间调为0cout<

课程设计报告-贪心算法：任务调度问题

数据结构课程设计报告 贪心算法：任务调度问题的设计 专业 学生姓名 班级 学 号 指导教师 完成日期

贪心算法：任务调度问题的设计 目录 1设计内容 (1) 2）输入要求 (1) 3）输出要求 (1) 2设计分析 (1) 2.1排序（将数组按照从小到大排序）的设计 (1) 2.2多个测试案例的处理方法的设计 (2) 2.3 for循环设计 (2) 2.4系统流程图 (2) 3设计实践 (2) 3.1希尔排序模块设计 (2) 3.2 多个测试案例的处理方法的模块设计 (3) 4测试方法 (4) 5程序运行效果 (4) 6设计心得 (6) 7附录 (6)

数据结构课程设计报告（2017） 贪心算法：任务调度问题的设计 1设计内容 有n项任务，要求按顺序执行，并设定第I项任务需要t[i]单位时间。如果任务完成的顺序为1，2，…，n，那么第I项任务完成的时间为c[i]=t[1]+…+t[i]，平均完成时间（ACT）即为（c[1]+..+c[n]）/n。本题要求找到最小的任务平均完成时间。 2）输入要求 输入数据中包含n个测试案例。每一个案例的第一行给出一个不大于2000000的整数n，接着下面一行开始列出n各非负整数t（t≤1000000000），每个数之间用空格相互隔开，以一个负数来结束输入。 3）输出要求 对每一个测试案例，打印它的最小平均完成时间，并精确到0.01。每个案例对应的输出结果都占一行。若输入某一个案例中任务数目n=0，则对应输出一个空行。 2 设计分析 这个题目属于贪心算法应用中的任务调度问题。要得到所有任务的平均完成时间，只需要将各个任务完成时间从小到大排序，任务实际完成需要的时间等于它等待的时间与自身执行需要的时间之和。这样给出的调度是按照最短作业优先进行来安排的。贪心算法通过一系列的选择来得到一个问题的解。它所做的每一个选择都是当前状态下某种意义的最好选择，即贪心选择。在许多可以用贪心算法求解的问题中一般具有两个重要的性质：贪心选择性质和最有子结构性质。所谓贪心选择性只是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到，这是贪心算法可行的第一基本要素。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心选择最终将会得到问题的一个整体最优解。首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。而且做了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步做贪心选择，最终可得到问题的一个整体最优解。其中，证明贪心选择后问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。当一个问题的最优解包含着它的子问题最优解时，称此问题具有最优子结构性质，这个性质是该问题可用贪心算法求解的一个关键特征。 2.1排序（将数组按照从小到大排序）的设计 排序的方法有很多，如：冒泡排序、希尔排序、堆排序等，这些排序的方法都可以使用。这里采用希尔排序来实现。 它的基本思想是：先取一个小于n的整数d1作为第一个增量；这里选取n的一半作为第一个增量（increment=n》1），把数组的全部元素分成d1个组。所有距

算法之多机调度问题

算法之多机调度问题 用贪心法解决多机调度问题 （1）问题的描述 设有n个独立的作业{1, 2,…, n}，由m台相同的机器{M1, M2,…, Mm}进行加工处理，作业i所需的处理时间为ti（1≤i≤n），每个作业均可在任何一台机器上加工处理，但不可间断、拆分。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。 （2）算法设计思想 解多机调度问题的贪心策略是最长处理时间作业优先，即把处理时间最长的作业分配给最先空闲的机器，这样可以保证处理时间长的作业优先处理，从而在整体上获得尽可能短的处理时间。 （3）数据及解题过程 设7个独立作业{1, 2, 3, 4, 5, 6, 7}由3台机器{M1, M2, M3}加工处理，各作业所需的处理时间分别为{2, 14, 4, 16, 6, 5, 3}。贪心法产生的作业调度如下： （4）程序使用C++运行测试 （5）代码如下： #include #include using namespace std; //冒泡法对作业时间t降序排列，作业编号p的顺序也随t的顺序改变而改变，这点很重要！ void Dsc_Order_By_t(int t[],int p[],int n) //注意：数组元素下标从1开始{ //你的代码 int i,j;

for (i=1;i<=n;i++) { for (j=1;j<=n-i;j++) { if (t[j]

实验二(贪心算法)

华东师范大学计算机科学技术系上机实践报告 课程名称：算法设计与分析年级：05上机实践成绩： 指导教师：柳银萍姓名：张翡翡 上机实践名称：贪心算法学号：10052130119上机实践日期：2007-4-10 上机实践编号：NO.2组号：上机实践时间：10:00-11:30 一、目的 了解熟悉掌握贪心算法实质并学会灵活运用，从而解决生活中一些实际问题。 二、内容与设计思想 1.超市的自动柜员机(POS)要找给顾客各种数值的现金，表面上看，这是一个很简单的任务，但交给机器办就不简单了。你作为一个计算机专家，要求写一个程序来对付这个“简单”的问题。 你的自动柜员机有以下的币种：100元，50元，20元，10元，5元，2元，1元。你可以假设每种钱币的数量是无限的。现在有一笔交易，需要找个客户m元，请你设计一个算法，使得找给顾客的钱币张数最少。 要求： 输入：第一行仅有一个整数n(0

(完整版)智能算法在柔性车间调度中的应用

智能算法在柔性作业车间调度中的应用摘要：为提高企业生产效率，合理的流水车间生产调度显得尤为重要。本文介绍了三种智能算法（蚁群算法、遗传算法、改进粒子群算法）在车间生产调度中的应用，主要介绍了算法的基本思想、模型结构、算法实现以及运用前景。对智能算法在生产调度中的应用做出总结。 关键字：智能算法；蚁群算法；遗传算法；改进粒子群算法；生产调度 0.前言 柔性作业车间调度问题(Flexible job-shop sche- duling problem, FJSP)是传统作业车间调度 问题的扩展，是实际生产中迫切需要解决的一类问 题。在传统的作业车间调度问题中，工件的每道工序只能在一台确定的机床上加工。而在柔性作业车间调度问题中，每道工序可以在多台机床上加工，并且在不同的机床上加工所需时间不同。柔性作业车间调度问题减少了机器约束，扩大了可行解的搜索范围，增加了问题的难度。 作业车间的主要特点是：n个工件需要在m台机器上进行加工，每个工件都有其独特的加工步骤，但无明显的顺序约束，并且加工时间是已知的，调度的目标是在不允许两个工件同时在同一台机器上加工的前提下，如何安排工件在每台机器上的加工顺序使这些工件能够尽快加工完毕[1]。 1.蚁群算法在作业车间的应用[2] 以3个工件2台机器的问题作为例子，如图1。 图1 三个工件两台机器的JSP问题 为确定先对哪个工件进行加工，需要设置一个初始节点O0，所有的蚂蚁最初都放置在O0。图1中除与O0相连的有向弧表示同一个工件的加工顺序，工件必须按照该顺序进行加工。其它则为无向弧。每个弧与表示节点间信息素的量和启发式距离的一对 值{αij, d ij}有关。d ij 通常为对节点 j 的第 i 步操作的加工时间，τij使用蚁周方式进行更新：其中，ρ是个系数，1?ρ表示在时间t和t+1之间信息素的蒸发，Q为常数，Tk为完成所有加工步骤后最短的总加工时间。初始时刻τij(0)= c（c为常数）。 这个规则包含了两个方面：(1)图1中所有边缘上的信息素都要蒸发；(2)完成所有的加工后要将该解的效果加到各边缘上。蒸发可以防止搜索局限在局部最小的邻域中，另一方面又能根据已有解的效果好坏来更新信息素，进行增强学习。 另一个关键的问题就是如何保证蚂蚁按照工件的工艺路线产生一组可行解。这里用到3个集合：对每个蚂蚁 k，首先要有集合G k，表示没有访问过的节点集合；S k 表示根据技术路线下一步允许访问的节点集合；还需要一个禁忌表，存放已经访问过的节点。在我们的例子中， G k ={1，2 ，3，4，5 ，6}，S k ={1，2 ，3}。转移概率是通过下式计算的： T ij 为工件i在机器j上的加工时间。每选择一个节点，该节点就被追加到禁忌表中并从G k和 S k中删除；如果被选的节点不是工件的最后一步，那该工件中紧邻的下一个节点会被加到Sk中。该过程一直重复到G k = φ。最后禁忌表中得到的节点的排列顺序就是蚂蚁 k 找到的解。 参数α和β决定了算法的收敛速度并对解的性能好坏有重要影响，同时蒸发常数也需要进行适当的调整以使搜索能在好的搜索空间中进行，并防止陷入局部最优的邻域中。

操作系统处理器调度算法C++程序

一、先来先服务算法 1．程序简介 先来先服务算法按照作业进入系统后备作业队列的先后次序挑选作业,先进入系统的作业将优先被挑选进入主存,创建用户进程,分配所需资源,然后,移入就绪队列.这是一种非剥夺式调度算法,易于实现,但效率不高.只顾及作业的等候时间,未考虑作业要求服务时间的长短,不利于短作业而优待长作业,不利于I/O繁忙型作业而有利于CPU繁忙型作业.有时为了等待场作业执行结束,短作业的周转时间和带全周转时间将变得很大,从而若干作业的平均周转时间和平均带权周转时间也变得很大。 2．分析 1．先定义一个数组代表各作业运行的时间，再定义一个数组代表各作业到达系统的时间，注意到达系统的时间以第一个作业为0基础（注意：若各程序都同时到达系统，则到达系统时间都为0）。 2．输入作业数。 3．然后运用循环结构累积作业周转时间和带权周转时间。 4．最后，作业周转时间和带权周转时间分别除以作业数即可得到平均作业周转时间和平均带权周转时间。 3．详细设计 源程序如下： #include #include using namespace std; int main() { int n,a[100],b[100]; double s[100],m[100],T=0,W=0; cout<<"请输入作业数:"<>n; cout<<"请分别输入各作业到达系统的时间:"<>b[i]; } cout<<"请分别输入各作业所运行的时间:"<>a[i];s[0]=0; s[i+1]=s[i]+a[i]; m[i+1]=(s[i+1]-b[i])/a[i]; T=T+s[i+1]-b[i]; W=W+m[i+1]; }

多处理机调度问题的一种近似算法

1997年7月 烟台大学学报(自然科学与工程版) July1997第10卷第3期 Journal of Yantai U niversity(N atural Science and Eng ineering) Vol.10No.3 多处理机调度问题的一种近似算法 程建纲 (烟台大学数学与信息科学系,烟台264005) 秦成林 (上海大学数学系,上海201800) 摘要 对多处理机调度问题P C max,给出一种近似算法.大量实例的计算结果 表明,本文的算法是非常有效的. 关键词 组合优化 排序 近似算法 随机算法 中图分类号 O224 多处理机调度问题P C max考虑有n个独立的工件和m台相同的机器,每一工件在并且仅在一台机器上加工一次,同时在加工时不允许中断加工的情形,所讨论的问题为:确定工件在各机器上的分配方案,使得从第一个被加工工件开始加工时刻起到全部工件加工完毕时刻止的时间跨度取极小.由于它在许多领域中都有广泛的应用,同时又是一个NP-C 问题,故其近似算法的研究受到广泛重视[1,2].本文对此问题通过随机迭代来给出一种近似算法,并通过大量的计算实例来表明对通常的P C max问题,本文的算法能够获得精度很高的近似解,而且在许多情况下也能获得问题的精确解. 下面首先给出本文中对此问题的数学描述形式.设m,n是正整数,R n+表示分量全为正数的n维向量的全体,同时为了方便起见,在本文中,对任意的向量,其分量始终用括号的形式表示,例如对l R n+,其相应的n个分量为l(1),l(2),!,l(n),另外对j所满足的条件组 ,以?{l(j)|条件组 }表示对所有j满足条件组 的分量l(j)做累加,以M表示由 {1,2,!,n}到{1,2,!,m}的映象全体所构成的空间,此时l R n+表示n个工件的工件组,其中第j个工件的加工时间为l(j),q M表示对工组的一个分配方案,它将第j个工件分配给第q(j)号机器,进而P C max问题为:对给定的l R n+,极小化问题 min max 1#i#m?{l(j)|q(j)=i} s.t q M(P)为了便于描述本文对此问题的算法,再引进以下一些记号,以R m表示通常的m维空间, [0,h]n表示R n中所有分量都不超过h的n维非负向量的全体,以S n表示{1,2,!,n}上的全体置换所构成的n次对称群,对l R n+, S n,l 表示向量(l( (1)),l( (2)),!, l( (n))),映象A:R n+?M%R n+的定义为A(l,q)的第n个分量A(l,q)(j)=?{l(k)|q(k)=q(j),k&j},映象D:R n+%S n的定义为:对y R n+,D(y)由以下两条件唯一确定:

算法设计与分析课程大作业

题目作业调度问题及算法分析 学院名称：计算机与信息工程学院 专业名称：计算机科学与技术

目录 《算法设计与分析》课程大作业.................................................................... 错误!未定义书签。一．动态规划算法解决流水作业调度. (4) 1、问题描述 (4) 2、算法分析 (4) 3. 算法的描述 (5) 4、部分算法实现 (6) 5. 运行结果 (8) 6、时空效率分析 (8) 二．贪心算法解多机调度问题 (8) 1、问题描述 (8) 2、算法分析 (9) 3.部分算法实现 (9) 4.计算复杂性分析 (11) 5. 运行结果 (12) 三．回溯法解决批作业调度问题 (12) 1.问题描述 (12) 2.算法思想 (13) 3. 部分算法实现 (14) 4.运行结果 (15) 5.时间复杂性分析 (15) 四．作业调度算法比较 (16) 五．课程学习总结 (16)

摘要： 在现代企业中，作业调度已成为提高资源利用率、从而提高企业运行效益的关键环节之一。把各个作业分配到车间现有的设备上，并确定它们的先后次序，这是一项复杂的工作本文就作业调度排序问题进行了研究，通过对几个经典作业调度算法的分析讨论，总结了各个算法对作业调度的求解过程，并给出了每个算法的复杂度及性能分析。 关键词：作业调度；动态规划；贪心算法；回溯法；

一．动态规划算法解决流水作业调度 1、问题描述 给定n 个作业，每个作业有两道工序，分别在两台机器上处理。一台机器一次只能处理一道工序，并且一道工序一旦开始就必须进行下去直到完成。一个作业只有在机器1上的处理完成以后才能由机器2处理。假设已知作业i 在机器j 上需要的处理时间为t[i,j]。流水作业调度问题就是要求确定一个作业的处理顺序使得尽快完成这n 个作业。 2、算法分析 直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。 在一般情况下，机器M1开始加工S 中作业时，机器M2还在加工其他作业，要等时间t 后才可利用。将这种情况下完成S 中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。 由流水作业调度问题的最优子结构性质可知， )}},{({min )0,(1i i n i b i N T a N T -+=≤≤（1）

02流水线车间生产调度的遗传算法MATLAB源代码

流水线车间生产调度的遗传算法MATLAB源代码 n个任务在流水线上进行m个阶段的加工，每一阶段至少有一台机器且至少有一个阶段存在多台机器，并且同一阶段上各机器的处理性能相同，在每一阶段各任务均要完成一道工序，各任务的每道工序可以在相应阶段上的任意一台机器上加工，已知任务各道工序的处理时间，要求确定所有任务的排序以及每一阶段上机器的分配情况，使得调度指标(一般求Makespan)最小。 function [Zp,Y1p,Y2p,Y3p,Xp,LC1,LC2]=JSPGA(M,N,Pm,T,P) %-------------------------------------------------------------------------- % JSPGA.m % 流水线型车间作业调度遗传算法 % GreenSim团队——专业级算法设计&代写程序 % 欢迎访问GreenSim团队主页→https://www.sodocs.net/doc/8d12064745.html,/greensim %-------------------------------------------------------------------------- % 输入参数列表 % M 遗传进化迭代次数 % N 种群规模(取偶数) % Pm 变异概率 % T m×n的矩阵，存储m个工件n个工序的加工时间 % P 1×n的向量，n个工序中，每一个工序所具有的机床数目 % 输出参数列表 % Zp 最优的Makespan值 % Y1p 最优方案中，各工件各工序的开始时刻，可根据它绘出甘特图 % Y2p 最优方案中，各工件各工序的结束时刻，可根据它绘出甘特图 % Y3p 最优方案中，各工件各工序使用的机器编号 % Xp 最优决策变量的值，决策变量是一个实数编码的m×n矩阵 % LC1 收敛曲线1，各代最优个体适应值的记录 % LC2 收敛曲线2，各代群体平均适应值的记录 % 最后，程序还将绘出三副图片：两条收敛曲线图和甘特图（各工件的调度时序图） %第一步：变量初始化 [m,n]=size(T);%m是总工件数，n是总工序数 Xp=zeros(m,n);%最优决策变量 LC1=zeros(1,M);%收敛曲线1 LC2=zeros(1,N);%收敛曲线2 %第二步：随机产生初始种群 farm=cell(1,N);%采用细胞结构存储种群 for k=1:N X=zeros(m,n); for j=1:n for i=1:m X(i,j)=1+(P(j)-eps)*rand;

模拟一种处理机调度算法讲解

课程设计报告 设计名称：模拟实现一种处理机调度算法 学生姓名： xxx 专业：计算机科学与技术 班别： xxxxxxxx 学号： xxxxxx 指导老师： xxxxx 日期： 2014 年 6 月 20 日

初始条件： 1．预备内容：阅读操作系统的处理机管理章节内容，对进程调度的功能以及进程调度算法有深入的理解。 2．实践准备：掌握一种计算机高级语言的使用。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） 1．模拟进程调度，能够处理以下的情形： ⑴能够选择不同的调度算法（要求中给出的调度算法）； ⑵能够输入进程的基本信息，如进程名、优先级、到达 时间和运行时间等； ⑶根据选择的调度算法显示进程调度队列； ⑷根据选择的调度算法计算平均周转时间和平均带权周 转时间。 2．设计报告内容应说明： ⑴需求分析； ⑵功能设计（数据结构及模块说明）； ⑶开发平台及源程序的主要部分； ⑷测试用例，运行结果与运行情况分析； ⑸自我评价与总结： i）你认为你完成的设计哪些地方做得比较好或比较出 色； ii）什么地方做得不太好，以后如何改正；

iii）从本设计得到的收获（在编写，调试，执行过程中 的经验和教训）； iv）完成本题是否有其他方法（如果有，简要说明该方 法）； 进程调度模拟设计——先来先服务、优先级法1、背景： 当计算机系统是多道程序设计系统时，通常会有多个进程或线程同时竞争CPU。只要有两个或更多的进程处于就绪状态，这种情形就会发生。如果只有一个CPU可用，那么就必须选择下一个要运行的进程。在操作系统中，完成选择工作的这一部分称为调度程序，该程序使用的算法成为调度算法。 进程调度的核心问题是采用什么样的算法把处理机分配给进程，好的算法将提高资源利用率，减少处理机的空闲时间，避免有些作业长期得不到相应的情况发生等，从而设计出受欢迎的操作系统。较常见的几种进程调度算法有：先来先服务调度算法；短作业优先调度算法；时间片轮转调度算法；优先级调度算法；高响应比优先算法和多级反馈队列调度算法等。 2.1设计目的 无论是在批处理系统还是分时系统中，用户进程数一般都多于处理机数、这将导致它们互相争夺处理机。另外，系统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略，动态地把处理机

贪 心 算 法

【贪心算法】思想 & 基本要素 & 贪心算法与局部最优 & 贪心算法与动态规划的区别 & 运用贪心算法求解问题 首先我们先代入问题来认识一下贪心算法涉及的问题 找钱问题 给顾客找钱，希望找零的钞票尽可能少，零钱种类和数量限定 找钱问题满足最优子结构 最快找零（贪心）：为得到最小的找零次数，每次最大程度低减少零额活动安排问题 设个活动都需要使用某个教室，已知它们的起始时间和结束时间，求合理的安排使得举行的活动数量最多 贪心：使得每次安排后，教室的空闲时间最多 解决过程如下： 贪心算法求得的相容活动集是最大的 第一步：证明最优解中包含结束时间最早的活动 设相容集 A 是一个最优解，其结束最早的活动为 a，则 ( A - { a }) U { 1 } 也是一个最优解 第二步：证明去掉结束时间最早的活动后，得到的子问题仍是最优的：反证法 理解贪心算法 贪心算法总是做出当前最好的选择 贪心选择的依据是当前的状态，而不是问题的目标

贪心选择是不计后果的 贪心算法通常以自顶向下的方法简化子问题 贪心算法求解的问题具备以下性质 贪心选择性质：问题的最优解可以通过贪心选择实现 最优子结构性质：问题的最优解包含子问题的最优解 贪心选择性质的证明 证明问题的最优解可以由贪心选择开始 即第一步可贪心 证明贪心选择后得到的子问题满足最优子结构 即步步可贪心 背包问题 问题描述：给定 n 个物品和一个背包。物品 i 的重量为 Wi ，价值为 Vi ，背包的容量为 c ，问如何选择物品或物品的一部分，使得背包中物品的价值最大？ 当 n = 3 ，c = 50 0-1背包问题：装入物品2、3，最大价值220 背包问题：装入物品1、2和2-3的物品3，最大价值240（贪心算法）贪心算法无法求解0-1背包问题，按贪心算法，0-1背包问题将装入物品1和2 贪心与局部最优 思考：为什么0-1背包可以用动态规划？而不能用贪心算法 贪心易陷入局部最优

处理器调度习题教学内容

处理器调度习题

处理器调度 选择题 ?当CPU执行操作系统代码时，则处理机处于( )。 ?A．执行态 B．目态 C．管态 D．就绪态 ?( )是机器指令的扩充，是硬件的首次延伸，是加在硬件上的第一层软件。 ?A．系统调用 B．操作系统 C．内核 D．特权指令 ?操作系统提供给程序员的接口是( )。 ?A．进程 B．系统调用 C．库函数 D．B和C ?用户程序向系统提出使用外设的请求方式是( )。 ?A．作业申请 B．原语 C．系统调用 D．I／O指令 ?当作业正常完成进入完成状态时，操作系统( )。 ?A．将输出该作业的结果并删除内存中的作业 ?B．将收回该作业的所占资源并输出结果 ?C．将收回该作业的所占资源及输出结果，并删除该作业 ?D．将收回该作业的所占资源及输出结果，并将它的控制块从当前的队列中删除 ?下列选项是关于作业和进程关系的描述，其中哪一个是不正确的( )。 ?A．作业的概念主要用在批处理系统中，而进程的概念则用在几乎所有的OS中。 ?B．作业是比进程低一级的概念。 ?C．一个作业至少由一个进程组成。 ?D．作业是用户向计算机提交任务的实体，而进程是完成用户任务的执行实体以及向系统申请分配资源的基本单位。 ?作业从后备作业到被调度程序选中的时间称为( )。 ?周转时间B．响应时间C．等待调度时间D．运行时间 ?设有三个作业J1，J2，J3，它们同时到达，运行时间分别为T1，T2，T3，且T1≤T2≤T3，若它们在一台处理机上按单道运行，采用短作业优先算法，则平均周转时间为( )。 ?A．T1+T2+T3 B．1／3(T1+T2+T3) ?C．T1+2／3T2+1／3T3 D．T1+1／3T2+2／3T3 ?从作业提交给系统到作业完成的时间间隔称为作业的( )。 ?A．中断时间 B．等待时间 C．周转时间 D．响应时间 ?设有四个作业同时到达，每个作业执行时间均为2 h，它们在一台处理机上按单道方式运行，则平均周转时间为( )。 ?A．1 h B．5 h C．2．5 h D．8 h ?FCFS调度算法有利于( )。 ?A．长作业和CPU繁忙型作业 B．长作业和I／O繁忙型作业 ?C．短作业和CPU繁忙型作业 D．短作业和I／O繁忙型作业 ?下列哪种说法不是SJ(P)F调度算法的缺点( )。 ?A．对于长作业(进程)不利 ?B．未考虑作业(进程)的紧迫程度 ?C．不能有效降低作业(进程)的平均等待时间 ?D．由于根据的是用户提供的估计执行时间，因此不一定真正做到短而优先。 ?选择排队进程中等待时间最长的进程被优先调度，该调度算法是( )。 ?A．先来先服务调度算法B．短进程优先调度算法 ?C．优先权调度算法D．高响应比优先调度算法 ?在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和( )相同。 ?A．先来先服务调度算法B．短进程优先调度算法

贪心算法求解多机调度问题

贪心算法求解多机调度问题 设有n项独立的作业{1,2,…, n},由m 台相同的机器加工处理。作业i 所需要的处理时间为台相同的机器加工处理。设有n 项独立的作业由ti。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分成更小的子作业。多机调度问题要求给出一种调度方案，能拆分成更小的子作业。多机调度问题要求给出一种调度方案，使所给的n 个作业在尽可台机器处理完。利用贪心策略，设计贪心算法解决多机调度问题，能短的时间内由m 台机器处理完。利用贪心策略，设计贪心算法解决多机调度问题，并计算其时间复杂度。 多机调度问题的一个实例： 多机调度问题的一个实例：项独立的作业{1,2,3,4,5,6,7}，要由三台机器M1, M2 ,M3 处理。各个作业所需处理。各个作业所需例如设有7 项独立的作业，要的处理时间分别为{2,14,4,16,6,5,3}。利用你设计的贪心算法，要的处理时间分别为。利用你设计的贪心算法，安排作业的处理顺序使得机器处理作业的时间最短。器处理作业的时间最短。 #include using namespace std; void Greedy(int t[],int n,int m); int main() { int n=7,m=3,t[]={2,14,4,16,6,5,3};//待分配的工作

Greedy(t,n,m); return 0; } void Greedy(int t[],int n,int m) { int flagn,flagm; int M[]={0,0,0,0,0,0,0,0}; for(int i=0;iM[j]) {flagm=j;} } M[flagm]=M[flagm]+t[flagn]; t[flagn]=0; //被选择过的机器时间调为0 cout<

贪心算法经典问题：活动安排,背包问题,最优装载,单源最短路径 Dijiksra,找零钱问题,多机调度

活动安排 public static int greedySelector(int [] s, int [] f, boolean a[]) { //s[]开始时间f[]结束时间 int n=s.length-1; a[1]=true; int j=1; int count=1; for (int i=2;i<=n;i++) { if (s[i]>=f[j]) { a[i]=true; j=i; count++; } else a[i]=false; } return count; } 背包问题 void Knapsack(int n,float M,float v[],float w[],float x[]) { Sort(n,v,w); //以每种物品单位重量的价值Vi/Wi从大到小排序 int i; for (i=1;i<=n;i++) x[i]=0; float c=M; for (i=1;i<=n;i++) { if (w[i]>c) break; x[i]=1; c-=w[i]; } if (i<=n) x[i]=c/w[i]; //允许放入一个物品的一部分 } 最优装载 void Loading(int x[], T ype w[], T ype c, int n) { int *t = new int [n+1]; //t[i]要存的是w[j]中重量从小到大的数组下标Sort(w, t, n); //按货箱重量排序 for (int i = 1; i <= n; i++) x[i] = 0; //O(n) for (int i = 1; i <= n && w[t[i]] <= c; i++) {x[t[i]] = 1; c -= w[t[i]];} //调整剩余空间 } 单源最短路径Dijiksra template void Dijikstra(int n, int v, Type dist[], int prev[], Type **c) { //c[i][j]表示边(i,j)的权，dist[i]表示当前从源到顶点i的最短特殊路径bool s[maxint]; for(int i= 1;i<=n; i++) { dist[i]=c[v][i]; s[i]=false;

操作系统实验一处理机调度算法的实现

实验报告 学院（系）名称：计算机与通信工程学院 姓名学号专业计算机科学与技术班级2009级3班实验项目实验一：处理机调度算法的实现 课程名称操作系统课程代码0668036 实验时间2011 年11月17日第3、4节 2011 年11月21日第7、8节 2011 年11月24日第3、4节 实验地点软件实验室7-216 批改意见成绩 教师签字： 实验内容： 1．设定系统中有五个进程，每一个进程用一个进程控制块表示。 2．输入每个进程的“优先数”和“要求运行时间”。 3．为了调度方便，将五个进程按给定的优先数从大到小连成就绪队列。用一单元指出队列首进程，用指针指出队列的连接情况。 4．处理机调度总是选队首进程运行。采用动态优先数算法，进程每运行一次优先数就减“1”，同时将运行时间减“1”。 5．若某进程运行时间为零，则将其状态置为“结束”,且退出队列。 6．运行所设计程序，显示或打印逐次被选中进程的进程名，以及进程控制块的动态变化过程。 实验要求： 1．详细描述实验设计思想、程序结构及各模块设计思路； 2．详细描述程序所用数据结构及算法； 3．明确给出测试用例和实验结果； 4．为增加程序可读性，在程序中进行适当注释说明； 5．认真进行实验总结，包括：设计中遇到的问题、解决方法与收获等； 6．实验报告撰写要求结构清晰、描述准确逻辑性强； 7．实验过程中，同学之间可以进行讨论互相提高，但绝对禁止抄袭。

【实验过程记录（源程序、测试用例、测试结果及心得体会等）】 程序运行代码如下： #include #include #include struct PCB{//定义进程控制块PCB，包括进程的名字，优先运行数，运行时间char name[20]; int pri; int time; struct PCB * next; }*k; struct LinkQueue{//链式队列节点类型定义 PCB * front; PCB * rear; }; LinkQueue InitQueue(){//链式队列初始化 LinkQueue Q; PCB * p; p=(PCB*)malloc(sizeof(PCB));//申请头结点存储空间 if(p){ Q.front=Q.rear=p; Q.front->next=NULL;//头结点指针域置空 return Q; }else{ printf("初始化队列失败，程序运行终止！\n");//初始化失败 exit(0); } } LinkQueue sort(LinkQueue Q,PCB * p){//定义将进程按给定的优先数从大到小连成就绪队列的函数 PCB *temp1; PCB *temp2; if(Q.rear==Q.front){ Q.front->next=p; Q.rear=p; }else{ temp1=Q.front; temp2=temp1->next; while(temp2->pri>=p->pri && temp2->next!=NULL){ temp1=temp2; temp2=temp1->next; }if(temp2->next==NULL && temp2->pri>=p->pri){ temp2->next=p; Q.rear=p;

matlab生产调度问题及其优化算法

生产调度问题及其优化算法（采用遗传算法与MATLAB编程） 信息014 孙卓明 二零零三年八月十四日

生产调度问题及其优化算法 背景及摘要 这是一个典型的Job-Shop动态排序问题。目前调度问题的理论研究成果主要集中在以Job-Shop问题为代表的基于最小化完工时间的调度问题上。一个复杂的制造系统不仅可能涉及到成千上万道车间调度工序，而且工序的变更又可能导致相当大的调度规模。解空间容量巨大，N个工件、M台机器的问题包含M ( N)! 种排列。由于问题的连环嵌套性，使得用图解方法也变得不切实际。传统的运筹学方法，即便在单目标优化的静态调度问题中也难以有效应用。 本文给出三个模型。首先通过贪婪法手工求得本问题最优解，既而通过编解码程序随机模拟优化方案得出最优解。最后采用现代进化算法中有代表性发展优势的遗传算法。文章有针对性地选取遗传算法关键环节的适宜方法，采用MATLAB 软件实现算法模拟，得出优化方案，并与计算机随机模拟结果加以比较显示出遗传算法之优化效果。对车间调度系列问题的有效解决具有一定参考和借鉴价值。 一．问题重述 某重型机械厂产品都是单件性的，其中有一车间共有A，B，C，D四种不同设备，现接受6件产品的加工任务，每件产品接受的程序在指定的设备上加工， 条件：1、每件产品必须按规定的工序加工，不得颠倒； 2、每台设备在同一时间只能担任一项任务。 （每件产品的每个工序为一个任务） 问题：做出生产安排，希望在尽可能短的时间里，完成所接受的全部任务。 要求：给出每台设备承担任务的时间表。 注：在上面，机器 A，B，C，D 即为机器 1，2，3，4，程序中以数字1，2，3，4表示，说明时则用A，B，C，D

第四章-贪心算法(模拟试题)

计算机与信息科学学院2010-2011学年第2学期模拟试卷 计算机算法设计与分析—第四章.贪心算法 本卷满分100分 完卷时间120分钟 一. 简答题（每小题2分，共20分） 1. 当一个问题具有 且具有 时可用贪心算法，如最小生成树问题（背包问题，活动安排问题等）。 2. 在动态规划可行的基础上满足 才能用贪心。 3. 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的 选择。 4. 动态规划算法通常以 的方式解各子问题，而贪心算法则通常 以 的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题 5. 贪心算法和动态规划算法都要求问题具有 性质，这是2类算法的一个共同点。 6. 当一个问题的最优解包含其子问题的最优解时，称此问题具有 。 7. 对于具有n 个顶点和e 条边的带权有向图，如果用带权邻接矩阵表示这 个图，那么Dijkstra 算法的主循环体需要 时间。这个循环需要执行n-1次，所以完成循环需要 时间。算法的其余部分所需要时间不超过 。 8. 0-1背包问题指：给定n 种物品和一个背包。物品i 的重量是Wi ，其价值为Vi ，背包的容量为C 。应如何选择装入背包的物品，使得装入背包中物品的 最大。 9. 有一批集装箱要装上一艘载重量为c 的轮船。其中集装箱i 的重量为Wi 。最优装载问题要求确定在 不受限制的情况下，将 装上轮船。 10. 多机调度问题要求给出一种作业调度方案，使所给的n 个作业在 由m 台机器加工处理完成。 二. 综合题（1-6题每题7分，7-8题每题9分，共60分） 1. 有4个物品，其重量分别为(4, 7, 5, 3)，物品的价值分别为(40, 42, 25, 12)，背包容量为10。试设计3种贪心策略,并给出在每种贪心策略下背包问题的解。 )(n O

企业战略混合遗传模拟退火算法解决多机调度问题

企业战略混合遗传模拟退火算法解决多机调度问题 Ting Bao was revised on January 6, 20021

★★★文档资源★★★ 摘要：将模拟退火引入遗传算法，构造混合遗传模拟退火算法。通过对具体多机调度问题的求解，表明混合遗传模拟退火算法的效率要优于单一的遗传算法和模拟退火算法。 关键词：多机调度；遗传算法；模拟退火算法；混合遗传模拟退火算法 作业调度问题是生产管理与控制的一个基本问题。按照加工设备数量和加工作业的流动方式，一般可分为单机调度、并行机调度、Flowshop调度、可重入式调度和Jobshop调度等多种类型。作业调度中的许多问题，不仅具有随机性、约束复杂、规模大及多目标冲突等特点，而且许多都属于NP完全问题，即使在单机情形也是如此。因此，如何寻求有效可行的调度求解方案，一直是生产管理与控制研究的热点和难点。 一、多机调度问题的数学模型 二、算法分析 自Davis首次将遗传算法（Genetic Algorithms，GA）引入到调度问题的研究中以来，进化算法（包括遗传算法）在制造生产零件和生产调度研究领域获得了广泛的应用，并取得了较好的优化效果。遗传算法用于求解某些并行多机调度问题也有不少的研究成果。遗传算法的优点是：不受搜索空间的****性假设的约束，不必要求诸如连续性、导数存在和单峰的假设，并且具有内在的并行性，收敛速度快，能够解决非常困难的寻优问题。当然，传统的遗传算法也有许多缺点，其中最为严重的是“过早收敛”问题。所谓“过早收敛”是指在搜索的初期，由于优良个体急剧增加使种群失去多样性，从而造成程序陷入局部，达不到全局最优解的现象。遗传算法的另一个缺陷是“GA欺骗”问题，即在GA的搜索过程中，有可能搜索到最优解然后又发散出去的现象。另外，遗传算法还有参数选择未能定量和不能精确定位最优解等缺陷。 模拟退火算法（Simulated Annealing，SA）又称为模拟冷却法、统计冷却法、Monte－Carlo退火法、随机松弛法和概率爬山法等。模拟退火算法是一种新的统计优化方法，其思想最早是由N．Metropolis等人借鉴统计力学中物质退火方法而提出的。1983年Kirkpatrick等人开展了一些富有成效的工作，成功地将该思想引入组合优化理论。模拟退火算法源于对固体退火过程的模拟，采用Meteropolis接受准则，并用一组称为冷却进度表的参数控制算法进程，使算法在多项式时间里给出一个近似最优解。模拟退火算法的主要优点之一就是能以一定的概率接收目标函数值不太好的状态。即算法不但往好的方向走也可向差的方向走；这使得算法即便落入局部最优的陷阱中，理论上经过足够长的时间后也可跳出来从而收敛到全局最优解。模拟退火算法的主要缺点是解的质量与求解时间长短之间的矛盾。为得到一个好的近似最优解，需要进行反复迭代运算，当问题的规模不可避免地增大时，缺乏可行的解决途径。

作业调度快速贪心算法

作业调度快速贪心算法 班级：08级通信三班学号：14081403173 姓名：阮晨 成绩：分 一、设计目的 1.掌握贪心算法的思想； 2.掌握贪心算法的典型问题，如作业调度问题； 3.进一步多级调度的基本思想和算法设计方法； 4.提高分析与解决问题的能力。 二、设计内容 1．任务描述 1）多段图问题简介 在无资源约束且每个作业可在等量的是时间内完成的作业调度问题中，可以拟定一个最优解的算法，制定如何选择下一个作业的量度标准，使得所选择的下一个作业在这种量度下达到最优。快速贪心算法利用减少作业移动—分配最晚时间片原则使得作业在最短的时间片内达到最大的效益值。 2）设计任务简介 设计快速贪心算法实现在效益p=(35, 30, 25, 20, 15, 10, 5, 1),时间期限 d=(4, 2, 4, 5, 6, 4, 5, 7)条件下的最大效益，输出作业的调度序列。 2．快速贪心算法的实现过程 已知n=8, p=(35, 30, 25, 20, 15, 10, 5, 1), d=(4, 2, 4, 5, 6, 4, 5, 7)。设计、编程实现作业调度快速贪心算法, 要求按作业调度顺序输出作业序列。 案例分析： 可用最晚空闲时间片序号数组 F[]。 存储截止期限值为 i 的作业可用的最晚空闲时间片序号。 初始状态: F[0:k]={0, 1, 2, 3, …, k-1, k},k = min { n, max {dj} } 竞争可用最晚空闲时间片的截止期限值集合 set[0:k] 在树结构表示下, 初值为： set[0:k]={{0,-1},{1, -1},{2, -1},{3, -1}, …,{k-1, -1},{k, -1}}. 如下表：