博弈视角下的多目标生产调度问题探讨

1 博弈理论

博弈论是研究两个人或者多个人谋略和决策的理论, 是现代数学和运筹学的分支。

1.1 博弈理论发展

博弈论思想在孙子兵法和“田忌赛马”中都有体现, 而真正现代意义上的博弈理论是1838年, Augustin Cournot提出了“寡头竞争”“问题解”, 学术界认为这是现代非合作博弈理论中核心理念-纳什均衡的早期版本, 之后又有一批学者对不完全竞争问题进行了研究, 这些问题就是博弈论的思想基础。之后在1944年, 冯·诺依曼和摩根斯坦的《博弈论与经济行为》开始对博弈论进行系统化, 表示着博弈论这门学科的建设, 在1950年, Tucker提出的“囚徒困境”是非合作博弈的典型范例。在上世纪60-70年代, 子博弈完美纳什均衡、完美贝叶斯纳什均衡、动态博弈、不完全信息博弈等等概念的提出极大的推动了博弈论的发展, 并在80年代以后开花结果, 成为研究社会经济现象有力的数学工具, 对决策主体的理性决策均衡结果有着重要的指导意义。

1.2 博弈论在生产调度中的应用

生产调度问题是对客户或者加工性能指标在一定约束条件下的优化和加工任务在稀缺加工资源上的分配。约束存在复杂性, 客户目标和加工目标存在多样性, 而加工资源稀缺, 所以生产调度中存在着激烈的竞争, 生产调度中个体之间存在着严重的竞争, 所以, 生产调度问题和经济问题之间存在一定的相似性, 所以, 博弈论是可以应用到生产调度问题中来的。

合作博弈论在生产调度中的应用最早应用于生产调度排序和成本分配, 在1986年, Tijs提出可以使用夏普利值方法解决成本分配问题, 也有学者结合排序理论和合作和博弈理论, 采用排列博弈方法解决生产调度问题。近年来, 重视个体理性的非合作博弈在生产调度中的应用也越来越广泛, 参与者首先通过市场竞争获得加工资源, 之后找寻目标相近的参与者进行合作, 建立具有各自竞争性能指标的工件和机器博弈模型。

根据已有研究结果, 合作博弈对调度方案的制定更为关注, 而对收益成本的分配方面还存在一定的不足, 需要相关研究工作者的继续努力。

2 基于博弈的多目标生产调度

2.1 合作博弈

合作博弈中存在一个重要假设, 即假设参与者能够形成联盟。所以, 生产联盟的形成是合作博弈的基本条件。合作博弈可以使用特征函数表达, 也就是博弈的特征性。

2.1.1 核配置

参与者能够带来收益, 就面临着收益的分配问题, 这就是核配置研究的问题。联盟稳定存在的情况下没有参与者愿意离开联盟。

合作博弈的解释一个集合, 实际利用过程中希望获得一个合理解, 其中夏普利值就是一个应用广泛的核配置。

2.1.2 核分配

(1) 不可分成本平均分配

这是一种非常直观的方法, 参与人承担各自可分成本, 不可分成本在所有参与人之间分摊。但是这种方法没有充分考虑一些参与人数较小的联盟, 很多小部分参与者组成的小联盟往往效率更高, 参与者在小联盟中的成本分配可能会小于大联盟, 所以这部分参与者没有参加大联盟的动力, 可能无法形成大联盟。

(2) 夏普利值分配

按照亚当斯的公平理论, 按照贡献率的大小进行资源分配, 提高团队产出水平, 提高成员合作积极性。基本思想是, 参与人获得的收益或者承担成本和参与联盟的边际贡献平均值相等。

2.2 生产调度建模

2.2.1 考虑客户成本需求的多目标生产调度模型

几个加工任务竞争有限生产资源加工任务可能来自不同客户, 有着不同的生产目标。将基于客户成本需求的多目标生产调度模型定义成五元组 (N、M、p、c、) 。调度模型中, N是客户的结合, N={1, 2, 3, …n}。

客户采用合作机制, 相互转让优先加工权, 找寻一个最佳排序之后, 获得总加工成本, 每一个客户都有独立的完工时间相关成本函数, 从全局考虑, 总会有一个能够降低所有客户加工成本的调度方案。

2.2.2 调度解与博弈核分配关系

调度解和博弈核分配之间存在一定的关系, 在合作受益或者成本节省的驱使下才会形成生产联盟, 才能够获得合作博弈调度解, 所以, 只要合作博弈解存在, 就至少存在一个核分配。

2.3 流水车间博弈合作成本分配

2.3.1 基本单机调度合作博弈

n个客户形成生产联盟, 找寻最优解, 就能够获得最大的成本节省, 最后将总节省成本在客户之间合理分配。

2.3.2 比例增益成本分配

按照Smith规则找寻最优调度排序, 将相邻客户按早顺序调整获得的成本节省在两个客户之间均分, 通过相邻客户之间的两两调整最终获得最优调度排列。但是这是一种并不绝对公平的分配方法, 有些时候可行性差。

3 结语

调度问题的研究目标是将有序的生产资源合理分配给多个生产目标, 从而实现某些指标的优化。生产调度是现代制造业中的关键性问题, 从博弈论视角对这个问题进行研究能够有效提高企业生产效率, 节省成本, 创造更多的经济效益和社会效益。

摘要：主要研究博弈视角下的多目标生产调度问题, 学习了博弈理论, 分析博弈论在生产调度中应用的形式, 从核分配、生产调度建模、流水车间博弈合作等方面, 对多目标生产调度问题进行了博弈论讨论, 认为博弈论在生产调度问题中的应用能够获得更合理的调度方案, 研究价值很高。

关键词：博弈,多目标生产调度

参考文献

[1] 廖伟志, 古天龙, 王汝凉, 等.基于混杂Petri网的柔性制造系统免疫调度算法[J].系统仿真学报, 2010, 22 (1) :205-209.

[2] 于海斌, 薛劲松, 王浩波, 等.一种基于神经网络的生产调度方法[J].自动化学报.2012, 25 (4) :449-456.