一类分批排序问题的复杂性分析及近似算法

计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (3): 175-175.

一类分批排序问题的复杂性分析及近似算法

张建伟张保威郭云飞

郑州轻工业学院郑州轻工业学院国家数字交换系统工程技术研究中心

收稿日期:2006-02-10 修回日期:1900-01-01 出版日期:2007-01-21 发布日期:2007-01-21
通讯作者: 张建伟

Complexity Analysis of A Class of Problems on Batch Scheduling and Its Approximated Algorithm

Received:2006-02-10 Revised:1900-01-01 Online:2007-01-21 Published:2007-01-21

摘要/Abstract

摘要： 探讨了分批排序问题，分析了极小化加权总完工时间问题的复杂性，证明了此问题的NP-完备性，并对一类特定问题进行了研究，给出了解决问题的近似算法，证明了其可行性，进而对算法的性能进行了分析，结果表明算法有效的降低了计算复杂度。

关键词: 分批排序, 复杂度, 近似算法, NP完备性, 性能分析

Abstract: The problem of batch scheduling was discussed especially the problem of minimizing the total weighted completed time, namely problems . Besides the complexity of it was analyzed and the NP-completeness was proved. Then this paper focused on a class of special case of the problem and proposed an approximated algorithm to solve the problem. The proof showed that it was feasible and its capability was improved.

Key words: batch scheduling, complexity, approximated algorithm, NP-completeness, capability analysis

张建伟张保威郭云飞. 一类分批排序问题的复杂性分析及近似算法[J]. 计算机工程与应用, 2007, 43(3): 175-175.

[1]	孙璐, 梁永全. 融合网格划分和DBSCAN的改进聚类算法[J]. 计算机工程与应用, 2022, 58(14): 73-79.
[2]	刘艺，张起贵. 划分层次限制的快速帧间预测算法[J]. 计算机工程与应用, 2021, 57(10): 200-203.
[3]	袁顺杰，程辉，叶贞成，程培鑫. SOM-T2 FLS在股市预测中的应用研究[J]. 计算机工程与应用, 2020, 56(7): 130-136.
[4]	贾雁飞，杜艳丽，赵立权. 快速收敛参考独立分量分析方法[J]. 计算机工程与应用, 2020, 56(7): 255-259.
[5]	叶颖诗，魏福义，蔡贤资. 基于并行计算的快速Dijkstra算法研究[J]. 计算机工程与应用, 2020, 56(6): 58-65.
[6]	徐国愚，徐刚，姜涛，胡海涛. 天地一体化网络认证机制性能定量分析方法[J]. 计算机工程与应用, 2020, 56(21): 108-114.
[7]	石会，蔡跃明，杨炜伟，向中武，陈德川. Nakagami-[m]信道的TSR非可信中继网络安全性能分析[J]. 计算机工程与应用, 2020, 56(12): 98-104.
[8]	邓有为1，杨永建1，彭志颖1，甘轶1，马健1，黄柏儒2. 物种生灭算法的改进策略[J]. 计算机工程与应用, 2019, 55(3): 55-60.
[9]	陈飞1，2，刘建东1，胡辉辉1，2，商凯1，2. 二维整数帐篷映射模型设计及安全性仿真分析[J]. 计算机工程与应用, 2019, 55(1): 103-108.
[10]	赵瑛1，耿秀琳1，李琦1，蒋广琪1，谷宇1，2. 视觉假体中动态图像识别研究[J]. 计算机工程与应用, 2018, 54(23): 162-169.
[11]	唐坤剑，容强. 基于加权浓缩树的粗糙集属性约简算法[J]. 计算机工程与应用, 2018, 54(2): 76-81.
[12]	曾维新1，赵翔1，2，冯滔1，唐九阳1，2. 面向领域的命名实体消歧方法改进研究[J]. 计算机工程与应用, 2018, 54(17): 126-134.
[13]	蒋洁琦，杨庚，李鹏. 云环境下面向隐私保护的用户行为分析[J]. 计算机工程与应用, 2018, 54(14): 127-132.
[14]	刘光达，王伟，尚小虎. 基于脑电模糊分析的睡眠分期方法研究[J]. 计算机工程与应用, 2017, 53(23): 29-33.
[15]	崔佳琦，杨剑锋，徐俊，郭成城. CSMA/CA在CSMA/TDMA混合网络中的性能分析[J]. 计算机工程与应用, 2017, 53(20): 83-88.