工期可指派的两代理单机串行批交付调度问题研究

论文摘要

工期可指派的调度问题和多代理的分批交付问题都是在经典调度问题的基础上发展而来的。在之前的研究中,两种问题都是分开进行研究的。并且在工期可指派的调度问题中,工件的工期通常是事先给定的常量,但在很多情形下,工期是需要决策者根据实际情况来决策的变量。分批调度问题通常只考虑具有一个代理的情形,而忽略了现实中多个代理竞争使用有限资源的情形。本文主要研究具有两个竞争代理和工期可指派的单机串行批交付调度问题。对于两个相互竞争的代理,同一个代理连续加工的工件形成一个批次,该批次的工件完成加工后及时运输给相应的代理,每一批的运送都会产生一定的运输费用。每一批工件的完工时间等于该批最后一个工件的完工时间。本文主要探究了在两种工期指派方式CON（工件具有相同的工期）和DIF（工件具有不同的工期）下,每个代理均希望最小化与自身工件有关的优化目标（包括提前完工惩罚费用、拖期完工惩罚费用、储存费用、工期指派和运输费用）。总的调度目标是寻找最优的调度方案使得在一个代理的目标值不超过给定值的条件下,最小化另一个代理的目标值。本文具体研究三个问题,针对每个问题,主要讨论相应的NP-困难性,设计有效的求解算法,并分析算法的计算复杂性。本文证明了所研究的三个问题均是一般NP-困难的,并且给出了伪多项式时间最优算法和完全多项式时间近似方案。

论文目录

摘要

Abstract

第一章绪论

1.1 研究背景

1.2 研究现状

1.2.1 工期指派问题

1.2.2 集成生产和分批交付问题

1.2.3 多代理调度问题

1.3 本文的创新点

1.4 本文的结构安排

第二章单机串行批交付问题的描述与分析

2.1 问题的描述

2.2 概念说明

2.3 问题的结构分析

A:FB,D∈{CON,DIF}的求解193.1 伪多项式动态规划算法'>第三章问题1|D,s-batch|F^A:FB,D∈{CON,DIF}的求解193.1 伪多项式动态规划算法

3.1 伪多项式动态规划算法

3.2 完全多项式时间近似方案（FPTAS）

3.3 本章小结

A:G^B,D∈{CON,DIF} 和1|D,s-batch|G^A:G^B,D∈{CON,DIF}的求解'>第四章问题1|D,s-batch|F^A:G^B,D∈{CON,DIF} 和1|D,s-batch|G^A:G^B,D∈{CON,DIF}的求解

A:G^B的求解'> 4.1 问题1|D,s-batch|F^A:G^B的求解

A:G^B的伪多项式动态规划算法'> 4.1.1 1|D,s-batch|F^A:G^B的伪多项式动态规划算法

A:G^B的FPTAS算法'> 4.1.2 1|D,'-batch|F^A:G^B的FPTAS算法

A:G^B的求解'> 4.2 问题1|D,s-batch|G^A:G^B的求解

4.3 本章小结

第五章总结与展望

6.1 本文总结

6.2 本文展望

参考文献

致谢

攻读学位期间发表的学术论文目录

文章来源

类型: 硕士论文

作者: 李豆豆

导师: 殷允强

关键词: 调度,工期指派,批次交货,双代理,动态规划

来源: 昆明理工大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 昆明理工大学

分类号: O221

DOI: 10.27200/d.cnki.gkmlu.2019.001625

总页数: 57

文件大小: 3156K

下载量: 33

工期可指派的两代理单机串行批交付调度问题研究

论文摘要

论文目录

文章来源

相关论文文献

猜你喜欢