算子调度算法

操作系统实验报告一

班级：08网络工程

一、 实验目的

通过这次实验，加深对进程概念的理解，进一步掌握进程状态的转变、进程调度的策略及对系统性能的评价方法。

二、 实验内容

设计程序模拟进程的先来先服务FCFS和短作业优先SJF调度过程。假设有n个进程分别在T1, … ,Tn时刻到达系统，它们需要的服务时间分别为S1, … ,Sn。分别采用先来先服务FCFS和短作业优先SJF进程调度算法进行调度，计算每个进程的完成时间、周转时间和带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。

三、 要求

程序要求：

1）进程个数n；每个进程的到达时间T1, … ,Tn和服务时间S1, … ,Sn；选择算法1-FCFS，2-SJF。

2）要求采用先来先服务FCFS和短作业优先SJF分别调度进程运行，计算每个进程的周转时间和带权周转时间，并且计算所有进程的平均周转时间和带权平均周转时间；

3）输出：要求模拟整个调度过程，输出每个时刻的进程运行状态，如“时刻3：进程B开始运行”等等；

4）输出：要求输出计算出来的每个进程的周转时间、带权周转时间、所有进程的平均周转时间以及带权平均周转时间。

实验要求

1）上机前认真复习FCFS和SJF进程调度调度算法，熟悉进程调度的执行过程；

2）上机时独立编程、调试程序；

3）根据具体实验要求，完成好实验报告（包括实验的目的、内容、要求、源程序、实例运行结果截图、发现的问题以及解决方法）。

四、 源程序

#include

#include

#include

using namespace std;

void FCFS();

void SJF();

static const int MaxNum=100; int ArrivalTime[MaxNum];//到达时间

int ServiceTime[MaxNum];//服务时间

int FinishTime[MaxNum];//完成时间

遗传算法编码及算子简介

遗传算法主要是通过遗传操作对群体中具有某种结构形式的个体施加结构重组处理，从而不断地搜索出群体中个体间的结构相似性，形成并优化积木块以逐渐逼近最优解。由此可见，必须把群体中的个体转化成按一定基因结构组成的染色体或个体，即编码。编码原则包括两条：

1.有积极积木块编码规则，即所定编码应当易于生成所求问题相关的短距和低阶的积木块。

2.最小字符集编码规则，即所定编码应用最小字符集以使问题得到自然的表示或描述。

规则一是基于模式定理和积木块假设；规则二提供了一种更为实用的编码规则。评估编码策略常采用的规范有：

1.完备性：问题空间中的所有点都能作为GA空间的点表现。

2.健全性：GA空间中的染色体能对应所有问题空间中的候选解。

3.非冗余性：染色体和候选解一一对应。

这些评估规范是独立于问题领域的普遍准则。对某个具体的应用领域而言，应该客观化地比较和评估该问题领域中所用的编码方法。应用遗传算法进行优化，首先将问题描述成串的形式，以模拟染色体。选择何种编码方式对算法的运行有很大的影响。现在，流行的观点认为二进制编码能在相同的范围内表示最多的模式，能充分地体现所谓的隐含并行性。但是，二进制编码方式的精度依赖于染色体的基因位数及设计变量的范围。因而对于高精度、多变量问题，n值需很大，降低遗传算法的收敛速度。另外，二进制编码不直接反映真实的设计空间。其它的编码方式还有：格雷码编码、浮点编码、树结构编码 、参数动态编码和多维编码等。

遗传算法主要有选择、交叉和突变算子

选择算子

遗传算法使用选择算子或称复制算子来对种群中的个体进行优胜劣汰操作：选择算子使适

应性高的个体在后代中生存的概率较大，而适应度低的个体生存的概率很小甚至被淘汰。遗传算法中的选择操作就是来确定如何从父代群体中按某种方法选取那些个体以传到下一 代群体的一种遗传算法。选择操作是建立在群体中个体的适应度评价基础上的。选择操作的主要目的是为了避免基 因缺失、提高全局收敛性和计算效率。在遗传算法中级很重要的作用。

车辆调度方法

车辆调度是一个关键的管理环节，尤其对于物流行业来说，合理的车辆调度方法能够提高运输效率，降低成本，增强市场竞争力。本文将介绍一些常用的车辆调度方法，并探讨其优缺点。

一、先来先服务（First Come First Serve，FCFS）方法

先来先服务是最简单的车辆调度方法之一，即按照车辆到达的先后顺序进行调度。这种方法操作简单，适用于车辆任务较少、服务时间相对稳定的情况下。然而，FCFS方法存在一些问题。首先，如果某辆车遇到了较长的等待时间，可能会导致运输周期延长，影响整体运输效率。其次，车辆到达的时间并不一定能够反映任务的紧急程度，因此在某些情况下可能无法满足客户的需求。

二、最短任务时间优先（Shortest Job First，SJF）方法

最短任务时间优先方法是根据任务所需的时间长短进行车辆调度。该方法优先分配任务时间最短的车辆去执行，以最大限度地提高车辆的利用率。SJF方法适用于任务时间变化不大、需要高效完成的情况。然而，该方法也存在一些问题。一方面，SJF方法容易导致优先级低的任务长时间得不到调度，影响用户体验。另一方面，如果任务时间没有正确估计，可能导致不能按时完成任务。

三、最早截止时间优先（Earliest Due Date，EDD）方法

