下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、最优时间表问题问题描述 一台精密仪器的工作时间为 n 个时间单位。与仪器工作时间同步进行若干仪器维修程序。一旦启动维修程序,仪器必须进入维修程序。如果只有一个维修程序启动,则必须进入该维修程序。如果在同一时刻有多个维修程序,可任选进入其中的一个维修程序。维修程序必须从头开始,不能从中间插入。一个维修程序从第s个时间单位开始,继续 t个时间单位,则该维修程序在第s+t-1个时间单位结束。为了提高仪器使用率,希望安排尽可能少的维修时间。 输入文件示例 输出文件示例 input.txt output.txt 15 6 11 1 2 1 6 4 11 8 5 8 1 11 5 问题分析l最优子结构性质
2、 设( R(t0,T0) , R(t1,T1), R(tm,Tn) 是所给最优时间表问题的一个最优解,即不存在tj,使tm+Tntj, 那么( R(t0,T0) , R(t1,T1), R(tm-1,Tn-1)是ttm的最优时间表问题的一个最优解. 反证法,显而易见.l递归关系设S(i)表示执行R(ti,Tj) 后用于维修的最少时间。则Min S(i) = Min S (i1) +T(Ri) 简单的说,就是要求在所给的维修集合中选出某一极大相容维修子集合,使其所用时间最少。 对所有维修的起始时间进行排序。(t0,t1,,tk)(titj,ij)。R(tk,T)表示起始时间为tk,执行时间为T的维修。算法描述 建立一个n位长的数组S,每位表示一个时间。对任意维修R(tk,T)(tk+Tn),它要么进行,要么不进行。 Rtk,T要进行,则要么k0,要么在tk1到tk之间某点tx有某个维修完成。令S(tk+T-1)=S(tx)+T,表示执行Rtk,T后所用的维修时间。则可求出所有执行Rtk,T后的维修时间并求的最小值。以此类推,即可求出所有可能极大相容子集的最少维修时间。算法时间复杂性:算法的时间复杂性与工作时间的范围n
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 地泵建设合同范例
- 扎染课程设计必要性
- 教资课程设计初中历史
- 绿化官网合同范例
- 修正药业购销合同范例
- 外贸报价发票合同范例
- 权利转移合同范例
- 2024年柔性导轨项目可行性研究报告
- 养猪厂劳务承包合同范例
- 2024年中国单叉单火庭院灯市场调查研究报告
- 行政事业单位内部控制规范专题讲座
- 唐山房地产市场月报2024年08月
- 少儿美术课件国家宝藏系列《鸱吻》
- 端午节粽子购销合同
- 污水站托管运营合同范本
- 第18课《我的白鸽》教学设计++2024-2025学年统编版语文七年级上册
- 小学科学苏教版五年级上册全册知识点(2022新版)
- 第一单元(单元测试)-2024-2025学年三年级上册道德与法治 统编版
- 冀教版四年级上册数学计算题大全1000道带答案
- 新零售部工作手册
- 校园文明值周总结
评论
0/150
提交评论