两台机器及时完工工件数最大化问题的近似算法

来源 :高校应用数学学报：A辑 | 被引量 : 0次 | 上传用户：FUHENGBIN

【摘要】

：

平行机排序问题Pm∥∑uj当m≥2时是一个NP-难的问题.本文利用求解1∥∑uj的Moore算法构造了与P2∥∑uj等价的P2∥n-∑uj问题的一个多项式时间近似算法,并证明了该算法的绝对

【作者】

：

沈灏杨启帆

【机构】

：

浙江大学数学系

【出处】

：

高校应用数学学报：A辑

【发表日期】

：

2003年2期

【关键词】

：

平行机排序 NP—难问题近似算法绝对性能比渐近性能比 parallel machine sequencing NP|hard approxim

【基金项目】

：

国家自然科学基金，电子工业部电子科研院军事预研项目

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

平行机排序问题Pm∥∑uj当m≥2时是一个NP-难的问题.本文利用求解1∥∑uj的Moore算法构造了与P2∥∑uj等价的P2∥n-∑uj问题的一个多项式时间近似算法,并证明了该算法的绝对性能比为3/4.此外还研究了机器带有准备时间的问题P2,ri∥n-∑uj,并证明了在这种情况下算法的渐近性能比为2/3.

其他文献

到四元Grassmann流形的调和映射

利用奇异Darboux变换建立了四元Grassmann uniton的因子分解并给出了其极小uniton数的上界估计.

期刊

调和映射DARBOUX变换四元Grassmann扩张解极小uniton数Harmonic Map Darboux Transformation Mi

集值优化问题的Benson真有效解的广义最优性条件

引进了关于集值映射的(1，α)-阶Clarke导数，(1，α)-阶邻接导数，(1，α)-阶伴随导数概念；应用它们导出了具Slater约束规格的集值优化问题的Benson真有效解的广义导数型Kuhn-Tucker最

期刊

集值映射切锥Benson真有效广义Kuhn-Tucker条件set-valued maptangent coneBenson proper effi

一类非线性方程激波位置的转移

讨论一类非线性方程的激波位置，得出了在一定的情况下，当边界条件作微小的变化时，激波的位置将作较大的偏移，甚至由内层转到边界层。

期刊

非线性方程激波内层边界层nonlinear equation shockinternal layerboundary layer

颊肌补牙树脂瓣鼻腔植入治疗萎缩性鼻炎

目的：探讨一种治疗萎缩性鼻炎的手术方法，观察手术近期及远期效果。方法：慢性萎缩性鼻炎病例36例（72例），采用带蒂颊肌补牙树脂瓣鼻腔粘骨膜下植入，随访3个月-4年，根据术前术后症状、

期刊

颊肌补牙树脂瓣治疗萎缩性鼻炎

一类时变动力系统的高余维分岔及其控制

研究了一类时变动力系统的高余维分岔及其控制问题.首先利用新方法对时变分岔方程的两个方向的分岔转迁和跃迁现象进行分析，分别通过慢变解的线性化近似和量级平衡估计分岔转

期刊

时变动力系统分岔反馈控制脉冲振动HOPF分岔动态滞后环分岔转迁值Time-dependent Dynamical SystemBifurcati

基于一类新的胞腔排除遗传算法求解迭代函数系逆问题

提出求解迭代函数系(IFS)逆问题的一类有效遗传算法.该算法基于新发展的可拼接/可分解编码,并结合使用胞腔排除技巧.对于典型图像的应用表明:该方法可有效应用于基于矩匹配表

期刊

迭代函数系逆问题目标测度矩匹配编码胞腔排除遗传算法图像处理非线性优化问题Inverse Problem of IFS Target Measur

云南高校体育专业2006届毕业生求职就业心理的调查分析

本文以云南高校体育院系体育专业2006届毕业生为调查对象，对毕业生求职心理状况进行调查分析，探讨大学生求职就业心理的规律，为提高学生心理素质并对学生进行求职就业指导提供理

期刊

体育专业求职就业心理sports specialty employment-seeking employment psychology

具有一定消失矩的优化线性相位滤波器

利用消失矩特性和编码误差最小，给出了一类有限长线性相位的双正交小波滤波器组BNVF的构造方法，BNVF的综合低通和分解高通的系数为二进分数，将其用于图像的分解与重构时，可避免一

期刊

图像压缩双正交小波最优化小波变换变换编码biorthogonal wavelet optimization wavelet transform

两台机器及时完工工件数最大化问题的近似算法

其他学术论文