Service Level Agreements (SLAs) are currently one of the major research topics in
grid computing. Among many system components for SLA-related grid jobs, the SLA
mapping mechanism has received widespread attention. It is responsible for assigning
sub-jobs of a workflow to a variety of grid resources in a way that meets the user's
deadline and costs as little as possible. With the distinguished workload and
resource characteristics, mapping a heavy communication workflow within an SLA
context gives rise to a complicated combinatorial optimization problem. This paper
presents the application of various metaheuristics and suggests a possible approach
to solving this problem. Performance measurements deliver evaluation results on the
quality and efficiency of each method.
Adam, T.L.
,
Chandy, K.M.
, and
Dickson, J.R.
(1974).
A comparison of list scheduling for parallel processing systems
, Communication of the ACM, 17(12):
685-690.
2.
Berriman, G.B.
,
Good, J.C.
, and
Laity, A.C.
(2003).
Montage: a grid enabled image mosaic service for the National Virtual
Observatory
, ADASS, 13:
134-142.
3.
Brandic, I.
,
Benkner, S.
,
Engelbrecht, G.
, and
Schmidt, R.
(2005).
QoS support for time-critical grid workflow applications
, in Proceedings of e-Science 2005, IEEE CS Press, pp.
108-115.
4.
Brucker, P.
(2004). Scheduling Algorithm, 3rd edition,
Berlin:
Springer-Verlag .
5.
Burchard, L.
,
Hovestadt, M.
,
Kao, O.
,
Keller, A.
, and
Linnert, B.
(2004).
The virtual resource manager: An architecture for SLA-aware resource
management
, in Proceedings of the IEEE CCGrid 2004, IEEE Press, pp.
126-133.
6.
Cao, J.
,
Spooner, D.P.
,
Jarvis, S.A.
, and
Nudd, G.R.
(2005).
Grid load balancing using intelligent agents
, Future Generation Computer Systems Special Issue on Intelligent
Grid Environments: Principles and Applications,
21(1):
135-149.
7.
Chen, J.
and
Yang, Y.
(2007).
Multiple states based temporal consistency for dynamic verification of
fixed-time constraints in grid workflow systems
. Concurrency and Computation: Practice and Experience,
19(7):
965-982.
8.
Chen, J.
and
Yang, Y.
(2006).
Selecting necessary and sufficient checkpoints for dynamic verification of
fixed-time constraints in grid workflow systems
, in Proceedings of the 4th International Conference on Business
Process Management(BPM2006), Vienna, Austria, LNCS
4102, Berlin: Springer, pp.
445-450.
9.
Coffman, E.G.
(1976). Computer and Job-Shop Scheduling Theory,
New York: John Wiley and Sons,
Inc.
10.
Colin, J.Y.
and
Chretienne, P.
(1991).
Scheduling with small computation delays and task duplication
, Operation Research, 39(4):
680-684.
11.
Deelman, E.
,
Blythe, J.
,
Gil, Y.
,
Kesselman, C.
,
Mehta, G.
,
Patil, S.
,
Su, M.
,
Vahi, K.
, and
Livny, M.
(2004).
Pegasus: mapping scientific workflows onto the grid
, in Proceedings of the 2nd European Across Grids
Conference, Nicosia, Cyprus, LNCS 3165, pp.
11-20.
12.
Dorigo, M.
and
Di Caro, G.
(1999). The ant colony optimization meta-heuristic, New Ideas
in Optimization, Maiden-head, UKMcGraw-Hill
, pp. 11-32.
13.
Dowsland, K.A.
(1993). Simulated annealing, in Modern Heuristic
Techniques for Combinatorial Problems, edited by
C. R. Reeves
, New York, NY: John Wiley
& Sons.
14.
Gary, M.R.
and
Johnson, D.S.
(1979). Computers and Intractability: A Guide to the theory
of NP-Completeness, San Francisco, CA:
W. H. Freeman and Co.
15.
Gent, I.P.
,
Macintyre, E.
,
Prosser, P.
,
Smith, B.M.
, and
Walsh, T.
(1996).
An empirical study of dynamic variable ordering heuristics for the
constraint satisfaction problem
, in Proceedings of Principles and Practices of Constraint
Programming - CP96, LNCS 1118, Berlin: Springer, pp.
342-352.
16.
Gerasoulis, A.
and
Yang, T.
(1992).
A comparison of clustering heuristics for scheduling DAGs on
multiprocessors
, J. Parallel and Distributed Computing , 16:
276-291.
17.
Glover, F.
(1989).
Tabu search: Part I
, ORSA Journal on Computing, 1(3):
190-206.
18.
Glover, F.
(1990).
Tabu search: Part II
, ORSA Journal on Computing, 2(1):
4-32.
19.
Hansen, P.
and
Mladenovic, N.
(2001).
Variable neighborhood search: principles and applications
, European Journal of Operational Research, 130:
97-116.
20.
Hou, E.S.H.
,
Ansari, N.
, and
Ren, H.
(1994).
A genetic algorithm for multiprocessor scheduling
, in IEEE Transactions on Parallel and Distributed Systems ,
5(2):
113-120.
21.
Hovestadt, M.
(2003).
Scheduling in HPC resource management systems: queuing vs. planning
, in Proceedings of the 9th Workshop on JSSPP at GGF8,
LNCS, Berlin : Springer, LNCS 2862, pp.
1-20.
22.
Jansen, K.
,
Mastrolilli, M.
, and
Solis-Oba, R.
(2000).
Approximation algorithms for flexible job shop problems
, in Proceedings of Latin American Theoretical Informatics
(LATIN'2000), LNCS 1776, Berlin: Springer, pp.
68-77.
23.
Kacem, I.
,
Hammadi, S.
, and
Borne, P.
(2001).
Approach by localization and multi-objective evolutionary optimization for
flexible job-shop scheduling problems, IEEE Transactions on Systems, Man,
and Cybernetics
. Part C, 32(1): 1-
13.
24.
Kacem, I.
,
Hammadi, S.
, and
Borne, P.
(2002).
Pareto-optimality approach for flexible job-shop scheduling problems:
hybridization of evolutionary algorithms and fuzzy logic
, Journal of Mathematics and Computers in Simulation,
60(3):
245-276.
25.
Kirkpatrick, S.
,
Gelatt, C.
and
Vecchi, M.
(1983).
Optimization by simulated annealing
, Science, 220:
671-680.
26.
Kohler, W.H.
and
Steiglitz, K.
(1974).
Characterization and theoretical comparison of branch-and-bound algorithms
for permutation problems
, Journal of ACM, 21(1):
140-156.
27.
Kruatrachue, B.
and
Lewis, T.G.
(1987). Duplication Scheduling Heuristics (DSH): A New
Precedence Task Scheduler for Parallel Processor Systems,
Oregon State University, Corvallis,
OR.
28.
Kumar, V.
(1992).
Algorithms for constraint-satisfaction problems: a survey
, AI Magazine, 13(1):
32-44.
29.
Kwok, Y.K.
and
Ahmad, I.
(1999).
Static scheduling algorithms for allocating directed task graphs to
multiprocessors
, ACM Computing Surveys (CSUR), 31(4):
406-471.
30.
Lovas, R.
,
Dózsa, G.
,
Kacsuk, P.
,
Podhorszki, N.
, and
Drótos, D.
(2004).
Workflow support for complex grid applications: integrated and portal
solutions
, in Proceedings of 2nd European Across Grids Conference,
Nicosia, Cyprus, LNCS 3165, pp.
129-138.
31.
Ludtke, S.
,
Baldwin, P.
, and
Chiu, W.
(1999).
EMAN: semi-automated software for high-resolution single-particle
reconstruction
, Journal of Structure Biology , 128:
146- 157.
32.
Mastrolilli, M.
and
Gambardella, L.M.
(2000).
Effective neighborhood functions for the flexible job shop problem
, Journal of Scheduling , 3(1):
3-20.
33.
McGough, S.
,
Afzal, A.
,
Darlington, J.
,
Furmento, N.
,
Mayer, A.
, and
Young, L.
(2005).
Making the grid predictable through reservations and performance
modelling
, The Computer Journal, 48(3):
358-368.
34.
Nowicki, E.
and
Smutnicki, C.
(1996).
A fast taboo search algorithm for the job shop problem
, Management Science, 42:
797-813.
35.
Nowicki, E.
and
Smutnicki, C.
(2005).
An advanced taboo search algorithm for the job shop problem
, Journal of Scheduling, 8(2):
145-159.
36.
Pelikan, M.
,
Goldberg, D.
, and
Cantú-Paz, E.
(1999).
BOA: the Bayesian optimization algorithm
, in Proceedings of the Genetic and Evolutionary Computation
Conference GECCO-99, Orlando, FL, Morgan Kaufmann,
pp. 525- 532.
37.
Pelikan, M.
,
Goldberg, D.
, and
Lobo, F.
(1999).
A survey of optimization by building and using probabilistic models
, Tech. Rep. No. 99018,
IlliGAL, University of
Illinois .
38.
Quan, D.M.
(2007).
Error recovery mechanism for grid-based workflow within SLA context
, to appear in International Journal of High Performance Computing
and Networking (IJHPCN), 5(1/2):
110-121.
39.
Quan, D.M.
and
Hsu, D.F.
(2006).
Network-based resource allocation for Grid Computing within an SLA
context
, in Proceedings of the 5th International Conference on Grid and
Cooperative Computing(GCC 2006), IEEE Press, IEEE CS Press, pp.
274-280.
40.
Quan, D.M.
and
Kao, O.
(2005a).
On architecture for an SLA-aware job flows in grid environments
, Journal of Interconnection Networks,
6(3):
245-264.
41.
Quan, D.M.
and
Kao, O.
(2005b).
SLA negotiation protocol for grid-based workflows
, in Proceedings of the International Conference on High
Performance Computing and Communications (HPPC-05), LNCS 3726,
Berlin: Springer, pp.
505-510.
42.
Quan, D.M.
and
Kao, O.
(2005c).
On architecture for an SLA-aware job flows in grid environments
, in Proceedings of the 19th IEEE International Conference on
Advanced Information Networking and Applications (AINA 2005), IEEE
Press, pp. 287-292.
43.
Quan, D.M.
and
Kao, O.
(2005d).
Mapping grid job flows to grid resources within SLA context
, in Proceedings of the European Grid Conference(EGC
2005), LNCS 3470, Berlin: Springer, pp.
1107-1116.
44.
Rewini, H.E.
and
Lewis, T.G.
(1990).
Scheduling parallel program tasks onto arbitrary target machines
, Journal of Parallel and Distributed Computing ,
9(2):
138-153.
45.
Sadeh, N.
and
Fox, M.S.
(1996).
Variable and value ordering heuristics for the job shop constraint
satisfaction problem
, Artificial Intelligence , 86:
1-41.
46.
Sahai, A.
(2002). Automated SLA monitoring for web services, DSOM 2002,
LNCS, Berlin:
Springer-Verlag , pp.
28-41.
47.
Sarkar, V.
(1989). Partitioning and Scheduling Parallel Programs for
Multiprocessors, Cambridge, MA:
MIT Press.
48.
Shahid, A.
,
Muhammed, S.T.
, and
Sadiq, M.
(1994).
GSA: scheduling and allocation using genetic algorithm
, in Proceedings of the Conference on European Design
Automation, September, IEEE CS Press, pp. 84-89.
49.
Sih, G.C.
and
Lee, E.A.
(1993).
Declustering: a new multiprocessor scheduling technique
, in IEEE Transactions on Parallel and Distributed Systems,
4(6):
625-637.
50.
Spooner, D.P.
,
Jarvis, S.A.
,
Cao, J.
,
Saini, S.
, and
Nudd, G.R.
(2003).
Local grid scheduling techniques using performance prediction
, in IEEE Proceedings - Computers and Digital Techniques ,
150(2):
87-96.
51.
Stützle, T.
(1999a). Iterated local search for the quadratic assignment
problem, Tech. Rep. Aida-99-03, FG Intellektik, TU Darmstadt.
52.
Stützle, T.
(1999b). Local Search Algorithms for Combinatorial
Problems-Analysis, Algorithms and New Applications, DISKI-Dissertationen zur
Künstliken Intelligenz . infix, Sankt Augustin,
Germany.
53.
Voudouris, C.
(1997). Guided Local Search for Combinatorial Optimization
Problems, PhD dissertation,
Department of Computer Science, University of Essex
.
54.
Voudouris, C.
and
Tsang, E.
(1999).
Guided local search
, European Journal of Operation Research,
113(2): 469-
499.
55.
Wolski, R.
(2003).
Experiences with predicting resource performance on-line in computational
grid settings
, ACM SIGMETRICS Performance Evaluation Review,
30(4):
41-49.
56.
Zeng, L.
,
Benatallah, B.
,
Ngu, A.
,
Dumas, M.
,
Kalagnanam, J.
, and
Chang, H.
(2004).
QoS-aware middleware for web services composition
, in IEEE Transactions on Software Engineering,
30(5):
311-327.
