报告人/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
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.