@inproceedings{ae447d3daf1a4752a7fe00a2534a36af,
title = "Resource scheduling with supply constraint and linear cost",
abstract = "We consider the following resource scheduling problem to minimize the total weighted completion time. There are m resources available at each time unit, and n jobs, each requiring an arbitrary number s i of resources. Each resource can only be assigned to one job. The objective is to find a schedule that minimizes ∑ w ic i, where w i is the weight/importance of job J i and c i is the time that job J i receives all resources it requires. We show this problem is NP-hard when m is the input of the problem. We then give a simple greedy algorithm with 2-approximation ratio. Finally, we present a polynomial time algorithm with complexity O(n d+1) to solve this problem when the number of different resources requirements that are not multiples of m is at most d.",
keywords = "Algorithms, Machine scheduling, Parallel tasks, Supply allocation",
author = "Qiang Zhang and Weiwei Wu and Minming Li",
year = "2012",
doi = "10.1007/978-3-642-31770-5\_19",
language = "英语",
isbn = "9783642317699",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "212--222",
booktitle = "Combinatorial Optimization and Applications - 6th International Conference, COCOA 2012, Proceedings",
note = "6th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2012 ; Conference date: 05-08-2012 Through 09-08-2012",
}