logo资料库

2018数模国赛B题-国二.doc

发布时间：2022-06-05 发布人：admin 分类：说明书 资料大小：0.48M 资料格式：doc 举报 版权申诉
第1页 / 共42页
第2页 / 共42页
第3页 / 共42页
第4页 / 共42页
第5页 / 共42页
第6页 / 共42页
第7页 / 共42页
第8页 / 共42页
资料共42页，剩余部分请下载后查看
    1.问题重述
    2.模型假设与约定
    3.符号说明及名词定义
    4.模型的建立与求解
    4.1针对第一种具体情况的建模以及算法求解
    4.1.1智能加工系统的抽象量化
    4.1.2 RGV的行为函数的详细解释
    4.1.3 CNC的行为函数的详细解释
    4.1.4智能RGV的动态调度策略与算法
    4.1.5智能RGV的动态调度策略的代码实现
    4.1.6 模型求解与分析
    4.2第二种具体情况的求解
    4.2.1第二种具体情况的抽象量化
    4.1.2 RGV的成员函数的详细解释
    4.1.3 CNC的成员函数的详细解释
    4.2.2刀具类型分配的选择模型
    4.2.3第二种具体情况的算法实现
    4.3第三种具体情况的求解
    4.3.1故障判断和维修时间的确定模型
    4.3.2基于智能RGV动态过程的改进模型
    4.3.3基于固定故障序号的静态改进模型
    5.模型评价
    5.1模型的优点
    5.2模型的缺点
    5.3模型的展望
    6.参考文献
    智能 RGV 的动态调度模型 摘要 本文通过建立智能 RGV 的贪心算法动态调度模型，利用 C++编程进行模型模 拟，给出了智能 RGV 在三种不同的具体情况下的调度策略和系统的作业效率。 针对第一种具体情况，我们利用 C++中类的抽象特性把 RVG 以及 CNC 抽象为不 同的类，每种类含有常量、变量（如位置量，时间量等）、行为函数（如 RGV 的移动行为，上下料行为，等待行为，CNC 的工作行为）。各种类的常量、变量 与行为函数会发生改变，在智能 RGV 的状态改变上（即动态调度），我们采用 了基于 ERD 算法（尽可能早地调度先到达的作业）和 SPT 算法（尽可能早地调度 作业长度短的作业）的智能 RGV 动态调度贪心算法模型。与此同时我们发现在 第一种具体情况的第一组数据中，是存在循环规律的，我们通过该循环规律得到 了第一种具体情况下的第一组数据的运行规律。随后，我们利用构建的智能 RGV 动态调度贪心算法模型进行编程处理。将题中所给的表 1 中系统作业参数的 3 组数据代入程序，求解出了程序模型下的 RGV 的调度策略和系统的作业效率。 最后我们用程序代码运行出的结果与循环规律得出的结果进行比较，从而验证了 程序的正确性。 针对第二种具体情况，我们把基于贪心算法的智能 RGV 动态调度模型进行了 改进，加入了加工两道工序所必须的常量、变量和行为函数，保证了贪心算法的 每步最优性。在建模的过程中，我们发现在第二种具体情况中各台 CNC 的刀具 类型对智能调度系统的工作效率有影响。因此为了得到更优的结果，我们讨论了 各台 CNC 的刀具类型的选择策略，得到了刀具类型分配的选择模型。针对得到 的新模型，我们进行了 C++程序编译并利用题中所给数据求解出了第二种具体情 况下智能 RGV 的调度策略和系统工作效率。 针对第三种具体情况，我们在第一种和第二种情况的基础上运用对 CNC 加入 了故障和维修的行为，当贪心算法进行最优解判断时，我们对其进行了一次最优 解故障判断，从而让 RGV 避开故障 CNC。此外，当 CNC 开始工作时，我们用基 于随机函数的算法对 CNC 进行了一次判断，判断 CNC 是否故障，故障以后我们 设置了参数使 CNC 会发生维修的行为，接着我们利用题中所给数据求解出了第 三种具体情况下的单次智能 RGV 的调度策略和系统工作效率，以及故障发生数， 故障发生的节点。除了依照 RGV 和 CNC 的动态行为得到的改进模型，我们还讨 论了一种基于固定故障序号的静态改进模型，这种模型提前确定会发生故障的物 料序号，能够制定不同故障发生情况下的应急调度，具有较特别的理论价值。 最后，我们给出了模型的优缺点，还给出了模型的评价和展望。 关键词：RGV 贪心算法 单机调度 ERD 算法 SPT 算法 C++ 1 / 42
    1.问题重述 问题给出了一个智能加工系统的示意图，该智能加工系统由 8 台计算机数控 机床、1 辆轨道式自动引导车、1 条 RGV 直线轨道、1 条上料传送带、1 条下料 传送带等附属设备组成。RGV 是一种无人驾驶、能在固定轨道上自由运行的智能 车。它能够根据指令自动控制移动方向和距离，并能够完成上下料以及清洗物料 等任务作业。针对三种具体情况： （1）一道工序的物料加工作业情况，每台 CNC 安装同样的刀具，物料可以 （2）两道工序的物料加工作业情况，每个物料的第一和第二道工序分别由 在任一台 CNC 上加工完成； 两台不同的 CNC 依次加工完成； （3）CNC 在加工过程中可能发生故障（据统计：故障的发生概率约为 1%） 的情况，每次故障排除（人工处理，未完成的物料报废）时间介于 10~20 分钟之 间，故障排除后即刻加入作业序列。要求分别考虑一道工序和两道工序的物料加 工作业情况。 完成两项任务： 任务 1：对一般问题进行研究，给出 RGV 动态调度模型和相应的求解算法； 任务 2：利用表 1 中系统作业参数的 3 组数据分别效检验模型的实用性和算法的 有性，给出 RGV 的调度策略和系统的作业效率，并将具体的结果分别填入附件 2 的 EXCEL 表中。 2.模型假设与约定 1）将轨道分为四个位置，CNC1 与 CNC2 位于轨道位置 0 处，CNC3 与 CNC4 位于轨道位置 1 处，CNC5 与 CNC6 位于轨道位置 2 处，CNC7 与 CNC8 位于轨 道 3 处； （2）时间的最短间隔为 1S； （3）除了第三种具体情况中的 CNC 会发生故障以外，其它具体情况中智 能加工系统的其余部件均运行正常； （4）开始时刻 RGV 在轨道位置 0 处，且开始时刻所有的 CNC 都处于空闲 状态，没有装载任何物料； （5）假设第三种具体情况中 CNC 发生故障的概率是 1%，且维修的时间服 从均匀分布； （6）每一个 CNC 发生故障的概率都是相同的，没有差异和记忆性 （7）若 CNC 在这一次作业中会发生故障，则故障发生时刻为开始工作的 时刻 （8）约定在第一轮上料过程中，CNC 不会发生故障 2 / 42
    3.符号说明及名词定义 符号 单位 含义 position now cnc _ rgv _ flag posCalculate n 1 STEP STEP 2 STEP 3 CLEAN move load clean wait :: CNC n count number - - - s - s s s s - - - - - s - RVG 当前位置 RVG 当前目标 RGV 有无熟料的判断参数 RGV 的移动时间 加工物序列号 RGV 移动一步的时间 RGV 移动两步的时间 RGV 移动三步的时间 RGV 进行清洗操作的时间 RGV 移动 RGV 上下料 RGV 清洗 RGV 等待 加工物序列号 CNC 剩余工作时间 CNC 编号 3 / 42
    CNC position :: CNC WORKTIME _ 1CNC CNC 0 CNCNUMBER countdown - s s s - CNC 位置 CNC 加工一道工序的时间 奇数 CNC 的上下料操作时间 偶数 CNC 的上下料操作时间 CNC 的数量 - 为了让 CNC 和 RGV 的时间同步的函数 P M iM v U 1q 2q 1T 2T % s s - - - - - - RGV 的调度系统的作业效率 各台 CNC 的总空闲时间之和 编号为 i 的 CNC 总空闲时间 效率平衡系数 效率平衡残数 装有第二种刀具类型的 CNC 数量 装有第二种刀具类型的 CNC 数量 CNC 加工第一道工序的时间 CNC 加工第二道工序的时间 4 / 42
    4.模型的建立与求解 4.1 针对第一种具体情况的建模以及算法求解 因为智能加工系统的每班次作业时间固定，为 8 小时，而所有的熟料均由 CNC 加工而成，若各台 CNC 的空闲时间总和 M 越小，则系统的作业效率的工作效率 越高，且工作效率为 P  100%  M 8 *8 h （4.1-1） 因而我们的智能加工系统建模算法的目标函数记为 min( f ) min(  M ) min(   M )i 4.1.1 智能加工系统的抽象量化 为了建立第一种具体情况的模型，我们对 RGV 和 CNC#进行了必要的抽象量化 （1） RGV 的抽象量化 符号类型 符号 说明 position now cnc _ RVG 当前位置 RVG 当前目标 变量 rgv _ flag RGV 有无熟料的判断参数 posCalculate RGV 的移动时间 RGV 常量 行为函数 n 1 STEP STEP 2 STEP 3 CLEAN move load 5 / 42 加工物序列号 RGV 移动一步的时间 RGV 移动两步的时间 RGV 移动三步的时间 RGV 进行清洗操作的时间 RGV 移动 RGV 上下料
    clean wait RGV 清洗 RGV 等待 （2）CNC 的抽象量化 符号类型 符号 说明 变量 CNC position :: count number CNC position :: 加工物序列号 CNC 剩余工作时间 CNC 编号 CNC 位置 常量 CNC CNC WORKTIME _ CNC 加工一道工序的时间 1CNC CNC 0 奇数 CNC 的上下料操作时间 偶数 CNC 的上下料操作时间 CNCNUMBER CNC 的数量 行为函数 countdown 为了让 CNC 和 RGV 的时间同步 4.1.2 RGV 的行为函数的详细解释 RGV RGV : : ( ) （1） RGV 类构造函数，定义 RGV 类对象时实现成员变量的初始化。 具体成员变量初始化情况：RGV 初始位置 Position=0，初始最优解（RGV 当前操 flag 空闲，加工总耗时 now cnc =1，RGV 初始状态 _ rgv _ 作 CNC 台的编号） 为 0，加工熟料总数为 0。 6 / 42
    void RGV Init CNC p * ::   RGV 第一轮作业情况特殊，仅需考虑 RGV“移动”和“上料”动作。 int RGV posCalculate int pos :: 1,  int pos 2  （2） （3） 该函数返回 RGV 从位置 1pos1 移动到位置 2pos2 需要的时间。主要由函数 RGV：：move 调用。 void RGV move CNC p * ::   （4） _ next cnc ； ② 比 较 当 前 对 象 该函数抽象 RGV 类的“运动”作业。①先用“贪心算法”找到 RGV 下一 now cnc 和 最 优 对 象 移 动 目 标 的 最 优 解 next cnc ，如果当前对象不是最优对象，则移动向最优对象；③判断是否需要 等待，如果最优 CNC 工作台当前忙碌（CNC 工作剩余时间 count 不为 0），则等 待。 _ _ void RGV load CNC p * ::   （5） 该函数抽象 RGV 类的“上下料”作业。①判断当前 CNC 工作台编号的奇偶性， 选择奇数号上下料时间 CNC1 还是偶数号上下料时间 CNC2；②完成“上下料” 作业的同时，将此时 RGV 中的“加工物序列总数 RGV::n”和“CNC 加工完成一 CNC WORKTIME ”赋给当前 CNC 工作台的“加工 个一道工序的物料所需时间 _ 物序号 CNC n ”和“加工剩余时间 :: CNC count ”。 :: * void RGV clean CNC p ::   （6） 该函数抽象 RGV 类的“清洗”作业。将“完成清洗时间 CLEAN”同步到“总 时间”和所有 CNC“加工剩余时间  * void RGV wait CNC p ::  CNC count ”。 :: （7） 该函数抽象 RGV 类的“等待”作业。将“完成清洗时间 CLEAN”同步到“总时 间”和所有 CNC“加工剩余时间 CNC count ”。 :: 4.1.3 CNC 的行为函数的详细解释 （8） RGV::RGV() RGV 类构造函数，定义 RGV 类对象时实现成员变量的初始化。 具体成员变量初始化情况：RGV 初始位置 Position=0，初始最优解（RGV 当前操 7 / 42
    作 CNC 台的编号）now_cnc=1，RGV 初始状态 rgv_flag 空闲，加工总耗时为 0， 加工熟料总数为 0。 （9）void RGV::Init(CNC *p) RGV 第一轮作业情况特殊，仅需考虑 RGV“移动”和“上料”动作。 （10）int RGV::posCalculate(int pos1, int pos2) 该函数返回 RGV 从位置 1pos1 移动到位置 2pos2 需要的时间。主要由函数 RGV：：move 调用。 （11）void RGV::move(CNC *p) 该函数抽象 RGV 类的“运动”作业。①先用“贪心算法”找到 RGV 下一 移动目标的最优解 next_cnc；②比较当前对象 now_cnc 和最优对象 next_cnc，如 果当前对象不是最优对象，则移动向最优对象；③判断是否需要等待，如果最优 CNC 工作台当前忙碌（CNC 工作剩余时间 count 不为 0），则等待。 （12）void RGV::load(CNC *p) 该函数抽象 RGV 类的“上下料”作业。①判断当前 CNC 工作台编号的奇偶性， 选择奇数号上下料时间 CNC1 还是偶数号上下料时间 CNC2；②完成“上下料” 作业的同时，将此时 RGV 中的“加工物序列总数 RGV::n”和“CNC 加工完成一 个一道工序的物料所需时间 CNC_WORKTIME”赋给当前 CNC 工作台的“加工物 序号 CNC::n”和“加工剩余时间 CNC::count”。 （13）void RGV::clean(CNC* p) 该函数抽象 RGV 类的“清洗”作业。将“完成清洗时间 CLEAN”同步到“总 时间”和所有 CNC“加工剩余时间 CNC::count”。 （14）void RGV::wait(CNC* p) 该函数抽象 RGV 类的“等待”作业。将“完成清洗时间 CLEAN”同步到“总时 间”和所有 CNC“加工剩余时间 CNC::count”。 4.1.4 智能 RGV 的动态调度策略与算法 对于智能 RGV 的动态调动策略，我们选择采用基于 ERD 算法和 SPT 算法的 贪心算法求取智能 RGV 动态调度策略的局部最优解。 当 RGV 空闲时，选择判断当前的目标 CNC 是否为局部最优解，即判断 当 m 前的 iM 是否为最小值，判断情况根据基于 ERD 算法和 SPT 算法的贪心算法有两 种抽象情况 （1）先来先服务法（ERD 算法） 尽可能早地调度先到达的作业, 以充分利用各作业到达 时刻之间的时间段。 m 如：当前目标 CNC 的工作剩余时间为 count ，我们选择工作剩余时间为 为 （2）短作业优先法（SPT 算法） j m count  ，比较目标 min count count ,m j j CNC 的工作剩余时间  的目标。 尽可能早地调度作业长度短的作业(简称短作业), 使得其完成时间对后续 8 / 42
    分享到：
    赞 收藏

    相关推荐

    资料库

    考试认证

    共收录20637份资料，累计11个分类，关注成员有19位，主要包括：真题,美赛,软考,PMP,Linux/Unix认证,思科认证,微软认证,Oracle认证,华为认证,软考等考,其它

    热门标签

    真题 美赛 软考 PMP Linux/Unix认证 思科认证 微软认证 Oracle认证 华为认证 软考等考 其它

    最新资料