几类资源约束下加工时间可变的排序问题

摘要

排序问题是运筹学和组合最优化领域的一个重要分支,现已广泛应用于机器制造、生产管理、运输调度等方面。经典排序中工件的加工时间是固定的常数，但在实际生产中，任务的加工时间往往与其开始加工时间，加工所在位置或资源的分配量等因素有关。
　　第一章，主要介绍了排序问题的研究背景、发展现状以及本文所做的工作。
　　第二章，我们同时考虑了学习和退化效应双重因素以及资源分配量对任务加工时间的影响，并结合两种工期指派方法（工期窗口指派方法和不同工期指派方法）进行分类研究。对于工期窗口指派问题，目标是确定最优的工期窗口开始时间，工期窗口宽度、最优的资源分配量以及最优的任务排序最小化目标函数。对于不同工期指派方法，目标是确定任务的最优排序，每个工件的最优工期，以及分配到每个任务的资源量最小化目标函数。证明了这两个问题均是多项式时间O(n4)内可解，并给出了最优算法。
　　第三章，本文将目标函数为最小化加工时间和拒绝费用之和的单机可拒绝排序问题进一步拓展到平行机环境下，加工时间变为关于开始加工时间的线性退化函数，目标函数修改为工期，误工工件惩罚，总完工时间以及拒绝工件的惩罚费用之和。首先运用动态规划方法证明伪多项式时间内可求得问题的最优解，并运用简化状态空间的方法给出一个全多项式近似策略。时间复杂度为?O(n5/ε2D2), D=max{lnmax,ln(1+b)}的全多项式近似策略（FPTAS）。
　　第四章，研究带有加工和运输两个阶段供应链的系列批排序问题，其中任务的加工时间是关于双资源消耗的凸函数。在系列批中工件要求连续加工且每批工件的完工时间等于此批中最后一个被加工工件的完工时间，加工完成之后，每批工件通过容量有限的单车辆运输到客户，而且每辆车一次只能运输一批工件。我们给出了复杂度为O(n2logn)或O(n2lognlog(1/ε))的算法确定任务分批和批排序以及资源消耗量极小化最大完工时间。
　　最后，对本篇论文进行了总结，并提出一些有待解决的排序问题的研究方向。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

一、 排序问题研究背景

二、 三参数表示法及符号说明

三、排序问题的国内外研究现状

四、本文主要内容及结果

第二章 资源约束下加工时间可变的几类工期指派问题

一、引言

二、问题描述

三、共同工期窗口宽度指派问题

四、不同工期指派方法

五、小结

第三章 两台平行机环境下加工时间退化的可拒绝排序问题

一、引言

二、问题描述

三、最优解的性质

四、动态规划

五、简化状态空间构造FPTAS

六、小结

第四章 单机两阶段供应链的双资源系列批排序问题

一、引言

二、问题描述

三、极小化问题（4.1）加工阶段的最大完工时间

四、问题（4.1）的最优算法

五、小结

结论和展望

参考文献

致谢

个人简历

在学期间的研究成果和发表的学术论文