问题1｜dj=d｜ΣwjTj的一个全多项式近似方案

来源 :数学杂志 | 被引量 : 0次 | 上传用户：howard2000_0

【摘要】

：

本文对具有相同工期的单机最小化加权总误工问题进行了讨论.利用强NP-困难问题1ΣwjTj的一个O（n2）时间的近似算法,把该算法得到的目标值作为问题1｜dj=d｜ΣwjTj的一个上界,对问题1

【作者】

：

张喆李文华

【机构】

：

中原工学院理学院,郑州大学数学系

【出处】

：

数学杂志

【发表日期】

：

2015年4期

【关键词】

：

相同工期加权总误工全多项式近似方案 common due date total weighted tardiness FPTAS

【基金项目】

：

国家自然科学基金资助（11401604,11401605）, 国家天元基金资助（11326191）, 河南省自然科学基金资助（132300410392）

下载到本地 , 更方便阅读

下载此文赞助VIP

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

论文部分内容阅读

本文对具有相同工期的单机最小化加权总误工问题进行了讨论.利用强NP-困难问题1ΣwjTj的一个O（n2）时间的近似算法,把该算法得到的目标值作为问题1｜dj=d｜ΣwjTj的一个上界,对问题1｜dj=d｜ΣwjTj给出全多项式近似方案（FPTAS）.已知问题1｜dj=d｜ΣwjTj是一般意义下的NP-困难问题,并且已经有人对该问题给出了拟多项式时间算法,本文对已有结果进行了扩充.

其他文献

米力农联合多巴酚丁胺与机械通气治疗急性左心衰合并低氧血症及对心功能和血气的影响

目的探究米力农联合多巴酚丁胺与机械通气对急性左心衰合并低氧血症的影响。方法选取2014年2月至2015年6月收治的急性左心衰合并低氧血症80例,根据随机数字表法分为观察组和

期刊

米力农多巴酚丁胺机械通气急性左心衰低氧血症milrinone dobutamine mechanical ventilation acute l

夏季使用空调的三个提醒

依据气候规律,每年从六月中旬开始,我国大部分地区步入炎热的夏季,居室空调和车辆空调的使用频率开始提高.使用空调时,如何在降温去湿的同时,又能达到一种保健效果？以下三点是

期刊

空调夏季气候规律使用频率保健效果

随机比例微分方程θ-方法的T-稳定性

本文研究了一类具有无界延迟的随机微分方程θ-方法的T-稳定性．通过把具有两点分布驱动过程的θ-方法应用到线性方程上，得出了θ-方法T-稳定的条件．最后，一些数值实验说明了这些

期刊

随机比例微分方程T-稳定Θ-方法stochastic pantograph differential equation T-stabilitv θ-m

问题1｜dj=d｜ΣwjTj的一个全多项式近似方案

其他学术论文