无限批量调度中最小化加权完工时间和问题的一个线性时间近似方案

来源 :运筹学学报 | 被引量 : 0次 | 上传用户：akljdhnaliuhda

【摘要】

：

本文考虑n个工件的无限批量机器调度问题.一台机器可以同时加工B≥n个工件.每个工件具有一个正权因子、一个释放时间和一个加工时间.一个批次的加工时间是该批次所包含所有工

【作者】

：

李曙光李国君赵浩

【机构】

：

烟台大学数学与信息科学系,中国科学院软件研究所,山东大学计算机科学与技术学院

【出处】

：

运筹学学报

【发表日期】

：

2004年4期

【关键词】

：

完工时间近似线性加工时间加权调度问题多项式时间批次最小化批量 OR approximation algorithms unbounded

【基金项目】

：

This work was supported by the fund from NSFC under fund

下载到本地 , 更方便阅读

下载此文赞助VIP

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

论文部分内容阅读

本文考虑n个工件的无限批量机器调度问题.一台机器可以同时加工B≥n个工件.每个工件具有一个正权因子、一个释放时间和一个加工时间.一个批次的加工时间是该批次所包含所有工件的加工时间的最大者.在同一批次中加工的工件有相同的完工时间,即它们的共同开始时间加上该批次的加工时间.对于最小化加权完工时间和问题,本文给出了第一个多项式时间近似方案(PTAS).对任意给定精度,该算法的运行时间为线性的.

其他文献

对等式约束非线性规划问题的Hestenes—Powell增广拉格朗日函数的进一步研究

本文对用无约束极小化方法求解等式约束非线性规划问题的Hestenes-Powell增广拉格朗日函数作了进一步研究．在适当的条件下，我们建立了Hestenes-Powell增广拉格朗日函数在原问题

期刊

运筹学最优化非线性规划增广拉格朗日函数Hestenes—Powell增广拉格朗日函数Operation research optimization

PCEA防治胸科患者术后疼痛的观察与护理

术后疼痛是机体对疾病和手术所致组织损伤的一种生理反应,不利于患者术后康复.由于我们为胸科术后患者用了硬膜外自控镇痛(PCEA),临床效果满意,现报告如下.

期刊

PCEA术后疼痛护理胸部手术临床观察

推迟期刊装订的时间及方法探讨

本文针对由于期刊装订而影响读者利用的问题，提出了延缓装订的设想，并在装订时间的选择和装订方法的改进上，提出了自己的一些看法。

期刊