北京科学与工程计算研究院学术报告之四十九

报告人/Speaker: Minming Li, Department of Computer Science, CityUniversity of Hong Kong


报告题目/Title: Scheduling fully parallel jobs: Algorithms and Mechanisms


时间/Date & Time: May 18, 2018, 14:00—15:00


地点/Venue:北京科学与工程计算研究院M842报告厅


报告摘要/Abstract

We consider the following schedulingproblem. We have m identical machines, where each machine can accomplish oneunit of work at each time unit. We have a set of n jobs, where each job j hassome units (size) of workload, and each unit workload could be executed on anymachine at any time unit. A job is said completed when its whole workload hasbeen executed. The objective is to find a schedule that minimizes the totalweighted completion time. We proved the NP-hardness of the problem when m is afixed constant, and give a PTAS. Then we study the approximation ratio of agreedy algorithm, Largest-Ratio-First algorithm. Any permutation is a possibleoutcome of this algorithm when weight is the same as size for each job j, andfor this special case we show that the approximation ratio depends on theinstance size, i.e. n and m. Finally, when jobs have arbitrary weights, weprove that the upper bound of the approximation ratio is 1+(m-1)/(m+2). We alsoshow a game theoretic framework for the above scheduling model and designgreedy mechanisms which are strategyproof.


报告人简介/About the speaker:

Minming Li is currently an associateprofessor in the Department of Computer Science, City University of Hong Kong.He received his Ph. D. and B.E. degree in the Department of Computer ScienceandTechnology at Tsinghua University in 2006 and 2002 respectively. His researchinterests include algorithmic game theory, combinatorial optimization and algorithmdesign and analysis for scheduling problems.