计算机科学 ›› 2021, Vol. 48 ›› Issue (4): 37-42.doi: 10.11896/jsjkx.200600064
高吉吉, 岳雪蓉, 陈智斌
GAO Ji-ji, YUE Xue-rong, CHEN Zhi-bin
摘要： 给定m台平行机(同型机),n个工件,寻找一种分配方案,使得把这n个工件分配到m台机器后,整体完工时间尽可能短,这个NP-难问题被称为经典排序问题。如果每个工件的加工时间满足一定的条件,则有望能在多项式时间内有效地得到最优的分配方案。Yue等对加工时间满足整除性质的经典排序问题考虑了一种新的算法,该算法总是能得到这种特殊情况的最优分配。该算法在多项式时间内能够得到最优分配,是对于一般的经典排序问题的近似算法。文章在此基础上,考虑该新算法在一般问题上的近似比。文中考虑了这个新算法的两种版本,分别得到了3／2和2－1/2q(q∈Z+)的近似比。紧例子表明,文中对算法的两个版本的分析都是最优的。
中图分类号:
| [1]GRAHAM R L,LAWLER E L,LENSTRA J K,et al.Optimization and Approximation in Determini-stic Sequencing and Sche-duling:A Survey[J].Annals of Discrete Mathematics,1979,5(1):287-326. [2]GRAHAM R L.Bounds for Certain Multiprocessing Anomalies[J].Bell System Technical Journal,1966,45(9):1563-1581. [3]GRAHAM R.L.Bounds on multiprocessing time anomalies[J].SIAM Journal on Applied Mathematics,1969,17(2):416-429. [4]DEUERMEYER B L,FRIESEN D K,LANGSTON M A.Scheduling to Maximize the Minimum Processor Finish Time in a Multi-processor System[J].Siam Journal on Algebraic Discrete Methods,1982,3(2):190-196. [5]KAO T Y,ELSAYED E A.Performance of the LPT algorithm in multiprocessor scheduleing[J].Computers & Operations Research,1990,17(4):365-373. [6]CSIRIK J,KELLERER H,WOEGINGER G.The exact LPT-bound for maximizing the minimum completion time[J].Operations Research Letters,1992,11(5):281-287. [7]WOEGINGER G J.A polynomial-time approximation schemefor maximizing the minimum machine completion time[J].Operations Research Letters,1997,20(4):149-154. [8]COFFMAN E G,GAREY M R,JOHNSON D S.An Application of Bin-Packing to Multiprocessor Scheduling[J].Siam Journal on Computing,19787(1):1-17. [9]LANGSTON M A.Processor scheduling with improved heuristic algorithms[M].Texas A&M University,1981. [10]FRIESEN D K.Tighter Bounds for the Multifit ProcessorScheduling Algorithm[J].Siam Journal on Computing,1984,13(1):170-181. [11]YUE M.On the exact upper bound for the multifit processor scheduling algorithm[J].Annals of Operations Research,1990,24(1):233-259. [12]SAHN I,SARTAJ K.Algorithms for Scheduling Independent Tasks[J].Journal of the ACM,1976,23(1):116-127. [13] HOCHBAUM D S,SHMOYS D B.Using dual approximation algorithms for scheduling problems theoretical and practical results[J].Journal of the ACM(JACM),1987,34(1):144-162. [14]VEL H V D,SHIJIE S.A modification of Hochbaum andShmoys’ algorithm for scheduling problems[J].BIT Numerical Mathematics,1991,31(1):50-52. [15]JANSEN K.An EPTAS for scheduling jobs on uniform processors:using an MILP relaxation with a constant number of integral variables[J].SIAM Journal on Discrete Mathematics,2010,24:457-485. [16]KLEIN K M,JANSEN K,VERSCHAE J.Closing the gap for makespan scheduling via sparsification techniques[C]//Procee-dings of the 43rd International Colloquium on Automata,Languages,and Programming.2016,55(72):1-13. [17]CHEN L,JANSEN K,ZHANG G.On the optimality of exact and approximation algorithms for scheduling problems[J].Journal of Computer and System Sciences,2018,96(2):89-99. [18]IMPAGLIAZZO R,PATURI R,ZANE F.Which problems have strongly exponential complexity?[J].Journal of Computer and System Science,2001,63:512-530. [19]YUE X R,GAO J J,CHEN Z B.A polynomial time algorithm for scheduling on processing time constraints[C]//ACM International Conference Proceeding Series,2019 the 9th Internatio-nal Conference on Communication and Network Security.2019:109-113. [20]近似算法[M].郭效江,方志奇,农庆琴,译.北京:北京高等教育出版社,2010:74-75. |
| [1] | 姜新文. 哈密顿图判定问题的多项式时间算法 Polynomial Time Algorithm for Hamilton Circuit Problem 计算机科学, 2020, 47(7): 8-20. https://doi.org/10.11896/jsjkx.191200176 |
| [2] | 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究 Approximation Algorithm for Weighted Mixed Domination Problem 计算机科学, 2018, 45(4): 83-88. https://doi.org/10.11896/j.issn.1002-137X.2018.04.012 |
| [3] | 黄海,李松斌. 求解2-D Strip Packing问题的u-分组优化算法 u-Block Optimization Algorithm for 2-D Strip Packing Problem 计算机科学, 2017, 44(5): 290-293. https://doi.org/10.11896/j.issn.1002-137X.2017.05.053 |
| [4] | 孙焘,朱晓明. 基于格代数的最长公共子序列近似求解 Computing Longest Common Subsequences Approximately Based on Lattice 计算机科学, 2017, 44(2): 270-274. https://doi.org/10.11896/j.issn.1002-137X.2017.02.045 |
| [5] | 罗卫东,王建新,冯启龙. 最大圈分解问题的研究进展 Survey of Cycle Packing Problem 计算机科学, 2017, 44(1): 1-6. https://doi.org/10.11896/j.issn.1002-137X.2017.01.001 |
| [6] | 刘运龙. 3-Set Packing参数化计数问题的复杂性及近似算法 Research on Complexity and Approximation Algorithm for Counting 3-Set Packings of Size k 计算机科学, 2016, 43(9): 23-26. https://doi.org/10.11896/j.issn.1002-137X.2016.09.004 |
| [7] | 刘运龙,崔梦天. 难解问题的固定参数近似算法研究进展 Advances in Fixed-parameter Tractable Approximation Algorithms for NP-hard Problems 计算机科学, 2016, 43(8): 7-12. https://doi.org/10.11896/j.issn.1002-137X.2016.08.002 |
| [8] | 贾建伟,陈崚. 基于数据摘要奇偶性的集合相似性近似算法 Set Similarity Approximation Algorithm Based on Parity of Data Sketch 计算机科学, 2016, 43(6): 254-256. https://doi.org/10.11896/j.issn.1002-137X.2016.06.050 |
| [9] | 李伟东 李建平. 具有数目约束的负载均衡问题 Cardinality-constrained Load Balancing Problem 计算机科学, 2015, 42(7): 74-77. https://doi.org/10.11896/j.issn.1002-137X.2015.07.016 |
| [10] | 江顺亮,许庆勇,黄 伟,叶发茂,徐少平. 最短加法链的随机幂树方法 Randomized Power Tree Method for Shortest Addition Chains 计算机科学, 2015, 42(3): 228-232. https://doi.org/10.11896/j.issn.1002-137X.2015.03.047 |
| [11] | 黄取治,张军朝. 复杂网络中基于采样的近似三角计数方法研究 Approximating Triangle Counting Based on Sampling in Complex Networks 计算机科学, 2015, 42(11): 188-190. https://doi.org/10.11896/j.issn.1002-137X.2015.11.039 |
| [12] | 高文宇，李绍华. 图的树分解及其算法应用研究进展 Tree Decomposition and its Applications in Algorithms:Survey 计算机科学, 2012, 39(3): 14-18. |
| [13] | 李曙光，周彤. 限制树宽图上的有界聚类 Bounded Clustering on Bounded Tree-width Graphs 计算机科学, 2011, 38(11): 241-244. |
| [14] | 郑莹 王建新 陈建二. Steiner Tree问题的研究进展 Survey of Steiner Tree Problem 计算机科学, 2011, 38(10): 16-22. |
| [15] | 王建新,江国红,李文军,陈建二. 反馈集问题的研究进展 Algorithms for Feedback Set Problems:A Survey 计算机科学, 2011, 38(1): 40-47. |
|
||
首页