论文部分内容阅读
我们将限制某些工件不能同时处理的平行机排序问题称为异时排序问题，本文我们讨论工件加工时间相、目标为总完时时间最小的异时排序问题，我们证明了当机器台数为2时，该问题等价于图上的最大匹配问题，因在存在组合器多项式时间算法，但量当机器台数为3或都多于3时，该问题是强NP困难的。
异时排序问题的算法复杂性
【摘 要】
：
我们将限制某些工件不能同时处理的平行机排序问题称为异时排序问题，本文我们讨论工件加工时间相、目标为总完时时间最小的异时排序问题，我们证明了当机器台数为2时，该问题等价
【机 构】
：
中国科学院系统科学研究所管理决策与住处系统开放实验室
【出 处】
：
应用数学与计算数学学报
【发表日期】
：
1999年2期
【基金项目】
：
国家863项目资助
其他文献
本文通过对网络中有向支撑出树性质的研究，提出了在有向网络图中寻找以某一定点为根的最小有向支撑出树一产简便的计算方法，并给出了应用该算法进行了实际操作的一个算例。
本文根据矩阵的广义逆理论,建立了回归分析中进行参数估计的一种新方法,该方法更简单更精确.
本文提出了一种改进的乘幂法，一方面大大加快了收敛速度，另一方面可以方便地计算全部的特征值，最后给出一个计算的特征值通用算法。
Ｓａｒｋｅｒ和Ｐａｒｉｊａ（１９９６）建立了生产系统最优生产批量和原材料订购决策模型，然而他们的模型仅局限于单阶段生产系统，本文将他们的模型扩展到多阶段生产系统，我们首先建立了使整个系统总成本最小的各阶
将经典“试探函数组”1，x,x^2应用于扩展乘数法，建立了一个判别线性正算子能否改造为逼近任何无界连续函数的充要条件。利用该条件给出了一类变形的插值多项式算子的收敛性定理
本文给出一些新的、易于检验的判别定理，能通过简便的方法来判别一类非对角占优矩阵Ａ的可逆性，给出∥Ａ＾－１∥的上界以及解相应扰动方程组（Ａ＋δＡ）（ｘ＋δｘ）＝ｂ＋δｂ的误差估计，具有较好的实用价值。
对多级适应性休假的Ｍ／Ｇ／１排队系统，若休假时间服从位相型（ＰＨ）分布，我们证明了随机分解中的附加队长和附加延心窘辊离散和连续的ＰＨ随机变量，并给出其不可约ＰＨ表示，是一类不国内外广泛研究地多重
本文给出了线性规划（ＬＰ）的解和其相应的精确罚函数解的等价性，证明是初等的，简明的。
本文构造分裂迭代算法用于计算二重对称破缺转向点，该方法将明显地减少计算的工作量和占用的内存，并且以可调节的速度线性收敛，数值计算成功地说明了分裂迭代算法的有效性。
本文研究了具有非更新寿命和成批加工的ＣＩＭＳ生产线的可靠性问题。首先证明了在系统平稳状态下工作站的广义加工过程是万有马氏过程，然后利用准生灭过程理论，给出了系统稳态时运行指