【摘 要】
：
经典排序论中使误工工件的个数为最少的单台机器排序问题,简称为误工问题[14],它是排序论中最基本的问题之一,具有重要的理论意义和实用价值.本文研究误工排序问题及其推广,研究这些问题的算法和改进.本文第一章,综述了排序论的学术意义和排序问题的研究概况.本文第二章,介绍了排序问题的一些基础知识.本文第三章,首先研究经典的误工问题1‖∑Uj,著名的Moore-Hodgson算法可以在时间O（n log
论文部分内容阅读
经典排序论中使误工工件的个数为最少的单台机器排序问题,简称为误工问题[14],它是排序论中最基本的问题之一,具有重要的理论意义和实用价值.本文研究误工排序问题及其推广,研究这些问题的算法和改进.本文第一章,综述了排序论的学术意义和排序问题的研究概况.本文第二章,介绍了排序问题的一些基础知识.本文第三章,首先研究经典的误工问题1‖∑Uj,著名的Moore-Hodgson算法可以在时间O（n log n）内得到误工问题的最优解.虽然经过改进,然而Moore-Hodgson算法最优性的证明仍然非常复杂.本文研究Moore-Hodgson算法最优性新的证明,给出Moore-Hodgson算法最优性的几种简单的证明.并且在Moore-Hodgson算法最优性证明的基础上,又分析和研究了求解几种推广的误工排序问题的算法,并且也给出相应的比较简单的新的证明.比如研究求解在保证工件的一个子集T中的工件必须不误工的前提下,使误工工件的个数为最少的误工问题1｜T｜∑Uj的Sidney算法,并且给出Sidney算法最优性新的证明;研究求解工件的就绪时间不相同、但是与交货期有“一致性”关系时,使误工工件的个数为最少的误工问题1｜（ri≤rj）（?）（di≤dj）｜∑Uj的KIM算法.对误工排序问题1｜（ri≤rj）（?）（di≤dj）｜∑Uj,最近李杉林、陈志龙、唐国春用反例指出Kise、Ibaraki、Mine证明最优性时提出的引理2是错误的.本文分析引理2的错误所在,给出修改后的引理2’,由此应该相应修改KIM算法,然而,最后,我们证明KIM算法仍然可以得到最优解.在本文中也给出了越民义先生对KIM算法最优性的一个新的简单的证明.接着本文分析和研究了工件之间存在先后关系的误工问题1｜prec｜∑Uj,根据工件之间的先后关系找到一个求解这个误工排序问题的有效算法.并且在此基础上,本文又分析和研究了工件有先后约束的最小带权误工工件数排序问题1｜prec｜∑wjUj,在没有任何约束条件的情况下,根据工件之间的先后关系找到一个求解这个带权误工工件数排序问题的有效算法.本文第四章,分析和研究了多台机器的误工排序问题.在罗守成,唐国春研究两台平行机误工排序问题P2‖∑Uj的基础上,给出了三台平行机误工排序问题P3‖∑Uj的解的一些性质.并且在Moore-Hodgson算法的基础上研究了多台机器误工排序问题Pm｜pj=1｜∑wjUj和Pm｜T,pj=1｜∑Uj等.本文第五章,对全文作了一个总结,并提出了一些有待研究的问题.
其他文献
带有约束的非线性规划问题广泛见于工程、军事、国防、经济等许多领域。求解它的主要方法之一是把它转化为无约束规划问题,然后利用求解无约束规划问题的最优化方法去求解。罚函数方法是将约束规划问题无约束化的重要方法之一,该方法通过求解一个或一系列罚问题而得到原约束规划问题的解。在上世纪六十年代后期,首先由Eremin和Zangwill给出了精确罚函数的概念,从那时起对精确罚函数方法的研究一直吸引着很多学者。
本文简要论述了求解定态薛定谔方程解析解与数值近似解的方法,研究了多项正幂与逆幂势函数叠加条件下径向薛定谔方程的解析解。根据量子系统波函数必须满足单值、连续和有限的标准条件,首先求出径向坐标r→∞以及r→0时的解析解,然后采用奇点邻域附近的级数解法与求得的渐近解相结合,确定指标s以及幂函数各项系数间的约束关系,通过幂级数系数比较法得到势函数叠加势为V（r）=α1r~8+α2r~3+α3r~2+β3r
混沌是非线性动力系统所特有的复杂状态。现在已经有很多的方法去研究混沌性状,其中应用拓扑学的思想方法能够避免复杂的计算,是研究混沌理论的有力工具。本文采用这种方法研究了混沌特有的拓扑结构和性质,更重要的是将群的作用引入到拓扑空间中,寻找通往混沌的新道路。在第一章中,我们简要地介绍了拓扑动力系统的发展现状及本文的写作背景和研究的主要内容。在第二章中,我们主要研究了Li-Yorke混沌集和非游荡点集的关
本文主要研究了含有等式约束的非线性整数规划问题的新的填充函数方法。第一章主要综述了全局优化问题的意义以及解决全局优化问题的方法之一:填充函数方法的发展及研究意义,介绍了几种重要的填充函数以及国内外研究现状。为了系统地介绍非线性整数规划问题的填充函数方法,在第二章介绍了和本文一脉相承的文献[7]中的箱子集约束的非线性整数规划问题的填充函数方法,及其该填充函数的性质和算法、算例。然后在第三章主要介绍了
本文简要论述了求解定态薛定谔方程精确解与数值近似解的方法,研究了三项正幂与四项逆幂势函数叠加条件下径向薛定谔方程的解析解。通过量子力学我们知道,一般复杂的叠加势很难求得解析解.但考虑到耦合条件后,这种叠加势是能够给出其波函数和能量方程.本文在量子系统波函数必须满足单值、连续和有限的标准条件下,先求出径向坐标r→∞以及r→0时的渐进解,然后采用奇点邻域附近的级数解法与求得的渐近解相结合,确定指标s以
设H是一具有内积〈?, ?〉和范数‖?‖的实Hilbert空间,F :H→H是一算子。C是H的一非空闭凸子集,在第二章中我们考虑下面的变分不等式:求u*∈C,使得,VI（F,C） :〈F（u*）,v-u*〉≥0,v∈C。设T1,T2…TN:H→H是N个非扩张映象,使得,（?）,任给x0∈H,定义（?）,其中（?）,F :H→H是η强单调和k-Lipschizian映射,在一定合适假设下,证明了{x
伪轨跟踪性是在伴随着动力系统中稳定性的研究与发展而产生的,已经成为动力系统理论中的重要动力性状之一。“伪轨”不是真正的轨道,它是带有误差的映射迭代下的“轨迹”。伪轨跟踪性质与系统的稳定性态和混沌性态都有着密切的联系,在动力系统的定性理论中起着重要的作用。基于理论和应用的需要,人们从不同的标准出发相继提出了不同的伪轨概念,各种各样的跟踪性也应运而生,例如平均跟踪性,弱跟踪性,强跟踪性,极限伪轨跟踪性
动力系统的研究最早始于十九世纪,但拓扑动力系统的研究在近三十年才受到较为广泛的重视并呈现出较大的活力,尤其是一维动力系统的研究更是吸引了许多科学学者的关注,特别地对于线段自映射和圆周自映射的研究发展迅速,对于各种映射的研究也开始层出不穷,本文主要就2∞映射进行了深入探讨和系统的研究。在第一章中,简要地介绍了拓扑动力系统的发展现状及本文的写作背景及研究的主要内容;第二章给出全文预备知识,对2∞映射的
非线性算子不动点理论是非线性泛函分析的重要组成部分,同时也是人们关注的重点问题之一,尤其是非线性算子方程解的迭代逼近问题,已成为非线性泛函分析领域近年来研究的活跃课题,并取得了显著的成绩。在不动点问题研究的众多方向中,关于构造逼近不动点序列的迭代收敛问题以及其在控制、非线性算子和微分方程等方面的理论结合及应用成为研究的主流问题,对这方面问题的研究会在实际运用中起到至关重要的作用。本文研究了两类非线
全局优化问题广泛见于经济模型、金融、网络交通、数据库、集成电路设计、图象处理、化学工程设计及控制、分子生物学、环境工程学等。二次规划问题在现实生活中有着重要的意义。无论是在局部优化问题的研究还是在全局优化问题的研究中,二次规划问题始终得到广泛的重视。二次规划有着广泛的应用背景,特别是在组合优化中有着很多重要的应用,然而很多二次规划问题都是NP-难或NP-完全的。因此,研究二次规划问题是非常必要的。