Resource Scheduling with Supply Constraint and Linear Cost

Qiang Zhang; Weiwei Wu; Minming Li

doi:10.1007/978-3-642-31770-5_19

Resource Scheduling with Supply Constraint and Linear Cost

Qiang Zhang
, Weiwei Wu
, Minming Li

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

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.

Original language	English
Title of host publication	Combinatorial Optimization and Applications
Subtitle of host publication	Proceedings
Editors	Guohui Lin
Publisher	Springer Berlin Heidelberg
Pages	212-222
ISBN (Electronic)	9783642317705
ISBN (Print)	9783642317699
DOIs	https://doi.org/10.1007/978-3-642-31770-5_19
Publication status	Published - Aug 2012
Event	6th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2012) - Banff, AB, Canada Duration: 5 Aug 2012 → 9 Aug 2012

Publication series

Name	Lecture Notes in Computer Science
Volume	7402
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	6th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2012)
Abbreviated title	COCOA 2012
Place	Canada
City	Banff, AB
Period	5/08/12 → 9/08/12

Research Keywords

Algorithms
Machine scheduling
Parallel tasks
Supply allocation

Access Output

10.1007/978-3-642-31770-5_19

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{f409ed25b7cb433a926feae743c8f04e,

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 si of resources. Each resource can only be assigned to one job. The objective is to find a schedule that minimizes ∑ wici, where wi is the weight/importance of job Ji and ci is the time that job Ji 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(nd+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",

month = aug,

doi = "10.1007/978-3-642-31770-5\_19",

language = "English",

isbn = "9783642317699",

series = "Lecture Notes in Computer Science ",

publisher = "Springer Berlin Heidelberg",

pages = "212--222",

editor = "Guohui Lin",

booktitle = "Combinatorial Optimization and Applications",

note = "6th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2012), COCOA 2012 ; Conference date: 05-08-2012 Through 09-08-2012",

}

Zhang, Q, Wu, W & Li, M 2012, Resource Scheduling with Supply Constraint and Linear Cost. in G Lin (ed.), Combinatorial Optimization and Applications: Proceedings. Lecture Notes in Computer Science , vol. 7402, Springer Berlin Heidelberg, pp. 212-222, 6th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2012), Banff, AB, Canada, 5/08/12. https://doi.org/10.1007/978-3-642-31770-5_19

Resource Scheduling with Supply Constraint and Linear Cost. / Zhang, Qiang; Wu, Weiwei; Li, Minming.
Combinatorial Optimization and Applications: Proceedings. ed. / Guohui Lin. Springer Berlin Heidelberg, 2012. p. 212-222 (Lecture Notes in Computer Science ; Vol. 7402).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Resource Scheduling with Supply Constraint and Linear Cost

AU - Zhang, Qiang

AU - Wu, Weiwei

AU - Li, Minming

PY - 2012/8

Y1 - 2012/8

N2 - 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 si of resources. Each resource can only be assigned to one job. The objective is to find a schedule that minimizes ∑ wici, where wi is the weight/importance of job Ji and ci is the time that job Ji 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(nd+1) to solve this problem when the number of different resources requirements that are not multiples of m is at most d.

AB - 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 si of resources. Each resource can only be assigned to one job. The objective is to find a schedule that minimizes ∑ wici, where wi is the weight/importance of job Ji and ci is the time that job Ji 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(nd+1) to solve this problem when the number of different resources requirements that are not multiples of m is at most d.

KW - Algorithms

KW - Machine scheduling

KW - Parallel tasks

KW - Supply allocation

UR - https://www.scopus.com/pages/publications/84864967540

UR - https://www.scopus.com/pages/publications/84864967540#tab=impact

U2 - 10.1007/978-3-642-31770-5_19

DO - 10.1007/978-3-642-31770-5_19

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9783642317699

T3 - Lecture Notes in Computer Science

SP - 212

EP - 222

BT - Combinatorial Optimization and Applications

A2 - Lin, Guohui

PB - Springer Berlin Heidelberg

T2 - 6th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2012)

Y2 - 5 August 2012 through 9 August 2012

ER -

Resource Scheduling with Supply Constraint and Linear Cost

Abstract

Publication series

Conference

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this