【摘 要】
：
该文研究自由作业排序问题稠密时间表的性质,并研究在某些特殊情形下自由作业排序问题的多项式时间算法.自由作业(open shop)是排序论中一种多工序(multi-operation)作业,是
论文部分内容阅读
该文研究自由作业排序问题稠密时间表的性质,并研究在某些特殊情形下自由作业排序问题的多项式时间算法.自由作业(open shop)是排序论中一种多工序(multi-operation)作业,是工件依次在机器上加工的次序不指定的可以任意选择的一种加工方式.正由于这种"不指定"和"任意选择",是"open"的加工方式,因而自由作业的可行解集比较流水作业(flow shop)和异序作业(job shop)的可行解集要"大"得多,搜索最优解也就困难得多.已经证明,绝大多数的自由作业都是NP困难的.避免不必要的空闲是自由作业首先要研究的课题.对于已经没有不必要空闲时间的加工时间表,称为稠密时间表(denseschedule).研究稠密时间表在理论和应用两方面都是非常有意义的工作.该文的研究内容分为三个部分,前两部分分别研究工件有相同的到达时间(arrival time或release date)和不相同的到达时间两种情况下稠密时间表的性能比猜想,第三部分则研究在特殊情形下自由作业加工全长问题的多项式时间算法.
其他文献
该文的研究对象就是小3-流形(small 3-manifolds)中的一类分离的可定向的闭曲面.这类分离的闭曲面满足下面的性质:它将小3-流形分成两个3-流形,而且在这两个3-流形中都可压缩
目前,中国轴承行业中对滚动体表面质量的检测,仍采用传统的人工检验的方法,其质量验收满足不了在高温、高速等工作条件下的滚动体的设计要求.这样,就要求寻找一种自动检测方
该文从基因聚类的角度提出了一个基因表达数据的统计模型.在该统计模型的基础上,讨论了两种常用的聚类方法K-Means和Kohonen(Winner Take All)的实质和优缺点,指出在这一统计
该文研究了用正交设计方法求解区间约束最优化问题.提出了以正交设计原理为基础的两种方法——正交表法和加点正交表法求解非线性规划区间约束最优化问题;最后对算法安排正交
分歧现象是半线性偏微分方程研究领域当中一类非常重要的非线性现象,它的研究可以追溯到18世纪以来对流体力学,非线性震动等一些现象的研究.至今,在动力系统,非线性分析等研
在研究微分方程的过程中,有界解和概周期解等价的Bohr-Neugebauer理论并不适用于所有的概周期微分方程.而为了保证某些类微分方程有概周期类型解,往往需要增加某些条件,诸如F
该文较全面地研究了支撑向量机的学习算法,分析了已有算法的性能,将内点算法应用到支撑向量机的训练,同时对训练支撑向量机的线性规划方法提出了一种稳健实施策略.该文中,我
带有逐段常变量的微分方程是连续和离散系统的混合,具有微分方程和差分方程的双重性质,在控制理论和生物模型中有重要的作用.这种方程的概周期解的存在和唯一性问题已经得到
弹性薄板振动的理论分析与数值模拟由于其重要的应用背景与理论价值,一直是偏微分方程理论与应用关注的研究对象之一.但绝大多数的研究工作均只考虑薄板的横振动或纵振动问题
自二十世纪七十年代以来,非线性科学一直是各学科普遍关注的热点研究领域.作为非线性科学研究中的一个非常活跃的数学分支一全局优化的理论和算法从其诞生之日起便受到广泛的