节点文献

1|B,r_j∈{0,r}|ΣC_j问题的复杂性及近似算法

THE COMPLEXITY OF 1|B,r_j∈{0,r}|ΣC_j AND A 2-APPROXIMATION ALGORITHM

推荐 CAJ下载
PDF下载
不支持迅雷等下载工具，请取消加速工具后下载。

【Author】 DING Ji_huan ①, LIU Li_li ①, JIANG Bao_shan ②, ZHANG Yu_zhong ① (①Institute of Operations Research ,Qufu Normal University ,273165,Qufu; ②No. 3 Career School of Jining,272100,Jinin, Shandong)

【机构】曲阜师范大学运筹学研究所!273165；山东省曲阜市；济宁职业三中!272100；山东省济宁市；

【摘要】讨论了分批排序中工件有两个到达时间 ,以工件完工时间总和为目标函数的批处理问题 ,证明了其NP_完备性 ,并以Brucker等[1] 给出的动态规划算法为基础 ,给出了一性能指标为 2的多项式时间近似算法更多还原

【Abstract】 In this paper, the problem of minimizing the total completion time on a single batch processing machine in the case of two arrival times is discussed . Its NP_Completeness is proved and a polynomial approximation algorithm with performance ratio of 2 is given.更多还原

【关键词】分批排序；动态规划； NP-完备；性能指标；
【Key words】 batch processing； NP_Complete； dynamic programming； performance ratio；

【文献出处】曲阜师范大学学报(自然科学版) ,JOURNAL OF QUFU NORMAL UNIVERSITY(NATURAL SCIENCE) , 编辑部邮箱 ,2000年04期

【分类号】O223
【被引频次】21
【下载频次】56

知网节下载

节点文献中：

本文链接的文献网络图示:

本文的引文网络

节点文献