Computer Science

Computer Science ›› 2021, Vol. 48 ›› Issue (4): 37-42.doi: 10.11896/jsjkx.200600064

• Computer Science Theory • Previous Articles     Next Articles

Approximate Ratios Analysis of New Algorithm for Classical Parallel Scheduling

GAO Ji-ji, YUE Xue-rong, CHEN Zhi-bin   

  1. School of Science and Technology,Kunming University of Science and Technology,Kunming 650000,China
  • Received:2020-06-24 Revised:2020-08-26 Online:2021-04-15 Published:2021-04-09
  • About author:GAO Ji-ji,born in 1995,postgraduate.His main research interests include combinatorial optimization and so on.(965789294@qq.com)
    CHEN Zhi-bin,born in 1979,Ph.D,associate professor.His main research interests include combinatorial optimization,graph theory,approximation algorithms and operations research.
  • Supported by:
    National Natural Science Foundation of China(11761042,11461081).

PDF (PC)

628

Abstract: Given m parallel machines(identical machines) and n jobs,we need to find a distribution scheme so that the overall completion time is as short as possible after these n jobs are allocated to m machines.This NP-hard problem is called classical scheduling problem.If the processing time of each job meets certain conditions,it is expected to get the optimal allocation scheme effectively.Yue et al.consider a new algorithm for the classical scheduling problem that the processing time satisfies the divisional property,which can always obtain the optimal distribution in this special case.This algorithm can obtain the optimal distribution in polynomial time and is an approximate algorithm for the general classical scheduling problem.On this basis,the approximate ratio of the algorithm in general problems is considered.There are two versions of the proposed algorithm,and the approximate ratios of 3／2 and 2－1/2q(q∈Z+) are obtained respectively.The tight examples provided in this paper show that our analysis of two versions of the algorithm is optimal.

Key words: Approximation algorithm, Classic scheduling, One dimensional packing problem, Polynomial time algorithm, Tight example

CLC Number: 

  • TP301.6
[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] JIANG Xin-wen. Polynomial Time Algorithm for Hamilton Circuit Problem [J]. Computer Science, 2020, 47(7): 8-20.
[2] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem [J]. Computer Science, 2018, 45(4): 83-88.
[3] LUO Wei-dong, WANG Jian-xin and FENG Qi-long. Survey of Cycle Packing Problem [J]. Computer Science, 2017, 44(1): 1-6.
[4] LIU Yun-long. Research on Complexity and Approximation Algorithm for Counting 3-Set Packings of Size k [J]. Computer Science, 2016, 43(9): 23-26.
[5] LIU Yun-long and CUI Meng-tian. Advances in Fixed-parameter Tractable Approximation Algorithms for NP-hard Problems [J]. Computer Science, 2016, 43(8): 7-12.
[6] JIA Jian-wei and CHEN Ling. Set Similarity Approximation Algorithm Based on Parity of Data Sketch [J]. Computer Science, 2016, 43(6): 254-256.
[7] LI Wei-dong LI Jian-ping. Cardinality-constrained Load Balancing Problem [J]. Computer Science, 2015, 42(7): 74-77.
[8] JIANG Shun-liang, XU Qing-yong, HUANG Wei, YE Fa-mao and XU Shao-ping. Randomized Power Tree Method for Shortest Addition Chains [J]. Computer Science, 2015, 42(3): 228-232.
[9] HUANG Qu-zhi and ZHANG Jun-chao. Approximating Triangle Counting Based on Sampling in Complex Networks [J]. Computer Science, 2015, 42(11): 188-190.
[10] . Tree Decomposition and its Applications in Algorithms:Survey [J]. Computer Science, 2012, 39(3): 14-18.
[11] . Bounded Clustering on Bounded Tree-width Graphs [J]. Computer Science, 2011, 38(11): 241-244.
[12] ZHENG Ying,WANG Jian-xin,CHEN Jian-er. Survey of Steiner Tree Problem [J]. Computer Science, 2011, 38(10): 16-22.
[13] WANG Jian-xin,Jiang Guo-hong,LI Wen-jun,CHEN Jian-er. Algorithms for Feedback Set Problems:A Survey [J]. Computer Science, 2011, 38(1): 40-47.
[14] FENG Wang-sen,ZHANG Bei,CHEN Ping,CUI Jian. Transport Sub-network Selection:Approaching with Bounded Maximum Spanning Sub-graphs [J]. Computer Science, 2010, 37(3): 42-45.
[15] WANG Jian-xin,CHEN Bei-wei,CHEN Jian-er. Algorithms for Dominating Problems:A Survey [J]. Computer Science, 2010, 37(2): 7-11.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.