Lower bounds for constrained task allocation problem in distributed computing environment

Author

Pendharkar, P.C.

Author_Institution

Inf. Syst., Penn State Harrisburg, Harrisburg, PA, USA

fYear

2012

fDate

April 29 2012-May 2 2012

Firstpage

1

Lastpage

4

Abstract

In this paper, we propose three lower bounds to the constrained task allocation problem (CTAP). These three lower bounds are: a heuristic lower bound (HLB), a linear programming relaxation (LPR) lower bound and a lagrangean relaxation with subgradient optimization (LRSO) based lower bound. We empirically compare the performance of these three bounds under different task executing times. Our experiments with real-world CTAPs indicate that the LPR provides efficient and tight lower bounds for the CTAP.

Keywords

distributed processing; gradient methods; linear programming; CTAP; HLB; LPR; LRSO; constrained task allocation problem; distributed computing environment; heuristic lower bound; lagrangean relaxation with subgradient optimization based lower bound; linear programming relaxation; Distributed computing; Linear programming; Optimization; Program processors; Resource management; Throughput; Vectors; Distributed Computing; Lagrangean Relaxation; Lower Bounds; Mathematical Programming; Task Allocation;

fLanguage

English

Publisher

ieee

Conference_Titel

Electrical & Computer Engineering (CCECE), 2012 25th IEEE Canadian Conference on

Conference_Location

Montreal, QC

ISSN

0840-7789

Print_ISBN

978-1-4673-1431-2

Electronic_ISBN

0840-7789

Type

conf

DOI

10.1109/CCECE.2012.6335052

Filename

6335052