排序理论中若干问题的理论分析和算法设计

发布时间：2017-10-08 13:19

  本文关键词：排序理论中若干问题的理论分析和算法设计

  更多相关文章： 混合流水作业 供应链问题 排序博弈 多项式时间算法 社会无序代价

【摘要】：排序理论是运筹学组合优化领域中最为活跃的分支之一.自上世纪50年代以来,一直备受生产制造、供应链管理、互联网等领域研究人员的关注,并随着理论研究的深入及实际生产生活的需要,出现了很多新的模型.本文主要研究三类排序问题中的新模型：一个新的混合流水作业排序模型,一个新的两阶段供应链排序模型和一个混合协调机制下的排序博弈模型.对于前两个模型核心在于分析问题的计算复杂性并给出高效的最优算法,对于第三个模型主要分析它的社会无序代价从而评判出该协调机制的优劣.全文共分四章.第一章首先介绍了排序问题、计算复杂性和算法、算法博弈论和排序博弈等的基本概念和理论背景,接着论述了与本文相关的三类排序问题的研究背景和已有主要成果.第二章讨论了一个两台机器两个加工工序的混合流水作业问题.每个工件都包含两个加工工序,第一个工序可以在任何一台机器上加工,它被称为柔性工序；但是第二个工序必须在第一个工序完成后只能放在第二台机器上加工.该问题的关键在于如何选择工件柔性工序的加工机器使最大完工时间(makespan)极小化.首先对于该问题的一般模型我们给出了一个完全多项式时间近似方案(FPTAS),而对于工件加工时间均为单位时间的特殊情况,根据两台机器之间的缓存情况不同分成几个研究模型,我们分别给出了这些模型的最优算法并且发现了一个非常有趣的结果：机器间的缓存空间不少于2的前提下,再增加缓存空间并不会得到更好的结果.第三章研究了一个分批加工以准时交货为目的的排序问题,该问题相当于一个“生产-运输”两阶段的供应链问题.在这个问题中有K个客户的订单需要加工,每个订单包含若干个单位加工时间的工件并且有一个交货期.一个客户的订单被分成若干批次,当机器加工完一个批次的工件之后用具有载重限制的货车运送到客户仓库.客户要求准时交货,早于交货期或者晚于交货期都要承担一定惩罚费用,而每次用货车运送一批完工的工件到客户仓库都会产生定量的运输费用.研究的目标是找到一个加工安排方案使得工厂的总费用最小.首先在工件必须从0时刻开始加工的假设下(记作假设(a)),针对单客户模型,我们给出了最优调度的一些性质,在此基础上设计了一个多项式时间算法,并进而针对多客户模型的几个特例给出了动态规划算法.其次我们考虑更接近实际的模型,也就是不带上述假设(a)的情况下,针对单客户模型我们也给出了一个多项式时间算法.而对于多客户情况的几个特例也给出类似带假设(a)情况下的动态规划算法.第四章讨论了一个排序博弈问题.在这个排序问题中,每个工件是一个自私的参与者,它可以自主地选择一台机器加工以谋求自身加工费用(通常为工件的赋权完工时间)最小化.每个工件在0时刻到达并且不允许中断加工,而每台机器也是在0时刻达到并且可以任意选择自己的协调机制.这一点不同于之前绝大多数排序博弈问题的研究.在那些研究中,机器被要求统一按照某种协调机制而不像本章研究的问题那样,允许不同机器采用不同协调机制.本排序博弈问题中,共有两个协调机制可供不同机器选择,它们是赋权最小加工时间优先(wSPT)机制和按比例分配速度(PS)机制.而问题的社会目标为工件的赋权完工时间总和而不是以往的研究中通常所采用的最大完工时间(makespan).对于该排序博弈问题,我们首先给出一个该问题的松弛线性规划,然后写出该线性规划问题的对偶规划问题.通过比较上述两个规划问题的最优目标以及该排序博弈问题的最优社会目标和混合纳什均衡解的最差社会目标这四个数值,从而得到这个排序博弈问题的混合社会无序代价为4.
【关键词】：混合流水作业 供应链问题 排序博弈 多项式时间算法 社会无序代价
【学位授予单位】：上海大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O223
【目录】：

• 摘要6-8
• Abstract8-14
• 第一章 绪论14-26
• 1.1 排序问题14-15
• 1.2 计算复杂性和算法15-18
• 1.3 动态规划18-19
• 1.4 算法博弈论与排序博弈19-21
• 1.5 三类与本文相关的排序问题21-24
• 1.5.1 混合流水作业排序问题21-22
• 1.5.2 供应链排序问题22-23
• 1.5.3 混合协调机制的排序博弈问题23-24
• 1.6 论文概述24-26
• 第二章 一类特殊的两阶段混合流水作业问题26-47
• 2.1 引言26-28
• 2.1.1 问题描述和背景26-27
• 2.1.2 相关的研究和结果27-28
• 2.1.3 我们的结果,28
• 2.2 基本假设和已有结果28-29
• 2.2.1 基本假设28-29
• 2.2.2 有的结果29
• 2.3 模型SHFS(∞)的一个全多项式时间近似方案29-30
• 2.4 工件均相同的SHFS(B)模型的最优算法30-46
• 2.4.1 已知的性质31-32
• 2.4.2 模型SHFSI(no)的最优算法32-38
• 2.4.3 模型SHFSI(B)的最优算法38-46
• 2.5 结束语46-47
• 第三章 一个加工-运输模式的两阶段供应链调度问题47-74
• 3.1 引言47-49
• 3.2 符号说明和问题描述49-52
• 3.2.1 符号说明49
• 3.2.2 问题的定义49-52
• 3.3 假设(a)条件下问题IBSJS的单一订单模型52-64
• 3.3.1 知的性质53-54
• 3.3.2 d=0和054-55
• 3.3.3 d≥r时问题的最优算法55-59
• 3.3.4 b59-64
• 3.4 满足假设(a)的多客户订单问题K-IBSJS的几个特殊情况64-69
• 3.4.1 已知的性质65-66
• 3.4.2 两个特殊情况的动态规划算法66-69
• 3.5 一般情况下的单订单问题IBSJS的最优算法69-73
• 3.6 结束语73-74
• 第四章 一个混合协调机制排序博弈问题的研究74-92
• 4.1 引言74-75
• 4.1.1 相关的研究情况介绍74-75
• 4.1.2 我们的结果75
• 4.2 基本概念和符号介绍75-77
• 4.3 存在纯纳什均衡解实例的PPoA的一个上界77-87
• 4.3.1 符号说明77-78
• 4.3.2 PPoA的一个上界78-87
• 4.4 排序博弈的混合社会无序代价分析87-90
• 4.4.1 混合策略组合87-88
• 4.4.2 排序博弈的混合社会无序代价88-90
• 4.5 结束语90-92
• 参考文献92-99
• 博士期间完成的工作99-100
• 致谢100

，

本文编号：994243