现场管理_基于非合作博弈硫化车间生产研究

基于非合作博弈的硫化车间 多目标生产调度研究 学位论文完成日期： 指导教师签字： 答辩委员会成员签字： 独创性声明独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人已用于其他学位 申请的论文或成果。与我一同工作的同志对本研究所做的任何贡献均已在论文 中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 日期： 年 月 日 关于论文使用授权的说明关于论文使用授权的说明 本学位论文作者完全了解青岛科技大学有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅 和借阅。本人授权学校可以将学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人离校 后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍 然为青岛科技大学。(保密的学位论文在解密后适用本授权书) 本学位论文属于： 保密 ，在 年解密后适用于本声明。 不保密。 (请在以上方框内打“” ) 本人签名： 日期： 年 月 日 导师签名： 日期： 年 月 日 I 基于非合作博弈的硫化车间多目标生产调度研究 摘 要 当前我国轮胎企业面临着严峻的挑战。轮胎硫化车间硫化过程普遍存在规 模大、约束复杂、不确定性强、多目标和生产管理模式多样等特点，且传统调 度研究的优化目标是由全体工件的同构目标加权组成的全局目标。对于可能存 在的工件加工要求之间的差异，则通过权值在全局目标中简单地进行协调。显 然，这种方法没有充分重视不同工件具有的独立要求，因此也很难准确表达不 同类型的工件具有不同加工要求的意愿。针对多目标生产调度的需求现状，结 合博弈理论，发挥其优点，建立一种新的解决硫化车间制造多目标生产调度的 方法，有助于推动生产调度理论的发展，改善其性能，拓宽其应用领域，具有 重要的理论意义和积极的实际意义，应用前景广阔。 传统调度研究的关注于全局目标，忽视了客户目标，无法满足这类复杂制 造过程生产调度的需要。为了适应新的要求，本文在已有研究的基础上，应用 非合作博弈理论研究硫化车间的调度问题，分别建立基于客户和生产方驱动的 非合作博弈模型，并应用相应的算法对模型进行求解，总结起来本文主要做了 一下几方面的工作： 通过查阅大量的文献总结了生产调度的分类、特点，以及目前生产调度存 在的问题，阐述了已有的研究的背景及意义。 回顾了博弈论的要点，剖析了博弈论的理论精髓，指出博弈论在生产调度 中的应用的关键在于建模和求解。阐述了本文的研究关注点、可行性以及博弈 论在生产调度中的研究思路。 以客户利益为核心，建立客户驱动的非合作博弈的硫化车间多目标调度模 型，将制造任务、硫化机映射到博弈模型中，研究使用遗传算法进行非合作博 弈模型的 Nash 均衡点求解，通过求解结果验证模型的正确性。 从生产方目标出发综合考虑全局目标，分析硫化车间的特点，建立基于生 产方驱动的非合作博弈硫化车间多人多目标模型，给出纳什均衡调度的定义， 分析纳什均衡点的存在性。 针对生产方驱动的非合作博弈模型，以硫化车间生产调度为背景，将借鉴 传统调度算法，设计了一种基于价格调节机制的算法，来求解松弛的纳什均衡 调度，再将纳什调度转化为原纳什均衡调度的解，最后对算法进行仿真，通过 仿真结果验证该算法的合理性。 II 关键词关键词：生产调度， 非合作博弈，纳什均衡，遗传算法，硫化车间 I STUDY ON VULCANIZATION WORKSHOP PRODUCTION SCHEDULING BASED ON NON-COOPERATIVE GAME ABSTRACT Tire companies are facing severe challenges in China, the vulcanization process of the tire widespread large-scale, complex constraints, uncertainty, multi-objectives and the production management mode is various. The traditional scheduling optimization objective of the research is global goals. The differences that may exist between the jobs requirements and the requirements are simply coordinated by weighted in the global objectives. Obviously, this approach does not pay full attention to the independent requirements of different job, it is difficult to accurately express the different job with different types of processing , for the demand of multi-objective production scheduling, this research takes advantage of game theory to establish a new manufacturing production scheduling，that the establishment of multi-objective method to solve the vulcanization workshop to help promote the development of the theory of production scheduling, improve their performance and broaden its applications. The research has important theoretical and practical significance, broad application prospects. Traditional scheduling research focused on the global goal, ignoring the clients objectives, unable to meet the needs of such complex manufacturing process, in order to adapt to the new requirements, the paper takes advantage of non-cooperative game theory to study the vulcanization workshop scheduling problem, to create two models based on the customers and production-driven, and should use the appropriate algorithm to solve the model. Summed up this paper, the work lies in five aspects as follow: Review the main points of game theory and analyze its essence. Point out its IV applications in production scheduling in mathematical modeling and problem solving. Describe the focus and feasibility of this paper, including research ideas in production scheduling based on game theory. Build the multi-objective production scheduling model which is based on non- cooperative game theory and driven by the customersinterests,and map task manufacturing and vulcanizing machines into the game theory model，according to the core of the production namely the interests of customers.Meanwhile, study using the genetic algorithm to find out the Nash equilibrium point in the model of non- cooperative game theory, and verify the correctness of the model through the results. Set up the multi-objective non-cooperative game theory model promoted by the producers, starting from the targets of the producer, considering the global objectives, analyzing the characteristics of vulcanization workshop.Definite the Nash equilibrium scheduling, and analyze the existence of Nash equilibrium. The non-cooperative game theory model, pushed by the producer, taking the vulcanization workshop as the research background, will draw lessons from the traditional scheduling algorithms to design a Nash Equilibrium scheduling algorithm based on the price adjustment mechanism.By this sort of algorithms the problems of the slack scheduling of Nash equilibrium can be solved, and the answers will be converted to the solutions of the original Nash equilibrium scheduling. Finally, after simulation, the rationality of this algorithm will be verified. KEY WORDS: Vulcanization workshop ,Production scheduling，Non-cooperative game, Nash equilibrium, Genetic algorithm I 目 录 前言 1 第一章绪论 3 1.1 生产调度的问题概述.3 1.1.1 生产调度的描述3 1.1.2 生产调度的特点.4 1.1.3 生产调度的问题分类5 1.2 生产调度中研究方法.5 1.3 本课题研究的背景和意义.7 1.4 本文所做的工作与内容安排.9 1.4.1 本文主要的研究内容.9 1.4.2 本文的章节安排9 第二章 博弈论在生产调度中应用 11 2.1 引言.11 2.2 博弈论.11 2.1.1 博弈论概述.11 2.1.2 博弈论的分类.12 2.3 博弈论在生产调度中研究的现状.12 2.4 博弈论在硫化车间生产调度研究中的市场前景.15 2.5 本文的研究思路.15 第三章 客户驱动的硫化车间非合作博弈研究 16 3.1 引言.16 3.2 背景及建模思路16 3.2.1 研究背景16 3.2.2 硫化车间生产的特点.16 3.2.3 建模思路.18 3.3 客户驱动的硫化车间调度任务描述.19 3.3.1 客户驱动的硫化车间调度数学模型的描述.19 3.3.2 非合作博弈模型的纳什均衡21 3.4 结论22 第四章 客户驱动的硫化车间非合作博弈模型的求解 23 4.1 引言23 4.2 遗传算法概述23 4.2.1 遗传算法原理23 4.2.2 遗传算法的基本思想24 VI 4.2.3 遗传算法的特点24 4.3 自适应遗传算法设计26 4.3.1 算法流程26 4.3.2 编码设计.27 4.3.3 设计适应值函数.27 4.3.4 自适应遗传算法的进化27 4.4 实验仿真29 4.4.1 实验初始化条件和参数29 4.4.2 结果与分析30 4.5 总结31 第五章.生产方驱动的硫化车间非合作博弈研究 32 5.1 引言32 5.2 基于非合作博弈的硫化车间调度问题描述.32 5.3 生产方驱动的硫化车间非合作博弈建模.33 5.3 纳什均衡调度定义.36 5.4 纳什均衡的调度解的存在性.36 5.5 客户评价的性能指标.37 5.6 总结.38 第六章 生产方驱动的硫化车间模型求解 39 6.1 引言39 6.2 传统相关算法39 6.3 价格机制算法的设计.40 6.3.1 松弛模型及其纳什均衡解的定义.40 6.3.2 价格调整机制算法.41 6.3.3 价格调节机制算法的设计.43 6.4 价格调整机制算法仿真45 6.4.1 仿真测试平台及实验参数45 6.4.2 调度结果46 6.4.3 本节小结.51 6.5 总结51 总结及展望 .52 参考文献 .53 致 谢 57 攻读硕士期间发表的论文 .59 青岛科技大学研究生学位论文 1 前言 改革开放以来，随着经济的发展，人民生活水平的提高，汽车已经进入越 来越多的家庭，伴随着汽车业的蓬勃发展，轮胎制造业也焕发了行业的青春。 根据行业统计，2011年，我国汽车轮胎外胎总产量为8.32亿条，2012年全年产 量为8.92亿条，同比增长4.25%。巨大的产量为轮胎制造企业带来了巨大的收益， 同时也给企业生产带来了巨大的压力。并不断提高自身的竞争力，来参与国际 化的竞争。十一五期间, 我国轮胎工业实现了持续快速增长,虽然遇到了全球金 融危机, 但在国家大力实施拉动内需政策下, 轮胎产销基本得到恢复1。我国 目前轮胎的总产量已跃居全球首位，占全球总产量的1/4，到目前为止我国已经 能生成2000多种规格的轮胎，涵盖子午线和斜交型载重、轿车、农业、工程机 械和工业车辆等六大类轮胎。 当前我国轮胎企业面临着严峻的挑战，一方面在国际贸易中，出现贸易壁 垒，贸易保护主义抬头，经常出现打压我国轮胎出口的问题，近几年, 我国轮 胎出口贸易遇到不小的挫折，轮胎出口先后遇到美国、巴西、印度、秘鲁、土 耳其等国的反倾销制裁。另一方面我国很多轮胎企业中存在原料等存在严重的 浪费现象，而且生产效率低下，很难保证产品在规定的交货期内交货，严重影 响我国轮胎企业在国内外客户中的企业信誉，究其原因在于很多轮胎生产企业 的生产计划调度仍然依赖人工完成，信息靠人工传递，规范性差，报表效率低， 缺乏正确的、科学的、可行的生产调度方案，使得论坛生产车间设备使用不均 衡现象普遍存在，不科学的生产调度严重阻碍了轮胎企业生产效率的提高。在 这种情况下，设计良好的科学的轮胎生产调度计划，对于轮胎企业的生产效率 的提高有着极为重要的意义。 近年来随着计算机计技术的迅猛发展，计算机在提升传统产业、发展新兴 产业上发挥了重要作用，成为促进传统产业技术进步和支撑新兴产业发展的重 要工具2。目前计算机已经广泛应用于轮胎生产企业，现代化的轮胎生产不仅 要求计算机对整个的任务过程，生产过程进行全程控制和优化，而且要在获取 生产全部过程尽可能多的信息基础上，对整个的生产进行全方位的控制调度， 和对全部任务的综合管理。所谓的生产管理是指计划、调度、和控制，这三个 方面是生产管理的三个基本过程。优化生产计划和生产调度成为增强企业的竞 争力、提高企业的经济效益和社会效益的关键因素3。轮胎企业的生产调度， 不仅是轮胎生产企业生产运行的指挥调度中心，也是该类企业生产管理的核心 组成部分之一，同时也是其获得经济效益的重要来源4。 基于非合作博弈的硫化车间多目标生产调度研究 2 目前，我国虽然已经步入橡胶工业大国，但是还算不上橡胶工业强国，虽 然已经具有了向橡胶工业强国迈进的雄厚基础，但我国的橡胶工业面临的依然 是机遇与挑战并存5，力争通过大调整，大转变，大重组使我国在“十三五期 间”步入橡胶工业强国的行列。 轮胎制造行业是一个生产规模较大，资源和劳动力密集的行业，良好的生 产计划的制定对企业的生产过程和实际收益具有重大的意义。我国轮胎生产行 业普遍面临生产计划主要靠人工制定，生产效率不高的困境，因此提高企业调 度计划制定水平是我国制造业亟待解决的问题。 研究生产调度对我国橡胶生产企业有着重要的意义，能够加快我国橡胶工 业迈向橡胶工业强国的步伐，在橡胶企业中生产调度是计算机集尘制造系统的 组成部分，连接着管理层和控制层6,在橡胶企业的生产管理中起着举足轻重的 作用，现代轮胎制造业需要系统的、可行的、高效的生产调度方法。研究高效 生产调度的方法，对于缩短轮胎的生产周期，确保轮胎按时交货，降低轮胎的 生产成本有着极为重要的意义，特别是在当前经济全球化竞争激烈的市场环境 下，对提高轮胎生产企业的核心竞争力有着重要的实用价值。同时有助于调高 轮胎生产企业的全面高效的自动化水平，并为轮胎生产企业带来可观的经济效 益。 轮胎在硫化车间硫化是轮胎生产环节中最重要的一个工序，在这个环节中， 硫化一条轮胎需要花费很长时间，合理的调度就愈显重要。单纯依靠人工制定 调度计划，很难满足各种要求，如准时货期、花费成本最低等。利用计算机的 强大的运算能力通过设计分析生产环境的特点，建立数学模型，将订单信息输 入，通过大量的计算，能够得出相对较好的调度结果。利用这种调度结果进行 生产，不仅能够提高企业生产效率和收益，而且可以节能减排，降低污染和浪 费。因此投入大量精力进行此方面的研究，对轮胎企业和国家都具有很现实的 意义。 青岛科技大学研究生学位论文 3 第一章绪论 1.1 生产调度的问题概述 1.1.1 生产调度的描述 生产调度通常是生产过程的作业计划， 例如某机器上工件的加工顺序，以 及要加工点的工件如何划分批次。从本质上分，调度问题可以为开环调度和闭 环调度。所谓开环调度是指研究工件加工的顺序，所有的客户订购的产品，在 机器上排序生产，不考虑其他的因素，闭环调度是指，除了考虑工件的加工顺 序之外，还要考虑产品批次的大小等。显然闭环调度的复杂性远远大于开环调 度的复杂性，目前对闭环调度的处理通常使用近似方法，首先确定批量大小， 然后再确定加工顺序。 生产调度的问题基本上可以概述为：对于某一项可分解生产任务，在特定的 约束条件下，分派生产所需要的资源，安排子任务的生产时间，并对子任务进 行排序，目标是产品的最短的制造时间，或者最低产品成本。其中生产所需要 的资源主要包括：人力资源、资金、生产原料、生产设备等，评价目标好的的 指标一般有：产品的生产周期短，总成本低和生产设备利用率低等。 生产调度的形式可以描述为：n 个工件，m 台机器加工，每一个工件需要在 m 台中的一台或者多台加工，假设第 i 个工件，在第 j 台机上加工ni 1 加工时间为 Pij，加工操作位 Oij没一个工件的准备时间为 Rij，工件的mj 1 交货期为 Dij，交货期是指必须在规定的时间内交货，每一个工件有相应的工艺 流程，工件按照工艺的约束在机器上按顺序加工。所谓调度可以看做是，在一 定的约束条件下工件如何分配到机器上加工，本质上来说调度就是将工件在机 器上排序，其要符合以下两点要求： （1）符合产品工艺上的约束（可行调度） ； （2）对应的执行的目标调度是最优的7； 生产调度问题是一类复杂的问题，研究难度非常大，给学者的研究带来了 不小的困难，当前生产调度的研究还有很多问题没有解决，很多实际的生产调 度还停留在理论层次，大部分生产调度的算法研究只做了一些简单的假设，过 于简单，与实际的生产差距较大。目前很多企业的调度还是靠人工完成，耗费 了大量的人力物力，不利于企业成本的控制。 基于非合作博弈的硫化车间多目标生产调度研究 4 1.1.2 生产调度的特点 生产调度存在着一下的共同特点； （1） 复杂性，由于产品种类繁多，各种产品的生产工艺多种多样，生产环 境的条件复杂多变，生产调度问题的复杂程度会随着问题的规模的增 加成指数增长，早已被证明为 NP 完全问题。 （2） 约束性，约束条件主要是指产品往往有自己的工艺流程，设备，需要 的原料，产品的原料，产品的库存，产品的交货期等等。 （3） 不确定性，产品的生产设备故障会偶尔发生，存在不确定性，产品的 物料运输的不确定性等，使得调度问题具有不确定性 （4） 多目标性，生产调度优化的目标很多，比如产品的利润，产品的生产 周期，产品的交货期等，这些目标往往存在冲突，使得同时优化所有 的目标达到最优不太可能实现。 生产调度，是生产过程一个关键的模块（如图 1-1） ，是整个先进制造系统 发展的核心，高效的调度方法是实现提高生产效益的关键方法，能够增强企业 的核心竞争力，目前生产调度的研究主要分为两个方面，一方面是对调度的建 模，一方面是调度算法的设计，是个一个交叉性的研究领域，涉及非常多的学 科，如数学，运筹学，计算机，控制工程，工业工程等等。其中建模研究的是 调度的模型，调度的规则，调度的目标函数等等，算法主要研究的是指算法的 设计，收敛性，优化等问题。 生产过程 决策信息 管理信息 调度信息 工况信息 测量信息 经营决策 管理系统 生产调度 监控系统 控制系统 决策层 管理层 调度层 监控层 控制层 信息 控制 目标 利润最大 生产经营 经营管理 优化调度 先进控制 操作优化 故障诊断 复杂控制 常规控制 图 1-1 调度在生产过程中的作用 Figure 1-1 The role of scheduling in the production process 青岛科技大学研究生学位论文 5 1.1.3 生产调度的问题分类 生产调度从不同的角度可以有多种分类方式，表 1-1 给出了生产调度常见 的分类方式。 表 1-1 调度分类表 Table 1-1 scheduling classification 车间调度类型 需求产生的来源开环车间，闭环车间 加工系统复杂度单机问题，并行多机问题，flow shop，job shop 加工性能指标基于调度费用，基于调度性能 生产环境特点确定性调度，随机性调度 作业加工特点静态实时调度，动态实时调度 工件加路线致性有序加工，无序加工 生产调度还可以依据不同的生产设备环境进行分类，可以分为以下几类： （1） 作业车间调度：作业车间调度是指要加工的产品有多道工序，每道工序 由不同的设备完成，每个产品有不同的加工路径。作业车间调度是调度 最基本的一种类型； （2） 流水车间调度：流水车间调度是指要加工的产品有多道工序，每道工序 由不同的设备完成，每个产品不同的加工路径相同。生产线像流水一样 产品从一端流入，从另一端流出； （3） 开放式车间调度：开放式车间调度是指要加工的产品有多道工序，每道 工序由不同的设备完成，每个产品内部的工序是任意的，没有次序的限 制，工序可以任意排列。 生产过程可以分为连续，间歇，离散的制造过程，分类的依据在于生产的 产品的性质。 连续的生产过程是指，从原料到产品要经过某些专用设备，设备连续工作， 产品的输出是连续的。 间歇的生产过成是指每个产品经过多个生产的工序，每个工序之间是离散 的，而工序之间是连续的。 离散的制造过程是说，产品分批次加工，每个工件都有自己的特性，例如 机械加工是典型的离散加工过程。 相应的生产调度也可以分为离散的生产调度，间歇的生产调度等。 1.2 生产调度中研究方法 生产调度的研究最早在 1954 年，Johnson 研究了两台机器的调度问题，之 基于非合作博弈的硫化车间多目标生产调度研究 6 后很多学者纷纷加入了研究的行列，经过 50 多年的研究，车间调度领域取得了 丰硕的成果，这一时期产生了很多重要的调度方法8。调度的优化实质上就是 调度模型的求解，目前调度的求解分为精确的求解，和近似的求解。精确求解 的比较典型的方法有，解析法和枚举法，近似的求解主要有启发式方法，构造 方法等一下是几种常见的方法： （1）枚举方法 分支界定法，是枚举法中最典型的一类方法，其思想是将整个问题划分， 分解成小的子问题，然后对子问题进行分析，如果子问题能够在域内求解，再 将子问题分支。此法实质上求解相应子问题域的相对应问题的松弛问题。 （2）邻域搜索算法 邻域搜索算法是通过从邻域内不断寻找解来替换当前域内的解一种方法， 这种算法的缺点在于运行时间长，但往往解的可靠性高。 （3）启发式方法 启发式方法具有很多的优点，在生产中应用广泛，虽然启发式具有计算复 杂度低，简单，容易实现的特点，但是启发式方法不具备全局性的特点。许多 年来，学者们进行了广泛的研究，并不断创造出新的调度规则，主要分为简单 规则、复合规则、启发式规则三类 9。由于启发式调度规则简单，易于实现， 计算复杂度低等原因，因此在生产中得到了广泛的应用，但启发式规则主要缺 点是求出的解不一定满足所有的约束条件, 并且无法确定解的优劣, 常需要专 家的介入10 。 （4）运筹学的方法 运筹学方法能从理论上求取最优解，其思想是将复杂的生产调度问题简化 成为数学规划模型，数学模型的求解通过分支界定法或动态规划法进行的11。 此类方法主要适合于处理较小规模的调度问题。但由于大部分生产调度问题非 常复杂，究其本质，这是数学中一个规模很大的组合优化问题。并且其计算量 会由于问题规模的增大而出现爆炸性增长，是一个典型的 NP 完全问题。另外， 运筹学方法存在着很大的局限性，这种方法往往加入了与实际情况不符的假设， 容易造成所研究的理论与真实的使用之间存在很大的差距。 （5）拉格朗日松弛法 拉格朗日松弛法是一种较好的解决调度问题的方法，因其能为复杂的调度 问题提供好的次优解，并且有对给出的次优解进行定量评估的能力，所以成为 解决调度问题的一种非常广泛方法 12。拉格朗日松弛法仍然存在着一定的缺点， 例如与分枝定界法相比，更加耗时。拉格朗日松弛法得到的是原问题的一个界, 不能保证获得原问题的最优解, 甚至不能保证获得可行解。 青岛科技大学研究生学位论文 7 1.3 本课题研究的背景和意义 当今轮胎企业之间的竞争越来越激烈，产品的寿命周期变得越来越短暂， 客户的需求也越来越多，这使得调度成为日益复杂的工作。面对着这些变化和 随时可能发生的生产加工环境的改变，生产经营决策者必须多方面的考虑问题， 解决诸多相互联系但又相互矛盾的问题。 轮胎制造过程普遍存在规模大、约束复杂、不确定性强、多目标和生产管理 模式多样等特点，传统调度方法无法满足这类复杂制造过程生产调度的需要， 导致现在的企业人工调度的现象还普遍存在采用手工方式进行的现象，企业所 制定的生产调度计划，基本上没有考虑订单、生产设备、原材料、工艺等很多 的与调度有关的因素。企业没有能力处理生产过程中的突发事件，对此也很难 做出快速的、准确的响应，企业很难通过合理有效的生产调度对产品的生产作 出安排，来降低产品的生产成本。以上问题直接影响到企业的信誉、企业生产 效率和生产产品成本。为了解决生产车间上述的问题，很多专家研究机构和企 业对多目标生产调度问题正在进行大量的研究。 随着中国改革开放的不断深化，中国经济正在蓬勃发展，良好的市场环境 和巨大的市场，促使汽车工业的高速发展，世界各国的轮胎生产企业纷纷在中 国投资建厂，经济的全球化加速了，国外轮胎生产企业向中国转移的步伐加快， 目前全球前十位的轮胎生产企业，已经有绝大部分在中国安家落户，原有的国 有重点轮胎生产企业很多已经被并购，这对我国的轮胎工业的发展将产生全局 性的，深远的影响。 当前，现代轮胎制造企业业正处于迅猛发展阶段，全球化市场环境下的竞 争日趋激烈，快速面向市场推出高质量、低成本的产品已成为企业赢得竞争的 关键点。轮胎生产是离散与连续的混合生产方式，是带有若干缓冲区的区域性 功能生产系统，工艺、物流、设备属性复杂，管理与控制方式变化很大，给企 业计划调度、质量、成本控制造成很多困难。对轮胎制造企业来说，有按时交 货、库存最少、加工时间最短、各种半制品最少剩余、机器占用最少等众多生 产目标，对提交订单的企业来说，包括按时交货、加工成本最低等目标。因此 轮胎制造过程调度是具有多目标的生产调度。传统的生产和管理模式很难满足 这一要求企业在考虑自身生产要求的同时，还须满足客户的需求。由于制造任 务一般来源于不同客户，每个客户都希望自己提交的制造任务加工完成时间最 短，生产成本尽可能低，这就导致了客户间的竞争13-14。 显然，传统生产调度方法难以满足以上要求，因此需要寻求一种新的生产 调度策略和模型，以达到制造商与客户之间的利益均衡。一般情况下对于多目 基于非合作博弈的硫化车间多目标生产调度研究 8 标生产调度研究是通过是通过对全体工件的优化目标加权组成的生产调度的全 局目标，然后利经典的统数学方法或人工智能算法求解，对多目标生产调度问 题，一般是将其中一部分目标作为限制条件。这些方法在调度中对满足客户的 个体要求重视不足忽略了客户需求，因此对于客户的需求不具有适应市场变化 的能力。 20世纪中期提出并发展起来的博弈理论主要用于解决有约束、多人多目标 且目标函数相互矛盾的决策问题15，近年来博弈理论在控制、规划、计算机等 领域也得到很多应用，而调度问题本质上描述的是具有约束和优化目标的，对 于有限资源竞争和分配的问题，其中蕴藏着多个个体之间的冲突，因此博弈理 论有可能成为描述调度问题的一种很好的工具，进化计算近年来已成为信息科 学、人工智能与计算机科学的研究热点，是人们解决棘手问题的有力工具16。 针对多目标生产调度的需求现状，结合博弈理论和进化计算理论，发挥其 各自的优点，建立一种新的解决轮胎制造多目标生产调度的方法，有助于推动 生产调度理论的发展，改善其性能，拓宽其应用领域，具有重要的理论意义和 积极的实际意义，应用前景广阔。 调度问题实质上是描述典型的有约束和优化指标要求的稀缺资源分配和竞 争问题。资源数量的限制，从而导致每个个体在分配资源时获得的利益可能不 一直，因此调度问题中也不可或缺的存在个体之间的利益分配的冲突，从这一 角度讲，调度问题跟规划，经济问题非常类似，综合上文的分析，博弈论有可 能成为解决调度问题一种很好的理论工具，博弈论当前已经应用于很多调度场 合如：多cpu，空运，生产调度，生产调度作为其中具有代表性的一类问题，是 本论文的主要讨论对象。 调度是指在各种约束条件一定的情况下，通过对给定资源的合理利用，来 完成指定的任务，同时满足各种性能指标，如生产完成时间或生产成本的最优 化。生产调度计划是整个先进制造系统的管理技术中心，生产调度问题非常复 杂，究其本质，这是数学中一个规模很大的组合优化问题。并且其计算量会由 于问题规模的增大而出现爆炸性增长，是一个典型的NP完全问题。调度问题的 复杂性和难处理性，一直备受制造企业以及国内外广大学者的重视。市场化条 件下的现代制造企业竞争的压力越来越大。企业为了抢占市场，必须重视客户 的需求，把客户的需求放到首要的位置。 传统调度研究的优化目 标是由全体工件的同构目标加权组成的全局目标。 对于可能存在的工件加工要求之间的差异，则通过权值在全局目标中的比重， 来简单地进行协调。很明显，上述方法的缺点在于其并不关注于工件的独立目 标要求，很难准确表达不同工件具有不同类型的加工意愿。所以在调度中对对 青岛科技大学研究生学位论文 9 客户的个体要求重视程度不够，在市场中缺乏对客户的需求多要化的处理能力。 通过以上讨论，可考虑采用博弈理论中的思想来描述和处理此类的问题，建立 基于工件独立性能指标的博弈模型，通过工件的之间的合作或非合作的行为策 略形成对应的概念来描述此类问题的可行性调度。已有文献进行了这方面工作 的一些尝试，已有的研究成果表明，采用博弈方法解决多目标调度问题具有较 好的可行性。 1.4 本文所做的工作与内容安排 1.4.1 本文主要的研究内容 本文在已有研究的基础上，应用非合作博弈理论研究硫化车间的调度问题， 分别建立基于客户和生产方驱动的非合作博弈模型，并应用相应的算法对模型 进行求解，总结起来本文做了以下五个方面的工作： 通过查阅大量的文献总结了生产调度的分类、特点以及目前生产调度存在 的问题，阐述了本来的研究的背景及意义。 回顾了博弈论的要点，剖析了博弈论的理论精髓，指出博弈论在生产调度 中的应用的关键在于建模和求解。阐述了本文的研究关注点、可行性以及博弈 论在生产调度中的研究思路。 以客户利益为核心，建立客户驱动的非合作博弈的硫化车间多目标调度模 型，将制造任务、硫化机映射到博弈模型中，研究使用遗传算法进行非合作博 弈模型的纳什均衡点求解，通过求解结果验证模型的正确性。 从生产方目标出发综合考虑全局目标，分析硫化车间的特点，建立基于生 产方驱动的非合作博弈硫化车间多人多目标模型，并给出纳什均衡调度的定义， 并分析纳什均衡的存在性。 针对生产方驱动的非合作博弈模型，以硫化车间生产调度为背景，将借鉴 传统调度算法，设计一种基于价格调节机制的算法，来求解松弛的纳什均衡调 度，再将纳什调度转化为原纳什均衡调度的解，最后对算法进行仿真，通过结 果验证算法的合理性。 1.4.2 本文的章节安排 第一章对生产调度问题做了概述，分析生产调度的特点，以及生产调度的 基于非合作博弈的硫化车间多目标生产调度研究 10 分类。并说明本文研究的背景及意义。 第二章 在查阅大量的文献基础上，介绍了博弈论的基本概念，总结了博弈 论在生产调度中的应用，并分析博弈论在硫化车间生产调度中的可行性。 第三章 分析了硫化车间的生产特点，构建客户驱动的硫化车间非合作博弈 模型。 第四章设计自适应遗传算法对客户驱动的硫化车间非合作博弈的模型进行 求解，并通实验仿真验证算法的合理性。 第五章 构建生产方驱动的非合作博弈硫化车间多人多目标模型，给出纳什 均衡调度的定义，并分析纳什均衡的存在性。 第六章 设计一种基于价格调节机制的算法，来求解上一章构建的模型的解， 最后对算法进行仿，通过结果验证算法的合理性。 第七章对本文的主旨进行概括，提出未来研究的展望。 青岛科技大学研究生学位论文 11 第二章第二章博弈论及在生产调度中的应用博弈论及在生产调度中的应用 2.1 引言 本章节首先概述了的博弈论基本概念，分类以及模型，剖析了博弈论的理 论精髓，指出博弈论在生产调度中的应用关键在于建模和求解。阐述了本文的 研究关注点、可行性以及博弈论在生产调度中的研究思路。 本章内容安排如下：2.1 对博弈论进行概述；2.2 总结了博弈论在生产调度 中的研究现状；2.3 讨论了博弈论在硫化车间生产调度研究中的市场前景；2.4 给出了博弈论在硫化车间生产调度研究中的可行性；2.5 本文的研究思路。 2.2 博弈论 2.1.1 博弈论概述 博弈论（gametheory）又称决策理论，但对博弈论的确切定义至今仍没有 统一，罗伯特 吉普森认为博弈论是关于多人决策时行为特性的理论17,哈桑 尼认为：博弈论是研究不同局中人基于其他参与者行为作出理性决策的理论18。 博弈论最早来源于游戏，如扑克牌、象棋、桥牌、 “剪刀，石头，布”游戏 等，游戏的参与者在游戏中总是设法运用各种策略与智慧来赢取游戏的胜利。 很多人在研究游戏的规律，其共同点是：游戏的参与者不仅要考虑自己的行为， 还要考虑对方的行为，简而言之是关于在竞争环境中如何进行决策的问题。这 种研究游戏的思想，很广泛的出现在我们生活的方方面面，如经济领域的贸易 谈判、价格竞争、生产管理；企业管理内的，劳资纠纷、契约制定、薪资体系 设计；企业发展战略制定，政治领域中的选举策略，大众方针制定，斗争策略， 军事领域的进攻与防御策略；战略战术都是在有冲突的，竞争的环境下，运用 理智的分析，做出行动决策，博弈论从开始的游戏中的单纯的竞争，发张成为 一个非常重要，应用非常广泛的一个学科分支。 博弈论是在对局中，为求取胜，参与者分析对方的策略而决定自己的策略。 同时是对不同参与者参与某一类问题过程的具体行为的研究，参与人员都是理 性的对行为认真执行的决策人19。 中国古代就有博弈论的思想，如中国经典的兵法著作孙子兵法 ，不仅是 基于非合作博弈的硫化车间多目标生产调度研究 12 军事上的一本经典著作，也算是一部最早的博弈论著作，博弈论最初的关注点 仅在于游戏中的胜负问题，博弈论仅仅停留在经验上，没有理论上的概括与发 展。在游戏中博弈论考虑的是个体的行为策略，以及个体的行动策略。 冯诺 依 曼（von Neumann） ，策墨 洛 Zermelo，波雷尔 Borel 等人对博弈 论的研究揭开了近现代博弈论研究的序幕。 1928 年冯诺依曼证明了博弈的基本原理，标志着博弈论的正式诞生。 1944 年博弈论划时代作品博弈论与经济行为诞生，在书中作者冯诺依 曼和摩根斯坦将二人博弈推广到多人博弈，并将博弈论应用经济领域，取得了 巨大的成功， 此书奠定了博弈论的基础理论体系。 上世纪六十年代，约翰福布斯纳什划时代的论文n 人博弈的均衡点 、 非合作博弈给出了纳什均衡的概念和均衡点的存在性定理。纳什用不动点 定理证明了均衡点的存在，从而奠定了为博弈论的坚实的理论基础。除此之外， 塞尔顿、哈桑尼等人的研究对博弈论发展壮大也起到巨大的推动作用。时至今 日博弈论已发展成一门应用领域广、理论较完善的重要学科。 2.1.2 博弈论的分类 根据不同的基准博弈论可以有不同的分类，可以参与者的数目来分为多人 博弈和双人博弈，也可以根据参与者互相了解的程度分为完全信息博弈和不完 全信息博弈；按照参与者之间是否有合作可以分为合作博弈和非合作博弈，非 合作博弈是本文应用的重点；也可以根据参与者行为方式的先后顺序分为静态 博弈和动态博弈。表 2-1 展示了常见的分类方式。 表 2-1 博弈论分类表 Table 2-1 Game theory classification 分类基准第一类第二类 按参与者约束力分合作博弈非合作博弈 按参与者行为时间数列分动态博弈静态博弈 按参与者了解程度分完全信息博弈非完全信息博弈 按持续时间分有限博弈无限博弈 按逻辑基础分传统博弈演化博弈 2.3 博弈论在生产调度中研究的现状 调度问题的研究始于 20 世纪 50 年代，1954 年 Johnson 提出了解决 n/2/F/Cmax 和部分特殊的 n/3/F/Cmax 问题的优化算法20，代表调度理论研究 青岛科技大学研究生学位论文 13 的开始。60-70 年代建立了经典调度理论并重视调度复杂性的研究体系。70 年 代后期，人们开始注意并重视调度复杂性问题的研究，提出了用于研究算法有 效性和问题难度的计算复杂度理论21。从 80 年代开始，应用人工智能、计算智 能和实时智能解决实际调度问题的智能调度方法22-24走上历史的舞台。近年来 智能调度方法成为解决实际调度问题最有效的途径和最有前途的研究方向之一。 目前主要的计算智能调度方法有 Hopfield 人工神经网络、进化算法、群智能算 法、禁忌搜索、模糊逻辑等。但目前已有的调度成果大多是解决单目标或同构 多目标调度问题，对异构多目标调度问题研究较少。 博弈理论解决的是有约束、多人多目标、且目标函数相互矛盾的决策问题。 一般将 Von Neumann 和 Morgenstern 在 20 世纪 40 年代提出的多人多目标决策 问题作为博弈理论的开端25。50 年代初 Nash 提出的 Nash 均衡理论奠定了非合 作博弈26的基础。60 年代，Selten 和 Harsanyi 相继将动态分析和不完全信息 引入到非合作博弈的研究中。博弈尤其是非合作博弈也逐渐成为经济学的重要 组成部分。究其原因，是因为经济学研究如何利用稀缺资源，并将它们分配给 不同个人的资源分配与竞争问题，而博弈理论对于以个体优化目标为基础的分 布控制与决策问题，是一种很好的数学研究工具。 解决传统调度问题的方法很难解决异构多目标调度问题，近年来已有相关 文献开始考虑用博弈 理论来描述和解决调度问题，建立基于工件独立性能指标 的博弈模型，通过工件的合作或非合作的行为形成相应概念描述下的可行调 度。 文献27 研究博弈理论的应用领域，提出运筹学将是博弈理论的重要应用 领域。文献中虽然提及采用博弈方法研究调度问题，但尚未考虑异构多目标的 调度问题。 文献28采用合作博弈研究单机调度问题，利用合作关系平衡客户间的利益， 建立了单机调度问题的合作博弈模型，但在竞争日益激烈的现状下，合作关系 很容易被打破。 文献29采用同时竞争与合作的博弈理论研究多机调度问题，建立了具有各 自性能指标的工件和机器的博弈模型，但缺乏理论分析与算例验证。 文献30研究的多机调度问题，应用进化博弈和纳什均衡的基本原理，将工 件看作局中人，加工机器是可选策略集，通过构造工件操作选择不同机器所获 得的支付矩阵来寻找博弈的 NE 结果。当调度问题的规模非常庞大时，不论从 理论的角度讲还是从实际应用的角度讲，都存在很难处理的问题，此时建立支 付矩阵，需要的工作量非常巨大。 基于非合作博弈的硫化车间多目标生产调度研究 14 文献31研究了求解非合作博弈问题的常用经典数学方法，提出了进化计算 方法有希望成为该问题的有效方法，但未给出进化计算求解非合作博弈模型的 相关性能。 文献32给出了单机调度的非合作博弈模型，讨论了 NE 解的存在性，并且 首次在建模与分析中考虑了不同工件具有的不同优化目标。同时也指出博弈的 NE 解可能具有较差的全局性能。 文献33在上文模型基础上引入了考虑全局目标的机器目标，并设计了一种 松弛