一些单机和平行机排序情形的研究

发布时间：2017-11-19 06:23

  本文关键词：一些单机和平行机排序情形的研究

  更多相关文章： 排序情形 特征函数 代价分配 夏普里值 EWCS规则

【摘要】：本文主要研究了一些单机排序情形和平行机排序情形。在一个排序情形中,一些工件需要在若干台机器上加工,工件分别属于不同的客户。客户在他的工件完工之前会产生代价,在本文中代价是时间的线性函数,即单位时间的代价保持一致,称为客户的权重。不同加工顺序下客户的代价不同。这个问题可以看成是多个参与人在做决策,选择众多可能工序中的一个作为最后执行的工序,在达成协议的过程中还需协调利益冲突。在已有的文献中,应用合作博弈的理论去解排序情形产生的博弈被称为排序博弈。通常采用收益博弈理论来讨论排序情形,因此需要给出一个初始工序,在此基础上客户之间产生合作,并且尽量兼顾个人利益。然而初始工序强烈影响着客户的最终支付,在初始工序中占据一个好的位置意味着较少的代价支付。本文主要讨论无初始工序排序情形。我们主要研究一些排序情形对应的排序博弈的特征、设计分配规则并分析最终支付的公平性。全文主要分为六部分内容。第一章主要介绍了合作博弈论的基本思想和一些解的内容,排序问题的三参数表示法以及算法相关的一些概念,并介绍了合作博弈在排序理论中的应用这一课题的研究现状。第二章采用成本博弈的方法研究了单机无约束排序情形,客户的代价为工件的加权完工时间。与收益博弈不一样,不需要给出初始工序。我们给出了一个基于任意加工顺序的EWCS分配规则,并论证了这个规则的公平性,即这个规则会促使客户选择排序问题的最优工序。此外,我们把这个规则推广到单机带链式优先约束的排序情形,并根据解的性质做出一定的调整。第三章讨论了单机工件有学习效应的最大完工时间排序情形,这时每个客户的代价为客户的实际加工时间。假设初始工序为恒等排列,该问题最终可归纳为排列博弈,或者是特殊的指派博弈,本文给出一个单值解。若没有初始工序,则可引入指派博弈理论并给出一个基于指派博弈的核元素得到的解。第四章讨论了两台机器上的排序情形,一个客户恰好拥有两个个工件且它们分别要在机器1和2上加工,客户的代价为他对应的工件的加权最大完工时间。对于客户的两个工件加工时间完全一致的特殊情形,其分配规则可沿用单机排序情形的EWCS规则。对一般情况,可采用启发式算法编程求解最终加工顺序,我们制定了依赖于工序的代价分配方法。第五章对m台平行机的排序情形进行了探讨,由于对应的排序问题是NP-难的,主要对两种特殊情形的夏普里值计算进行了推导：当工件的加工时问一致时以及当工件的权重完全一致时,夏普里值的计算可在多项式时间内完成。第六章对未来的研究方向做了一些展望,并对本文做了一个总结。
【学位授予单位】：华东理工大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O223

【相似文献】

中国期刊全文数据库 前10条

1 张智聪;郑力;翁小华;;基于增强学习的平行机调度研究[J];计算机集成制造系统;2007年01期

2 陈荣军;唐国春;;平行机的供应链排序[J];系统科学与数学;2010年02期

3 陈荣军;张峰;唐国春;;平行机及自由作业的排序与转包[J];系统工程学报;2011年05期

4 陈荣军;唐国春;;平行机的排序与转包(英文)[J];数学季刊;2012年04期

5 蒋大奎;李波;;平行机作业环境下的订单分配与排序[J];管理学报;2013年06期

6 王成尧,汪定伟;有模机配合约束的平行机台调度方法[J];东北大学学报;1999年04期

7 曾欢欢,胡建华;可换速平行机工件带起止值的抢先进度表[J];数学理论与应用;1999年02期

8 蒋大奎;李波;曹立思;;考虑转包的平行机供应链排序[J];控制与决策;2014年05期

9 陈仕平,张国川;两台平行机的实时到达在线排序[J];应用数学学报;2000年01期

10 周伟刚;高成修;黄凯;;加工时间可控和简单线性增长的平行机排序[J];应用数学学报;2010年04期

中国重要会议论文全文数据库 前1条

1 闻振卫;;一类平行机上的任务指派问题及其动态规划算法[A];中国运筹学会第九届学术交流会论文集[C];2008年

中国博士学位论文全文数据库 前4条

1 刘珊珊;一些单机和平行机排序情形的研究[D];华东理工大学;2015年

2 程贞敏;平行机调度问题研究的若干结果[D];北京师范大学;2008年

3 蔡圣义;同类平行机在线半在线排序参数界的若干研究[D];浙江大学;2010年

4 何龙敏;一类平行机和批处理机组成的二阶段柔性流水作业问题[D];上海大学;2006年

中国硕士学位论文全文数据库 前10条

1 郭平宁;工件带权重的平行机博弈排序问题[D];曲阜师范大学;2015年

2 李大伟;考虑延误的平行机可拒绝排序[D];曲阜师范大学;2015年

3 洪文益;与平行机排序相关的几个组合问题研究[D];清华大学;2013年

4 李松松;在平行机博弈排序中的近似强纳什均衡问题[D];曲阜师范大学;2013年

5 王君丽;有加工权限平行机在线问题研究[D];浙江大学;2012年

6 财玉华;具有非交叉维修时间的平行机在线排序[D];郑州大学;2007年

7 莫祯贞;改进粒子群算法在模糊环境下平行机批调度问题中的应用研究[D];中国科学技术大学;2010年

8 林琳;具有同时性约束的平行机排序问题[D];郑州大学;2006年

9 徐武来;具有完工期和工装数量约束的平行机调度方法[D];广东工业大学;2012年

10 何晓琼;一致平行机上在线排序[D];湖南师范大学;2009年

，

本文编号：1202629