×

Deadline division-based heuristic for cost optimization in workflow scheduling. (English) Zbl 1176.90253

Summary: Cost optimization for workflow applications described by Directed Acyclic Graph (DAG) with deadline constraints is a fundamental and intractable problem on Grids. In this paper, an effective and efficient heuristic called DET (Deadline Early Tree) is proposed. An early feasible schedule for a workflow application is defined as an Early Tree. According to the Early Tree, all tasks are grouped and the Critical Path is given. For critical activities, the optimal cost solution under the deadline constraint can be obtained by a dynamic programming strategy, and the whole deadline is segmented into time windows according to the slack time float. For non-critical activities, an iterative procedure is proposed to maximize time windows while maintaining the precedence constraints among activities. In terms of the time window allocations, a local optimization method is developed to minimize execution costs. The two local cost optimization methods can lead to a global near-optimal solution. Experimental results show that DET outperforms two other recent leveling algorithms. Moreover, the deadline division strategy adopted by DET can be applied to all feasible deadlines.

MSC:

90B35 Deterministic scheduling theory in operations research
90B36 Stochastic scheduling theory in operations research
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abramson, D.; Buyya, R.; Giddy, J., A computational economy for Grid computing and its implementation in the Nimrod-G resource broker, Future Generation Computing Systems (FGCS), 18, 8, 1061-1074 (2002) · Zbl 1042.68514
[2] Akkan, C.; Drexl, A.; Kimms, A., Network decomposition-based benchmark results for the discrete time-cost tradeoff problem, European Journal of Operational Research, 165, 2, 339-358 (2005) · Zbl 1066.90021
[3] Al-Ali, R.; Hafid, A.; Rana, O.; Walker, D., An approach for quality of service adaptation in service-oriented Grids, Concurrency and Computation: Practice and Experience, 16, 5, 401-412 (2004)
[4] Al-Ali, R.; Rana, O.; Walker, D.; Jha, S.; Sohail, S., G-QoSM: Grid service discovery using QoS properties, Computing and Informatics Journal, Special Issue Grid Computing, 21, 4, 363-382 (2002) · Zbl 1102.68396
[5] J. Blythe et al., Task scheduling strategies for workflow-based applications in Grids, in: Proceedings of IEEE International Symposium on Cluster Computing and the Grid, Cardiff, Wales, United Kingdom, 2005, pp. 759-767.; J. Blythe et al., Task scheduling strategies for workflow-based applications in Grids, in: Proceedings of IEEE International Symposium on Cluster Computing and the Grid, Cardiff, Wales, United Kingdom, 2005, pp. 759-767.
[6] Buyya, R.; Abramson, D.; Giddy, J.; Stockinger, H., Economic models for resource management and scheduling in Grid computing, Concurrency and Computation: Practice and Experience Journal (Special Issue on Grid Computing Environments), 14, 13-15, 1507-1542 (2002) · Zbl 1007.68612
[7] R. Buyya, J. Giddy, D. Abramson, A case for economy Grid architecture for service-oriented Grid computing, in: Proceeding of 10th IEEE Internet Heterogeneous Computing Workshop (HCW 2001), San Francisco, CA, IEEE Computer Society, 2001, pp. 776-790.; R. Buyya, J. Giddy, D. Abramson, A case for economy Grid architecture for service-oriented Grid computing, in: Proceeding of 10th IEEE Internet Heterogeneous Computing Workshop (HCW 2001), San Francisco, CA, IEEE Computer Society, 2001, pp. 776-790.
[8] Cooper, K.; Dasgupta, A.; Kennedy, K., New Grid scheduling and rescheduling methods in the GrADS Project, (Proceedings of NSF Next Generation Software Workshop, International Parallel and Distributed Processing Symposium, Los Alamitos, CA, USA (2004), IEEE CS Press: IEEE CS Press Berlin), 199-206
[9] D˘ogan, A.; Ozguner, F., Scheduling independent tasks with QoS requirements in Grid computing with time-varying resource prices, (Proceedings of GRID 2002. Proceedings of GRID 2002, Lecture Notes in Computer Science, vol. 2536 (2002), Springer), 58-69 · Zbl 1024.68699
[10] De, P.; Dunne, E. J.; Ghosh, J. B.; Wells, C. E., Complexity of the discrete time-cost tradeoff problem for project networks, Operations Research, 45, 2, 302-306 (1997) · Zbl 0893.90086
[11] De, P.; Dunne, E. J.; Ghosh, J. B.; Wells, C. E., The discrete time-cost tradeoff problem revisited, European Journal of Operational Research, 81, 2, 225-238 (1995) · Zbl 0927.90046
[12] Deelman, E., Mapping abstract complex workflows onto Grid environments, Journal of Grid Computing, 1, 1, 25-39 (2003)
[13] Foster, I.; Kesselman, C., The Grid: Blueprint for a Future Computing Infrastructure (1999), Morgan Kaufman Publishers: Morgan Kaufman Publishers USA
[14] Foster, I.; Kesselman, C.; Nick, J. M.; Tuecke, S., Grid service for distributed system integration, IEEE Computer, 35, 6, 37-46 (2002)
[15] Foster, I.; Fidler, M.; Roy, A.; Sander, V.; Winkler, L., End-to-end quality of service for high-end applications, Computing Communication, 27, 14, 1375-1388 (2004)
[16] Frey, J.; Tannenbaum, T., Condor-G: a computation management agent for multi-institutional grids, Cluster Computing, 5, 2, 237-246 (2002)
[17] Golconda, K.; Ozguner, F., A comparison of static QoS-based scheduling heuristics for a meta-task with multiple QoS dimensions in heterogeneous computing, (Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS’04), Santa Fe, New Mexico (2004), IEEE Press), 106-116
[18] X. Gu, K. Nahrstedt, A scalable QoS-aware service aggregation model for peer-to-peer computing Grids, in: Proceeding of the 11th IEEE International Symposium on High Performance Distributed Computing (HPDC), Piscataway, NJ, USA, 2002, pp. 73-82.; X. Gu, K. Nahrstedt, A scalable QoS-aware service aggregation model for peer-to-peer computing Grids, in: Proceeding of the 11th IEEE International Symposium on High Performance Distributed Computing (HPDC), Piscataway, NJ, USA, 2002, pp. 73-82.
[19] Jin, H.; Chen, H.; Lu, Z.; Ning, X., QoS Optimizing Model and Solving for Composite Service in CGSP Job Manager, Chinese Journal of Computers, 28, 4, 578-588 (2005)
[20] Klein, R., Bidirectional planning: improving priority rule-based heuristics for scheduling resource-constrained projects, European Journal of Operational Research, 127, 4, 619-638 (2000) · Zbl 0979.90073
[21] Li, C.; Li, L., QoS based resource scheduling by computational economy in computational Grid, Information Processing Letters, 98, 119-126 (2006) · Zbl 1187.68088
[22] Li, C.; Li, L., Utility-based QoS optimization strategy for multi-criteria scheduling on the Grid, Journal of Parallel and Distributed Computing, 67, 2, 142-153 (2007) · Zbl 1158.68348
[23] Lin, M.; Lin, Z., A cost-effective critical path approach for service priority selections in Grid computing economy, Decision Support Systems, 42, 3, 1628-1640 (2006)
[24] Menascé, D. A., QoS in Grid computing, IEEE Internet Computing, 8, 4, 85-87 (2004)
[25] A. O’Brien, S. Newhouse, J. Darlington, Mapping of scientific workflow within the e-Protein project to distributed resources, in: Proceedings of UK e-Science All Hands Meeting, Nottingham, UK, 2004, pp. 404-409.; A. O’Brien, S. Newhouse, J. Darlington, Mapping of scientific workflow within the e-Protein project to distributed resources, in: Proceedings of UK e-Science All Hands Meeting, Nottingham, UK, 2004, pp. 404-409.
[26] Shi, Z.; Dongarra, JJ., Scheduling workflow applications on processors with different capabilities, Future Generation Computer Systems, 22, 6, 665-675 (2006)
[27] D. Xu, K. Nahrstedt, Finding service paths in a media service proxy network, in: Proceeding of SPIE/ACM Multimedia Computing and Networking Conference (MMCN), California, USA, 2002, pp. 171-185.; D. Xu, K. Nahrstedt, Finding service paths in a media service proxy network, in: Proceeding of SPIE/ACM Multimedia Computing and Networking Conference (MMCN), California, USA, 2002, pp. 171-185.
[28] Yu, J.; Buyya, R., A novel architecture for realizing grid workflow using tuple spaces, (Proceedings of the 5th IEEE/ACM International Workshop on Grid Computing, Pittsburgh, USA (2004), IEEE CS Press), 119-128
[29] Yu, J.; Buyya, R., A taxonomy of workflow management systems for grid computing, Journal of Grid Computing, 3, 3-4, 171-201 (2005)
[30] J. Yu, R. Buyya, C.K. Tham, Cost-based scheduling of workflow applications on utility Grids, in: Proceedings of the First IEEE International Conference on e-Science and Grid Computing, Melbourne, Australia, 2005, pp. 140-147.; J. Yu, R. Buyya, C.K. Tham, Cost-based scheduling of workflow applications on utility Grids, in: Proceedings of the First IEEE International Conference on e-Science and Grid Computing, Melbourne, Australia, 2005, pp. 140-147.
[31] Yuan, Y.; Li, X.; Wang, Q.; Zhang, Y., Bottom Level based heuristic for scheduling workflows in Grids, Chinese Journal of Computers, 31, 2, 283-290 (2008)
[32] Zeng, L.; Benatallah, B.; Ngu, A. H.H.; Dumas, M.; Kalagnanam, J.; Chang, H., QoS-aware middleware for web services composition, IEEE Transactions on Software Engineering, 30, 5, 311-327 (2004)
[33] Y. Zhao, M. Wilde, I. Foster, J. Voeckler, T. Jordan, E. Quigg, J. Dobson, Grid middleware services for virtual data discovery, composition, and integration, in: Proceeding of the Second Workshop on Middleware for Grid Computing, Toronto, Ontario, Canada, 2004, pp. 57-62.; Y. Zhao, M. Wilde, I. Foster, J. Voeckler, T. Jordan, E. Quigg, J. Dobson, Grid middleware services for virtual data discovery, composition, and integration, in: Proceeding of the Second Workshop on Middleware for Grid Computing, Toronto, Ontario, Canada, 2004, pp. 57-62.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.