最早截止时间优先方法是根据任务的最后期限进行车辆调度。该方法优先安排最早截止时间的任务，以确保任务能够按时完成。EDD方法适用于任务有严格截止时间要求的情况，例如快递配送。然而，EDD方法也存在一些问题。一方面，优先处理最早截止时间的任务可能会导致其他任务的延误，影响整体运输效率。另一方面，如果任务的截止时间没有正确估计，可能导致过早或过晚完成任务。

四、遗传算法（Genetic Algorithm，GA）方法

遗传算法是一种模拟自然选择和遗传机制的优化算法，通过遗传算子（交叉、变异）对种群进行进化，以获得最优解。在车辆调度中，遗传算法可以应用于选择合适的车辆进行任务调度，以最大限度地提高运输效率。相比于前面介绍的方法，遗传算法是一种更为复杂、高效的调度方法。然而，遗传算法也存在一些问题。一方面，遗传算法的性能受到参数设置和初始解的影响，需要进行精细的调参和优化工作。另一方面，遗传算法适用于综合考虑多个调度因素的场景，但对于一些特定的调度要求，可能需要进行定制化的改进。

２０１２年第３１卷第ｌＯ期　传感器与微系统（Ｔｒａｎｓｄｕｃｅｒ　ａｎｄ　Ｍｉｃｒｏｓｙｓｔｅｍ　Ｔｅｃｈｎｏｌｏｇｉｅｓ）　１２５　

基于贪心算法和遗传算法的仓储车辆调度算法　

王友钊，彭宇翔，潘芬兰　

（浙江大学仪器科学与工程学系，浙江杭州３１００２７）　

摘要：针对仓储车辆调度问题提出一种基于贪心算法与遗传算法的调度算法。它主要利用遗传算法为　框架筛选、进化出高效的调度方案，算法又融合了贪心算法对调度中的任务排序进行了快速优化。此融合　使得遗传算法的编码简便，排除了不可行解的可能，从而使得算法性能大大提高。算法已经Ｃ＋＋语言编　程实现，实验分析证明：算法有效地提升了调度方案的效率。　关键词：遗传算法；贪心算法；任务调度；仓储管理；融合　中图分类号：ＴＰ３９１　文献标识码：Ａ　文章编号：１０００－９７８７（２０１２）１０－０１２５－０４　

Ｓｃｈｅｄｕｌｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｖｅｈｉｃｌｅｓ　ｉｎ　ｗａｒｅｈｏｕｓｅｓ　

ｂａｓｅｄ　ｏｎ　ｇｒｅｅｄｙ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　

ＷＡＮＧ　Ｙｏｕ—ｚｈａｏ，ＰＥＮＧ　Ｙｕ—ｘｉａｎｇ，ＰＡＮ　Ｆｅｎ－ｌａｎ　（Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｉｎｓｔｒｕｍｅｎｔ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｚｈ￣ｉａｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，　Ｈａｎｇｚｈｏｕ　３１００２７，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｉｎ　ｖｉｅｗ　ｏｆ　ｓｃｈｅｄｕｌｉｎｇ　ｐｒｏｂｌｅｍ　ｏｆ　ｖｅｈｉｃｌｅｓ　ｉｎ　ｗａｒｅｈｏｕｓｅｓ，ａ　ｓｃｈｅｄｕｌｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｇｒｅｅｄｙ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｐｒｅｓｅｎｔｅｄ．Ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｕｓｅｓ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ａｓ　ｉｔｓ　ｆｒａｍｅ，ａｎｄ　ｔｈｅ　ｍｏｓｔ　ｅｆｆｉｃｉｅｎｔ　ｓｃｈｅｄｕｌｉｎｇ　ｓｃｈｅｍｅ　ｉｓ　ｓｅｌｅｃｔｅｄ　ａｆｔｅｒ　ｅｖｏｌｕｔｉｏｎ．Ｔｈｅ　ｆｕｓｅｄ　ｇｒｅｅｄｙ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｒｅｓｐｏｎｓｉｂｌｅ　ｆｏｒ　ｔｈｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｏｆ　ｔａｓｋｓ　ｓｏｒｔｉｎｇ．Ｉｔ　ｍａｋｅｓ　ｔｈｅ　ｃｏｄｉｎｇ　ｏｆ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｃｏｎｖｅｎｉｅｎｔ　ａｎｄ　ｅｘｃｌｕｄｅｓ　ｉｍｐｒａｃｔｉｃａｂｌｅ　ｓｏｌｕｔｉｏｎ．Ｔｈｅｒｅｆｏｒｅ　ｔｈｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｅｎｈａｎｃｅｄ　ｅｘｔｒｅｍｅｌｙ．Ｔｈｅ　ｓｃｈｅｄｕｌｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｈａｓ　ｂｅｅｎ　ｒｅａｌｉｚｅｄ　ｂｙ　Ｃ＋＋ｐｒｏｇｒａｍｍｉｎｇ．Ｅｘｐｅｒｉｍｅｎｔａｌ　ａｎａｌｙｓｉｓ　ｄｅｍｏｎｓｔｒａｔｅｓ　ｔｈａｔ　ｔｈｅ　ｅｆｆｉｃｉｅｎｃｙ　ｏｆ　ｓｃｈｅｄｕｌｉｎｇ　ｈａｓ　ｂｅｅｎ　ｐｒｏｍｏｔｅｄ．　Ｋｅｙ　ｗｏｒｄｓ：ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ；ｇｒｅｅｄｙ　ａｌｇｏｒｉｔｈｍ；ｔａｓｋ　ｓｃｈｅｄｕｌｉｎｇ；ｗａｒｅｈｏｕｓｅ　ｍａｎａｇｅｍｅｎｔ；ｆｕｓｉｏｎ