【毕业学位论文】（Word原稿）不确定条件下Flow Shop调度问题研究-计算机软件与理论

分类号： 单位代码： 10422 密 级： 学 号： 06910470631 硕 士 学 位 论 文 论文题目 ： 不确定条件下 度问题研究 F 作者 专业 计算机 软件与理论 导师 杨公平 副教授 合 作 导 师 2010 年 4 月 5 日 原创性声明和关于学位 论文使用授权的说 明 原 创 性 声 明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人承担。 论文作者签名： 日 期： 关于 学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本学位论文。 (保密论文在解密后应遵守此规定 ) 论文作者签名： 导师签名： 日 期： 山 东 大 学 硕 士 学 位 论 文 I 目 录 摘 要 . I . 1 章 绪 论 . 1 题研究的背景 和意义 . 1 文工作 . 2 文组织 . 2 第 2 章 生产调度问题综述 . 3 产调度问题的描述 . 4 产调度问题的一般描述 . 4 产调度问题的相关概念 . 4 产调度问题的约束条件 . 5 产调度问题的特点 . 5 产调度问题的分类 . 7 产调度问题的研究方法 . 9 统方法 . 9 算智能方法 . 10 于知识的调度方法 . 11 第 3 章 度问题及其算法 . 13 度问题描述 . 13 度问题的求解方法 . 14 发式方法 . 14 传算法 . 16 第 4 章 基于 满意度 的 不确 定条件下 度问题 求解 方法 . 27 产调度过程中的不确定性 . 27 于 满意度 的求解 方法 . 28 糊交货期下 度问题描述 . 28 山 东 大 学 硕 士 学 位 论 文 满意度方法分析及模拟实验 . 29 第 5 章 存储时间有限型 题提前 _拖期调度 . 33 言 . 33 题描述 . 33 学模型 . 34 传算法实现 . 34 码 . 34 始群的产生 . 35 定适应度函数 . 35 择操作 . 35 叉操作 . 35 异操作 . 35 止准则 . 35 验分析 . 35 第 6 章 结束语 . 38 参考文献 . 39 致 谢 . 42 攻读学位期间发表的学术论文 . 43 山 东 大 学 硕 士 学 位 论 文 F in . I in . . 1 1.1 an of . 1 1.2 . 2 . 2 . 3 of . 4 he . 4 . . 5 of . 5 of . 7 of . . 9 . 10 on . 11 . 13 of . 13 of . 14 . 14 . 16 . 27 in . 27 he of . 28 he of . 29 东 大 学 硕 士 学 位 论 文 IV . 33 . 33 . 33 . 34 . 34 . 34 . 35 . 35 . 35 . 35 . 35 . 35 5.3 . 35 . 38 . 39 . 42 of . 43 山 东 大 学 硕 士 学 位 论 文 I 摘 要 生产作业调度 问题 是研究在有限的资源条件下，如何分配资源 以满足某个或某些特定的生产指标 ， 并使得生产企业获得最大的经济利益和社会效益。 生产调度在企业生产管理中占据至关重要的战略位置。如何分配现有资源以满足特定的生产目标，从而使企业在日趋激烈的市场竞争中处于领先地位，是企业管理的重点内容。 因此，生产作业 调度 问题 一直是许多企业如制造业 的研究 热点 。 对生产作业调度问题的研究具有重要的理论意义和现实意义。 本文对生产作业调度问题进行了系统阐述，并对其中的 度问题重点研究。由于 实际生产过程中存在 大量的不确定因素 ，使 得由各种确定性模型和方法得到的优化调度性能指标降低甚至不再可行 ， 因此 本文 在处理生产调度问题 的时候，将 生产过程中存在的不确定因素 作为一项必不可少的条件。论文介绍了生产调度问题中的不确定因素及其分类，对模糊交货期下的 度问题进行阐述。 生产作业调度问题的研究 方法 历经 由简单到复杂的过程。 这些方法从不同程度上表述了 具体生产环境中的复杂的、多目标、动态的调度问题的一种抽象和简化 。 而评估一个调度算法的主要标准 是其优化效果的满意度。 调度优化算法传统上主要集中于数学规划、简单的规则等方 法。近几十年来，关于遗传算法、模拟退火算法、神经网络算法以及模糊逻辑等方法的研究十分活跃，已成为生产作业调度问题研究的热点之一。作为生产调度领域的重要研究方法， 遗传算法通过模拟达尔文“优胜劣汰、适者生存”的激励原理以及模拟孟德尔遗传变异理论在迭代过程中的作用，实现了随机优化与有效搜索 。 本文 重点研究 遗传算法的基本思想和流程及其参数设计，并将其应用在 度问题的算法研究中。 论文以不确定条件下生产调度问题算法研究为目的，针对 度问题进行研究，研究的一个侧重点是 中间 存储时间有限型 提前 _拖期调度问题。随着 流程工业中 准时制的发展，企业所追求的目标是尽可能极大化用户的满意水平，使 企业所承受的 提前 _拖期惩罚 达到最低目标 。 论文给出一种解决 另外由于产品在加工过程中存在不稳定性，山 东 大 学 硕 士 学 位 论 文 以产品在两个生产单元之间的储罐中的存储时间只能为一个有限值。本文 研究了 在处理时间不确定 的 条件下，带不同交货期窗口的存储时间有限型 采用三角模糊数描述处理时间的不确定性 ， 使用自然数编码方法 ， 随机产生初始种群， 以惩罚数的期望值 的倒数作 为 适 应度 目标函数值， 再 利用遗传算法 中的选择、交叉和变异算子 进行求解 。 根据实验结果证明本文所采用的研究方法是有效的 。 关键词： 度； 不确定条件 ；满意度； 提前 _拖期调度 山 东 大 学 硕 士 学 位 论 文 is of to to or to of a of in in It is in of to to in to in in as of of it to of is so in no so in as an is of in of a to of in to a is of of on so In of of As an 东 大 学 硕 士 学 位 论 文 IV by of of in s it a in of is in it is to to on it to of to s of be as as it a of to s of in it be in a of It of It of of as of of to of is 东 大 学 硕 士 学 位 论 文 1 第 1 章 绪 论 题研究的背景和意义 流程工业在我国工业生产中具有非常重要的地位 ,如何增强企业的竞争力、提高企业的经济效益和社会效益是企业面临的首要问题。 度问题研究多个作业在处理设备上以相同路径进行处理，如何安排作业序列来获得最 优生产目标 的问题。人们对 题在确定条件下的调度算法进行了大量研究20，然而，这些算法很难应用于实际的生产过程中。因为在实际生产中存在许多不确定因素，往往导致生产调度方案无法按预定目标正常执行。目前，对不确定因素主要采用模糊数学方法进 行描述，关于模糊处理时间的研究文献有很多，例如 212223。 流水车间调度问题研究工件在一系列生产设备上以相同顺序进行加工的问题。近来人们对流水车间问题研究给予了很大关注，以提高工业企业的生产效率和经济效益。在实际流水车间生产过程中，工件通常受到释放期限和收工期限的约束，即受工件被允许可以开始生产的期限和必须完成生产过程的期限的限制。比如，一个工件必须在所需原料储备完毕后才可以开始生产，并且收工期限必须保证产品能在用户要求的时间内送达。只有同时满足释放期限和收工期限的工件的加工序列才是可行的。传 统的调度算法只处理精确数据，当释放期限和收工期限的约束条件发生细微变化时可能会遗漏可行解。实际情况是工件的释放期限和收工期限可以在一定时间段内浮动，即放宽对两者的约束，这样可以得到满足松弛释放期限和收工期限的具有最大满意度的工件加工序列。 现代准时制生产（ 21 世纪企业的先进生产模式，其目的是以最低成本达到客户最大的满意效果。 求产品按时加工并且交货准时。生产企业只要偏离了客户需求的交货期都要受到惩罚。所以企业要尽量避免提前完工或拖期完工。对提前 _拖期调度问题的研究要综合考虑 实际生产过程中的不确定因素 ，还要加入必要的约束条件，即中间存储时间是有限的。遗传算法通过对编码后的字符进行搜索，搜索过程从一组可行解开始迭代到另一组解， 可操作性和简单性决定了其能够有效解决中间存储时间有限的 前 _山 东 大 学 硕 士 学 位 论 文 2 拖期调度问题。 文工作 本文详细阐述了生产调度问题中的 要工作为： 点是 产调度问题。 度问题，以模糊释放期限和模 糊收工期限来 使得工件的加工过程更加符合实际，并通过满意度计算公式可以获得最佳工件序列。 题提前 _拖期调度，利用遗传算法给出其求解过程，并给出实验分析。 文 组织 本文的研究内容共分为五章： 第一章绪论，简要介绍本课题研究的背景和意义、本文工作和论文的组织方式。 第 二 章 对 生产调度问题 进行 综述，并介绍了生产调度的特点、分类和研究方法。 第三章给出了 着重介绍遗传 算法； 第四章 阐述了模糊 据 其问题描述及相关模糊数，给出了模糊释放期限和模糊收工期限以及满意度计算方法，最后进行了模拟计算 ； 第五章研究了存储时间有限型 题提前 _拖期调度，给出了遗传算法解决该问题的步骤，并进行了实例仿真。 第 六 章对本文内容做了总结，并对下一步的工作给予展望。 山 东 大 学 硕 士 学 位 论 文 3 第 2 章 生产调度问题综述 随着科学技术的飞速发展、市场竞争的日益激烈、人们消费观念的日趋个性化、生产规模的不断扩大，以及生产过程的日益复杂化，促使生产企业必须采取更加先进合理的管理模式和生产方法，来提高自己的综合实力。 只有将简单的、局部的控制 和 凭经验的管理方式逐步转变为充分利用现有资源优势、高效科学的创造效益才能解决企业的经营管理者们的问题。 也就是说，企业要在竞争中取得优势，不仅要靠工艺水平的提高和先进设备的研发、引进，更要靠先进的生产和经营手段 10。 生产作业调度是研究在有限的资源条件下，如何分配资源 以满足某个或某些特定的生产指标 ,并使得生产企业获得最大的经济利益和社会效益。生产调度是流程企业生产管理的重要组成部分。 生产调度是 和 的一个重要组成部分，是生产管理的核心和关键技术。每当一组通用的资源，比如劳力、材料、设备，必须配 合使 用 并 在统一时间段内制成不同的产品时，就会发生调度问题。系统、全面、合理的生产调度方法不仅有助于提高企业的综合自动化水平，而且可以为企业部门带来显著的经济效益。国外的实施状况表明，单纯提高生产装置的控制水平，寻求局部最优的投入产出比，远远低于提高整体管理水平的投入产出比，因此，生产调度的改进是提高企业综合收益的最有利手段 11。 在介绍调度问题之 前，先来阐明什么是排序问题。排序问题是企业生产以及国防、交通运输和各服务行业中普遍遇到的问题；一般的，凡是需要完成多个不同项目就产生了某一类排序问题 1。排序问题有时会非常复杂，比如同一台设备上要加工的零件可能有多个，一个零件可能有多道工序要到不同的设备上加工，零件的加工工艺也可能不相同。不同任务在不同的机器上不同的加工顺序得出的结果可能差别很大，怎样安排这种顺序，以期得到最优的结果，就是调度问题。 调度问题通常是指对生产过程的作业计划，譬如工件在机器上的加工顺序、生产批量的划分等 2。调度问题的“设备 ”可以指工厂中的机床、维修工人、轮船要停靠的码头等，即表示服务者；调度中的“任务”则是等待加工的零件、待山 东 大 学 硕 士 学 位 论 文 4 维修的机器、将要停靠码头的轮船等，表示服务对象。一般情况下，“设备”和“任务”都有多个。调度问题及时要确定服务者对服务对象的服务顺序和时间，使目标函数取得最优解。 如图 1示，车间调度就是根据加工对象的加工需求，运用不同的调度决策规则，规划系统中的加工事件，并根据系统动态仿真运行的结果或者优化结果形成最佳的生产加工顺序，同时实现设备集和任务集的合理最优化结合 4。 图 2产调度问题的定义 下面将介绍生产调度问题的描述、生产调度问题的分类及其研究方法。 产调度问题的描述 本 小节 给出生产调度问题的一般描述，其中的符号作为本文研究问题的统一符号。给出的相关概念以使问题的阐述更加明 晰 ； 明确 生产调度问题中的约束条件 是理解本文研究问题的重要条件。 产调度问题的一般描述 生产调度问题一般可以描述为： n 个工件 ( ,1 在 m 台机器( ,1上加工，工件用相应的加工时间 (个调度就是在一定时间内分配各工件在机器上的加工时间。 产调度问题的相关概念 加工任务 ，是一组等待调度