首页 | 本学科首页   官方微博 | 高级检索  
     


A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time
Affiliation:1. Key Laboratory of Symbol Computation and Knowledge Engineering of Ministry of Education, and College of Computer Science and Technology, Jilin University, Changchun 130012, China;2. Cancer Systems Biology Center, China-Japan Union Hospital, Jilin University, Changchun 130033, China;3. Advanced Institute, Infervision, Beijing 100000, China;4. School of Mechatronics Engineering, Nanchang University, Nanchang 330031, China;5. School of Artificial Intelligence, Jilin University, Changchun, 130012, China;6. Sanford Research, Sioux Falls, SD 57104, USA;7. Department of Biochemistry and Molecular Biology and Institute of Bioinformatics, University of Georgia, Athens, GA 30602, USA;1. Lawrence Livermore National Laboratory, United States;2. University of Utah, United States;3. University of Pittsburgh, United States
Abstract:The identical parallel machine scheduling problem with the objective of minimizing total weighted completion time is considered in the online setting where jobs arrive over time. An online algorithm is proposed and is proven to be (2.5–1/2m)-competitive based on the idea of instances reduction. Further computational experiments show the superiority over other algorithms in the average performance.
Keywords:Online scheduling  Parallel machine  Competitive ratio  Total weighted completion time  Instance reduction
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号