硕士论文--基于启发式调度规则的车间作业计划算法及仿真研究

硕士论文--基于启发式调度规则的车间作业计划算法及仿真研究内容摘要：

有任务所包括的操作顺序是相同的即相当于具有相同 的工艺路线。 若每台机器对任务的加工顺序都 相同 ,则退化为置换调度问题。 单件车间作 业计划问题是最一般的调度问题。 包括多台机器 ,每个任务包括多个操作 ,操作的顺序不 尽相同。 显然 ,平行机调度问题和流水车间作业计划问题均是单件车间作业计划问题是特 例。 ..平行机调度问题模型 平行机问题是车间作业计划问题的一个子集 ,是最为活跃的研究分支之一。 一般平 行机问题可描述为 :给定机器集和工件集 ,。 其中 ,机器数量 ,可以为同型机或同 类机 ,机器不存在准备时间即零时刻可用。 各工件互相独立 ,投放时间为零 ,不存在交 货期约束。 每个工件只包括一道加工工序。 只需要在机器集中的 一台机器上加工一次。 工件的加工遵从不抢占规则。 要求将工件集 /分派到机器集上 ,并且确定加工次序 ,使 得某项目标达到最优。 ..流水线车间作业模型 流水车间作业计划一般可以描述为 :刀个工件在台机器上加工 ,一个工件分为道 工序 ,每道工序要求不同的机器加工。 刀个工件在台机器上的加工顺序是相同 ,工件 在机器 ,上的加工时间是给定的 ,设为甜 ,?,盯。 ,?,。 调度问 题的目标函数是求个工件的最优加工顺序 ,使最大流经时间最小。 对流水线车间作业计划问题常作如下假设 : 每个工件在机器上的加工顺序相同 ,且是确定的。 每台机 器在每个时刻只能加工某个工件的某道工序。 一个工件不能同时在不同机器上加工。 工序的准备时间与顺序无关 ,且包含在加工时间中。 ..单件车间作业计划问题模型 单件车间作业计划问题是一类与制造过程中实际生产调度密切相关的组合优化问题。 许多具体的单件车间作业计划问题都是通过对实际问题的分析和抽象 ,在基本的单件车间 作业计划问题模型的基础上提出来的。 为研究单件车间作业计划首先必须细致分析企业的 生产环境、生产过程及生产特点 ,从而建立起与企业实际生产过程、生产环境及生产特点 相适应的动态单件车间作业计划模型。 经典 的单件车间作业计划问题的数学问题描述为 :设该系统生产 ,个工件 ,表示为集 合 ,?,刀 ,生产系统内有朋台机器 ,表示为集合 ,?,聊 ,每个工件需要经过硕士学位论文 第页 武汉科技大学 若干个工序完成 ,若磕表示第个工件的射道工序在第台机器上加工的工序 ,其开始加 工时间和需要加工的时间分别记为 %和 %。 工件的最后一道工序的开始加工时间和需要 加工时间分别记为 amp。 和砭。 工件的投放时间和交货期分别记为和西。 是工件有序工 序对【易 ,%】集合 ,其中 ,%优先于 %。 风是使用机器后的所有工序 %的集合。 如果目标 函数为最小化最大完工 时间 ,或者最小生产周期 ,即如何安排加工使得加工所有工件的时 间最短。 车间作业计划问题采用整数线性规划模型描述为 : ∈ . 朋瓦。 . ∈ . 『 ,∈ ,?他 ‰一歌≥ % 【 %,%】∈只 ,∈ 七∈ . %一歌≥‰或‰一‰≥‰ 【 %,%】∈墨 ∈ 七∈ ∈ ,?啊 . ,。 ≤ :嗽≤西一 其中 ,式 .表示工序顺序约束 ,式 .表示资源约束 ,式 .表示投放时间和交货 期约束。 对于上述经典的车间作业计划问题 ,除工艺约束之外 ,需要对工件、机器、加工时间 和缓冲器等还将引入的一些假设【】 : 对工件的假定包括 : 从加工过程开始起 ,工件即可被加工 ,或者 ,也可将此假设减弱为 ,对不同类 型的工件需要有一个固定的相应准备时间 ,经过准备时间后即可开始加工。 每一个操作限定为不能由多于一台的机器来进行加工。 每个操作一旦开始 ,直到完成为止 ,不会被另外的操作所中断。 不存在可选工艺路线即各个工件必须按照指定的工艺路线依次在机器上加工。 各类工件之间不存在加工上的优先数 ,即对生产线而言 ,每类工件加工的重要 程度被认为是等同的。 对每个操作均允许等待。 也就是说 ,如果前一个操作还未完成即仍在进行 ,那 么后继的操作将需要等待。 这意味着 ,中间等待时间或者 库存被认为是允许的。 整个加工过程中 ,每个工件只能被一台机器加工一次。 对机器的假定包括 : 在从加工过程开始的计划时间内 ,所有台机器均为有效的。 也即 ,所有机器 从一开始就处于可加工状态 ,且在计划时间内不会出现损坏和需要修理的情况。 在生产线中 ,只有一台同一类型的机器 ,不用机器之间彼此独立。 在同一时刻 ,每台机器只能从事一个操作。 机器之外的其他资源无限制。 对加工时间的假定包括 : 对每个操作 ,其作业时间是事前给出的 ,且在整个计划时间内保持为常数。 除非特别说明 ,一般总认为 ,加工时间中已经包括了设置时间 ,即已经包括了第页 武汉科技大学 硕士学位论文 工件在机器之间的传送时间和装卸时间。 对缓冲器的假定包括 : 除非特别加以说明 ,缓冲器的容量均假设为充分大。 按照车间作业计划问题的特点及分类 ,依据本文研究的对象单件订货型企业的车间级 作业调度 ,文中研究的车间作业计划问题即是指开环动态基于调度性能的单件车间作业计 划问题。 .车间作业计划问题的求解策略 车间作业计划问题属于典型的组合优化问题 ,虽然对该问题求解策略的研究已经有几 十年的历史了 ,提出了一大批调度 算法 ,但至今尚未形成一套系统的理论和方法。 总体来 说 ,这些算法可分为两大类 :精确算法和近似算法。 其中精确算法包括 :解析法、枚举法。 近似算法包括 :构造方法、邻域搜索方法和人工智能方法。 接下来将研究车间作业计划问 题目前的若干求解方法 : 解析法。 指针对简单小规模调度问题的解析求解方法。 枚举法。 枚举法是隐含枚举整个空间的搜索方法 ,搜索效率低 ,但求解实际问题的 计算量太大。 采用枚举法 ,表达清晰 ,易于在计算机上求解 ,但生产环境具有很多不确定 性因素 ,存在建模不确定性和求解空间太大的问题 ,造成计算困难 ,特别是不能反 映特定 调度领域的自然结构 ,所以很难应用经验知识去处理调度问题。 传统的分支定界法【】 ,它是求解组合优化问题的为数不多的有效方法之一。 构造性方法。 这类方法能够快速构造解 ,但优化质量一般较差。 主要有移动瓶颈方 法、优先规则方法【喊、插入方法等【’。 移动瓶颈方法能够取得较好的优化质量 ,但求 解过程和算法实施很复杂 ,且难以移植到其它类型的问题 ,同时相对其它方法而言比较难 理解。 优先规则调度是指系统运行时 ,根据一定的规则和策略来决定下一步操作的调度方 法。 它是动态调度的典型 ,对于实际生产系统中 ,复杂的大规模的车间 作业计划来说 ,具 有很大的优越性。 人工智能方法。 近年来 ,人工智能技术被引入生产调度领域 ,成为解决调度问题的 有效途径 ,成为一个热门课题。 人工智能方法是采用人工智能研究领域提供的方法解决各 类生产调度问题方法的总称。 该类方法利用人工智能的原理和技术进行搜索 ,譬如将优化 过程转化为智能系统动态的演化过程 ,基于系统动态的演化来实现优化。 人工智能方法主 要包括专家系统方法、神经网络方法和蚁群系统等【也】。 专家系统的方法通过收集操作人 员经验构成数据库 ,然后在线寻优。 这类方法构成简单 ,使用方便灵活 ,但经验的搜集往 往非常困难 ,很难覆盖所有方面 ,同时由于一般难以量化 ,故该方法一般作为其他方法的 辅助。 而神经网路和蚁群系统等方法优化时间性能较差 ,而优化质量严重依赖于网路参数 , 甚至可能产生非法调度。 领域搜索方法。 这类方法【从若干解出发 ,对其领域的不断搜索和当前解的替换第页 硕士学位论文 武汉科技大学 来实现优化。 其中模拟退火方法、遗传算法、禁忌搜索等方法能够取得较满意的优化质量 , 但其性能对算法参数有较强依赖性 ,且优化时间通常较长 ,而简单地将它们与优先规则相 结合的混合方法对优化质量的改善程度比较有限。 因此 ,考虑到车 间作业计划问题的复杂性和规模 ,目前最为实用而有效的算法仍然是 启发式调度规则算法。 它是动态调度的典型代表 ,它的优点是直观、简单实用 ,且花 费的求解时间较少、易于实现 ,这类算法虽然在调度解的优化性能方面欠佳 ,但对于本文 的研究对象单件订货型企业这样的动态、随机、复杂的车间作业计划问题而言 ,求解速度 快、容易得到满意甚至近优的调度解启发式调度规则仍是目前的首选算法。 启发式调度规 则也称为调度规则 ,分派规则、优先规则。 但是 ,启发式调度规则具有全局敏感性 ,利用 不同的启发式调度规则可产生不同的调度方案 ,而且规则在不 同的场合所起的作用也不相 同 ,调度系统的性能取决与启发式调度规则的选择。 因此 ,在接下来将对启发式调度规则 的性能进行分析。 .本章小结 本章给出车间作业计划问题的研究的特点分类、提出三种不同的作业调度问题模型 , 给出了车间作业计划的数学描述。 对车间作业计划问题现有的各种求解策略做了逐一的探 讨 ,并在对比分析了不同的求解算法的基础上 ,提出了启发式调度规则在解决动态车间作 业计划问题时的可行性。 第页 武汉科技大学 硕士学位论文 第三章启发式调度规则及其调度算法设计。 对于强困难的调度问 车间作业调度问题是强困难 问题百 题 ,从实际系统的复杂性、规模性和可操作性角度考虑 ,启发式调度规则仍然是目前最可 行和有效的求解方法。 但是 ,启发式调度。