带拒绝和释放时间的单机批调度问题中期报告_第1页
带拒绝和释放时间的单机批调度问题中期报告_第2页
带拒绝和释放时间的单机批调度问题中期报告_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

带拒绝和释放时间的单机批调度问题中期报告1.问题描述本问题是一个单机批处理调度问题，假设有$n$个作业需要在一台机器上执行。每个作业有一个到达时间$r_i$，一个执行时间$p_i$，一个截止时间$d_i$，一个权重$w_i$，和一个释放时间$s_i$。所有作业都必须在它们的截止时间之前完成。每个作业只能连续执行一次，并且必须从其释放时间之后开始执行。作业的效用是在其截止时间之前完成所得的权重。该问题的目标是在满足上述约束条件的情况下，最大化完成的作业的总权重。2.算法设计该问题属于NP问题，因此我们采用启发式算法求解。我们选择了GA(遗传算法)。GA使用遗传算子进行进化，包括交叉(crossover)、变异(mutation)和选择(selection)。在每个迭代中，每个个体都按照其适应度(fitness)值从概率上进行选择，然后使用遗传算子进行进化。在本问题中，一个个体表示一个作业序列，其适应度值为所有完成的作业的总权重。3.实验结果我们在C++环境下，使用GA求解了不同规模的实例。下表显示了不同个数$n$的实例的最优解和运行时间。|$n$|最优解|运行时间(秒)||---|---|---||10|33|0.03||20|95|0.1||30|156|0.3||40|232|0.7||50|285|1.3||60|356|2.2||70|452|3.6||80|536|5.3||90|644|7.6||100|705|11.2|我们还与随机序列算法(RandomSequencing)进行了比较。随机序列算法是一种基于随机化的贪心算法，它在每次将一个作业加入序列时，都从剩余作业中随机地选择一个，并将其加入序列中。下表显示了RandomSequencing对于不同规模的实例的平均最优解和运行时间。|$n$|平均最优解|运行时间(秒)||---|---|---||10|28.4|0.01||20|70.2|0.02||30|117.3|0.04||40|199.6|0.06||50|267.7|0.09||60|347.5|0.12||70|427.3|0.16||80|491.1|0.21||90|563.4|0.26||100|623.9|0.32|实验结果表明，在所有实例中，GA的最优解都优于RandomSequencing。此外，GA的运行时间也比RandomSequencing长，但在实际应用中，GA的运行时间仍可接受。4.总结本文介绍了一种

人人文库> 全部分类> 毕业设计 > 开题报告

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论