有关两代理排序问题的研究

发布时间：2018-08-23 12:34

【摘要】：排序问题在管理科学、计算科学和控制科学等领域有广泛的应用,代理排序问题则是近十年兴起的。代理排序可以利用博弈论的基本方法来对各个代理的目标进行权衡；也可以利用组合优化方法,将多目标问题转化为约束限制优化问题、Pareto最优问题或单目标优化问题。本文主要基于两代理排序的约束限制优化模型,研究单机和平行机环境下的两代理排序问题。 对于单机环境,我们研究了工件具有达到时间、目标函数均为最大完工时间的两代理排序问题。我们利用划分问题证明了该问题是NP-hard的,然后为其设计了限制情形的PTAS。对于平行机环境,我们首先研究了m台平行机两个代理目标函数均为完工时间和的问题,设计了该问题的拟多项式时间算法,并由此说明了该问题是普通意义下NP-hard的,而且基于拟多项式时间算法,给出了该问题限制情形下的FPTAS。最后我们考虑了平行机台数m不作为输入参数、两个代理目标函数均为最大完工时间的两代理排序问题。基于物体尺寸为有限个的装箱问题的动态规划算法,我们给出了限制情形下两代理排序问题的PTAS。
[Abstract]:Scheduling problems are widely used in the fields of management science, computational science and control science. Agent ranking can make use of the basic method of game theory to tradeoff the objectives of each agent, and can also use the combinatorial optimization method to transform the multi-objective problem into a constrained optimization problem or a Pareto optimization problem or a single-objective optimization problem. In this paper, based on the constrained optimization model of two-agent scheduling, we study the two-agent scheduling problem in single machine and parallel machine environment. For a single machine environment, we study the two-agent scheduling problem in which the workpiece has the time to reach and the objective function is the maximum completion time. We prove that the problem is NP-hard by using partitioning problem, and then we design the PTAs for the restricted case. For parallel machine environment, we first study the problem that the two agent objective functions of m parallel machines are the sum of completion time, and design the quasi-polynomial time algorithm for this problem, and show that the problem is NP-hard in the common sense. Furthermore, based on the quasi-polynomial time algorithm, the FPTASs for the restricted case are given. Finally, we consider that the number of parallel machines m is not the input parameter, and the two agent objective functions are the two agent ordering problems with the maximum completion time. Based on the dynamic programming algorithm for the packing problem with finite size, we give the PTASs for the two-agent scheduling problem under restricted conditions.
【学位授予单位】：华东理工大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O223

【共引文献】

相关期刊论文 前10条

1 顾燕红;唐国春;;排序博弈:合作博弈的新发展[J];重庆师范大学学报(自然科学版);2012年02期

2 何程;林诒勋;付乳燕;;具有双工期的最小化最大延迟的双目标排序(英文)[J];工程数学学报;2009年01期

3 慕运动;皮军德;郭晓;;序列错位限制下最小化完工时间和的继列分批重新排序[J];大学数学;2012年04期

4 李小衬;;单机不相容双目标最优批排序研究[J];长江大学学报(自科版);2013年13期

5 唐国春;樊保强;刘丽丽;;排序博弈的分类、进展和展望[J];重庆师范大学学报(自然科学版);2014年01期

6 戴秦;郑兴山;张新功;严广乐;;总迟后相关的两个工况代理的单机排序问题[J];工业工程与管理;2014年06期

7 FENG Qi;LI Shi-sheng;SHANG Wei-ping;;Two-agent single machine scheduling with forbidden intervals[J];Applied Mathematics:A Journal of Chinese Universities(Series B);2015年01期

8 慕运动;田晓正;;重新排序中目标函数与错位量的Pareto最优解[J];河南大学学报(自然科学版);2010年05期

9 周艳平;顾幸生;;一类流水车间调度问题的合作博弈[J];化工学报;2010年08期

10 慕运动;许小艳;;重新排序问题的Pareto最优解[J];河南师范大学学报(自然科学版);2009年06期

相关会议论文 前4条

1 ;A Note on Two-agent Single-machine Scheduling Problem with Deteriorating Jobs[A];Proceedings of 2010 Chinese Control and Decision Conference[C];2010年

2 ;A Single-machine Scheduling Problem with Two Agents and Decreasing Linear Deteriorating Jobs[A];Proceedings of the 2011 Chinese Control and Decision Conference（CCDC）[C];2011年

3 ;Two Scheduling Problems of Two Agents' Jobs with Unit Processing Time and Different Release Dates[A];第六届中国不确定系统年会论文集[C];2008年

4 刘晓惠;;一类带安装时间的多客户竞争排序问题[A];第十一届中国青年信息与管理学者大会论文集[C];2009年

相关博士学位论文 前10条

1 丁国生;多代理竞争排序问题的研究[D];上海大学;2009年

2 李士生;工件具有不相容性质的机器排序问题[D];郑州大学;2012年

3 慕运动;关于重新排序问题的研究[D];郑州大学;2007年

4 王林平;应用齐套概念的离散制造业生产调度问题研究[D];大连理工大学;2009年

5 何程;多目标分批排序及其相关课题[D];郑州大学;2009年

6 谭琦;多目标优化算法在多客户批处理机环境下的应用研究[D];中国科学技术大学;2012年

7 周艳平;基于博弈理论的多目标生产调度问题研究[D];华东理工大学;2013年

8 常天田;装配型供应链调度与协调研究[D];青岛大学;2013年

9 冯琪;多个代理的机器排序问题研究[D];郑州大学;2013年

10 王磊;OKP企业分散式项目计划与调度优化方法研究[D];哈尔滨工业大学;2013年

相关硕士学位论文 前10条

1 李小衬;与双目标分批排序相关的排序问题[D];兰州大学;2011年

2 王洁明;有关代理竞争排序问题的研究[D];华东理工大学;2011年

3 宋鹏;面向承运人与发货人的调度博弈问题研究[D];上海交通大学;2011年

4 孙彬;基于无线传输的公交车载媒体节目管理系统研究与开发[D];浙江工业大学;2011年

5 冯琪;多目标排序中的几个结果[D];郑州大学;2005年

6 葛荣荣;基于非合作博弈的异构目标生产调度研究[D];上海交通大学;2007年

7 关树明;一类与交货期相关的多目标排序问题研究[D];武汉科技大学;2007年

8 孙培;工件有到达时间的多代理排序问题[D];郑州大学;2008年

9 张丽;一些分组工件排序问题研究[D];郑州大学;2012年

10 王晓博;电炉生产过程能耗监测与电耗智能分析方法的研究[D];长春工业大学;2012年

，

本文编号：2199096