Resource Scheduling with Supply Constraint and Linear Cost

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationCombinatorial Optimization and Applications
Subtitle of host publicationProceedings
EditorsGuohui Lin
PublisherSpringer-Verlag Berlin Heidelberg
Pages212-222
ISBN (Electronic)9783642317705
ISBN (Print)9783642317699
Publication statusPublished - Aug 2012

Publication series

NameLecture Notes in Computer Science
Volume7402
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Title6th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2012)
PlaceCanada
CityBanff, AB
Period5 - 9 August 2012

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.

Research Area(s)

  • Algorithms, Machine scheduling, Parallel tasks, Supply allocation

Citation Format(s)

Resource Scheduling with Supply Constraint and Linear Cost. / Zhang, Qiang; Wu, Weiwei; Li, Minming.

Combinatorial Optimization and Applications: Proceedings. ed. / Guohui Lin. Springer-Verlag Berlin Heidelberg, 2012. p. 212-222 (Lecture Notes in Computer Science ; Vol. 7402).

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)