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

Computer Engineering and Applications ›› 2007, Vol. 43 ›› Issue (3): 175-175.

• 数据库与信息处理 • Previous Articles Next Articles

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

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

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

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

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

[1]	SUN Lu, LIANG Yongquan. Improved Clustering Algorithm Fusing Grid Partition and DBSCAN [J]. Computer Engineering and Applications, 2022, 58(14): 73-79.
[2]	LIU Yi, ZHANG Qigui. Fast Inter-Frame Prediction Algorithm with Partition Level Limitation [J]. Computer Engineering and Applications, 2021, 57(10): 200-203.
[3]	YUAN Shunjie, CHENG Hui, YE Zhencheng, CHENG Peixin. Application of SOM-T2 FLS in Stock Market Forecasting [J]. Computer Engineering and Applications, 2020, 56(7): 130-136.
[4]	JIA Yanfei, DU Yanli, ZHAO Liquan. Fast Convergence for Independent Component Analysis with Reference [J]. Computer Engineering and Applications, 2020, 56(7): 255-259.
[5]	YE Yingshi, WEI Fuyi, CAI Xianzi. Research on Fast Dijkstra Algorithm Based on Parallel Computing [J]. Computer Engineering and Applications, 2020, 56(6): 58-65.
[6]	DENG Youwei1, YANG Yongjian1, PENG Zhiying1, GAN Yi1, MA Jian1, HUANG Boru2. Improved Strategies of Species Explode and Deracinate Algorithm [J]. Computer Engineering and Applications, 2019, 55(3): 55-60.
[7]	CHEN Fei1，2, LIU Jiandong1, HU Huihui1，2, SHANG Kai1，2. Two-dimensional Integer Tent Map Model Design and Security Simulation Analysis [J]. Computer Engineering and Applications, 2019, 55(1): 103-108.
[8]	ZHAO Ying1, GENG Xiulin1, LI Qi1, JIANG Guangqi1, GU Yu1, 2. Study on dynamic image recognition in visual prosthesis [J]. Computer Engineering and Applications, 2018, 54(23): 162-169.
[9]	TANG　Kunjian, RONG Qiang. Attribute reduction algorithm based on weighted condensed tree [J]. Computer Engineering and Applications, 2018, 54(2): 76-81.
[10]	WANG Linna1，2, YANG Xin3, YANG Xibei4. Research on composite decision-theoretic rough modeling and computational method [J]. Computer Engineering and Applications, 2018, 54(19): 122-128.
[11]	LIU Guangda, WANG Wei, SHANG Xiaohu. Study on sleep staging based on fuzzy analysis of EEG [J]. Computer Engineering and Applications, 2017, 53(23): 29-33.
[12]	GAO Feng1, SUN Lili2. Face recognition algorithm based on enhanced granular neural network [J]. Computer Engineering and Applications, 2017, 53(20): 141-147.
[13]	FENG Yanqing, WANG Lunwen. Electromagnetic environment complexity dynamic evaluation method based on constructive cloud neural networks [J]. Computer Engineering and Applications, 2017, 53(16): 211-215.
[14]	WANG Chi, FENG Gui. Fast mode decision algorithm for depth map intra coding in 3D-HEVC [J]. Computer Engineering and Applications, 2017, 53(11): 206-210.
[15]	LIU Huanyu, YU Xiaoguang. Algorithm integrates multi-heuristic rules with particle swarm optimization for spatial resource constrained project scheduling [J]. Computer Engineering and Applications, 2016, 52(22): 226-231.

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

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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics