avatar avatar 我的文献 基于博弈理论的多目标生产调度问题研究 作者 周艳平 单位 华东理工大学 导师 顾幸生 关键词 多目标生产调度; 博弈论; 合作博弈; 非合作博弈; Nash均衡; 进化博弈
摘要
调度问题研究如何将单个或多个资源分配给等待处理的任务,并使某些指标得以优化。生产调度是现代制造业的重要环节,是实施计算机集成制造系统的关键。合理的调度方案可以提高生产效率和资源利用率,为企业带来显著的经济效益和社会效益。传统的调度问题研究中,一般由加工方根据交货期、机器使用效率和库存等目标要求进行调度排序。在客户驱动下的现代制造业中,每个客户都有自己的个性目标需求,如交货期、满意度和加工成本等目标,基于加工方的调度排序很难满足每个客户的个性需求。在现实生活中,存在客户采用合作或者竞争机制主动参与调度安排的情况。本文系统的探讨了基于客户成本需求的多目标生产调度问题,结合博弈理论在解决有约束、多人多目标优化问题的优势,研究利用博弈理论解决多目标生产调度问题。分别利用合作博弈理论、非合作博弈理论和进化博弈理论对基于客户成本需求的多目标生产调度问题进行分析和建模,研究了客户驱动的调度优化算法。本文主要研究成果包括:(1)归纳了生产调度问题和博弈理论的研究成果,综述了博弈理论应用于多目标生产调度问题的研究现状,阐明了博弈理论应用于多目标生产调度的可行性和思路。(2)系统介绍了合作博弈基本理论和合作博弈的核分配方法,利用合作博弈理论建立了基于客户成本需求的生产调度合作博弈模型,从而将生产调度问题转换为最大化合作博弈调度联盟的成本节省问题;分析了合作博弈调度解的存在性,证明了其存在的充要条件,讨论了合作博弈调度解和博弈核分配的关系,比较了合作博弈调度解集合和所有调度解集合、可行调度解集合、Pareto调度解集合的关系。(3)针对基本单机调度、基于交货期和拖期惩罚的单机调度、加工时间和工序相关的流水车间调度、具有相同阶段加工时间的混合流水车间调度等四类调度问题,分别建立了对应的调度合作博弈模型,证明了所建立的调度合作博弈是平衡博弈。在分析已有核分配方法不足的基础上,分别提出了比例增益成本分配方法、加权前后边际成本分配方法、平均节省成本分配的实现方法,证明了所提出的成本分配方法是核分配方法。实例分析表明,所建立的模型是有效的,所提出的成本分配方法能给出公平合理、客户满意的节省成本分配方案。(4)借鉴经济学中市场竞价的方法,在带约束的单机调度问题中,提出客户通过成本约束下的竞价来确定加工优先权,采用非合作博弈方法分析了客户的报价策略。分析了带成本约束的单机调度任务,定义了基于完全信息的带成本约束的单机调度非合作博弈模型,选择客户的报价作为策略,定义了综合考虑客户多目标的收益函数,从而将带成本约束的单机调度问题就转化为求取基于相应约束的纳什均衡解。用实例给出了在非合作博弈框架下,客户利用竞价策略竞争加工优先权的过程,验证了采用客户竞价的非合作方式能给出满足成本约束的调度排序。(5)分析了带成本约束和交货期的单机调度问题,建立了基于完全信息的带成本约束和交货期的单机调度非合作博弈模型。设计了客户的竞价机制,各客户首先根据成本约束和交货期要求给出自己的加工开始时间和报价,通过对比各客户的报价,确定各客户的加工优先权;设计了加工冲突时的冲突消解机制,给出了求解该非合作博弈调度的纳什均衡解的方法;通过实例验证了所提非合作博弈模型和利用竞价机制求取客户满意调度方案的有效性。(6)针对一类带模糊交货期的无等待流水车间调度问题,在各加工任务均要求满足最低满意度阈值的基础上,以最大化综合满意度为目标,对该调度问题进行了描述,引入进化博弈理论,构建了进化博弈调度模型,将调度任务映射到进化博弈模型中,将对调度问题的求解转化为寻找约束条件下的进化博弈均衡点。设计了一种启发式遗传算法求解进化博弈均衡点,该算法在进化过程中加入启发式竞争策略,大大提高了进化效率。仿真结果表明,用进化博弈调度模型来描述该类带模糊交货期的无等待流水车间调度问题是合理有效的,设计的求解算法,能通过反复博弈,使客户动态的调整自己的策略,克服有限理性的限制,逐步达到进化稳定均衡。本文结合博弈理论,根据合作机制是否能形成,分别采用合作博弈和非合作博弈方法,建立了各种类型的基于客户成本需求的生产调度问题的博弈模型,研究了博弈理论框架下调度问题的求解办法。该理论和方法建立了一种新的解决多目标生产调度的途径,有助于推动生产调度理论的发展,改善其性能,拓宽其应用领域,具有重要的理论意义和积极的实际意义。
下载 cnki {{liketext}}
©2018 - iData {{ message }} 关闭