×

zbMATH — the first resource for mathematics

Reducing the solution space of optimal task scheduling. (English) Zbl 1348.90312
Summary: Many scheduling problems are tackled by heuristics due to their NP-hard nature. Task scheduling with communication delays \((P|\prec, c_{ij}| C_{\max})\) is no exception. Nevertheless, it can be of significant advantage to have optimal schedules, e.g. for time critical systems or as a baseline to evaluate heuristics. A promising approach to optimal task scheduling with communication delays for small problems is the use of exhaustive search techniques such as \(A^\ast\). \(A^\ast\) is a best first search algorithm guided by a cost function. While good cost functions reduce the search space, early results have shown that problem specific pruning techniques are paramount. This paper proposes two novel pruning techniques that significantly reduce the search space for \(P|\prec, c_{ij}| C_{\max}\). The pruning techniques Fixed Task Order and Equivalent Schedules are carefully investigated based on observations made with simple graph structures such as fork, join and fork-join, yet they are generally applicable. An extensive experimental evaluation of computing more than two thousand schedules demonstrates the efficiency of the novel pruning techniques in significantly reducing the solution space.

MSC:
90B35 Deterministic scheduling theory in operations research
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90C59 Approximation methods and heuristics in mathematical programming
Software:
Hypertool
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bender A. MILP based task mapping for heterogeneous multiprocessor systems. In: Proceedings of European design automation conference. IEEE; 1996. p. 190-7.
[2] Daoud, M. I.; Kharma, N., A high performance algorithm for static task matching and scheduling, Journal of Parallel and Distributed Computing, 68, 4, 399-409, (2008) · Zbl 1243.68103
[3] Davare A, Chong J, Zhu A, Densmore D, Sangiovanni-Vincentelli A. Classification, customization, and characterization: using MILP for task allocation and scheduling. Technical Report UCB/EECS-2006-166. Berkeley: University of California; December 2006.
[4] Davidović T, Liberti L, Maculan N, Mladenović N. Towards the optimal solution of the multiprocessor scheduling problem with communication delays. In: Proceedings of third multidisciplinary international conference on scheduling: theory and application (MISTA); August 2007. p. 128-35.
[5] Dechter, R.; Pearl, J., Generalized best-first search strategies and the optimality of A^{⁎}, Journal of the ACM, 32, July (3), 505-536, (1985) · Zbl 0631.68075
[6] Drozdowski, M., Scheduling for parallel processing, (2009), Springer · Zbl 1187.68090
[7] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and schedulinga survey, Annals of Discrete Mathematics, 5, 287-326, (1979) · Zbl 0411.90044
[8] Hagras, T.; Janeî¡ek, J., A high performance, low complexity algorithm for compile-time task scheduling in heterogeneous systems, Parallel Computing, 31, 7, 653-670, (2005)
[9] Hanen C, Munier A. An approximation algorithm for scheduling dependent tasks on m processsors with small communication delays. In: ETFA 95: INRIA/IEEE symposium on emerging technology and factory animation. IEEE Press; 1995. p. 167-89.
[10] Hu, T., Parallel sequencing and assembly line problems, Operations Research, 9, 6, 841-848, (1961)
[11] Hwang, J. J.; Chow, Y. C.; Anger, F. D.; Lee, C. Y., Scheduling precedence graphs in systems with interprocessor communication times, SIAM Journal of Computing, 18, April (2), 244-257, (1989) · Zbl 0677.68026
[12] Hwang, R.; Gen, M.; Katayama, H., A comparison of multiprocessor task scheduling algorithms with communication costs, Computer and Operations Research, 35, 976-993, (2008) · Zbl 1278.90159
[13] Jin, S.; Schiavone, G.; Turgut, D., A performance study of multiprocessor task scheduling algorithms, Journal of Supercomputing, 43, 77-97, (2008)
[14] Kadamuddi, D.; Tsai, J. J.P., Clustering algorithm for parallelizing software systems in multiprocessor environment, IEEE Transactions on Parallel and Distributed Systems, 26, April (4), (2000)
[15] Kafil, M.; Ahmad, I., Optimal task assignment in heterogeneous distributed computing systems, IEEE Concurrency, 6, 42-51, (1998)
[16] Kianzad, V.; Bhattacharyya, S. S., Efficient techniques for clustering and scheduling onto embedded multiprocessors, IEEE Transactions on Parallel and Distributed Systems, 17, 7, 667-680, (2006)
[17] Kwok, Y.-K.; Ahmad, I., On multiprocessor task scheduling using efficient state space approaches, Journal of Parallel and Distributed Computing, 65, 1515-1532, (2005) · Zbl 1103.68406
[18] Poole, D.; Mackworth, A., Artificial intelligencefoundations of computational agents, (2010), Cambridge University Press
[19] Rayward-Smith, V. J., UET scheduling with unit interprocessor communication delays, Discrete Applied Mathematics, 18, 55-71, (1987) · Zbl 0634.90031
[20] Russell, S. J.; Norvig, P., Artificial intelligencea modern approach, (2003), Prentice Hall
[21] Stuart S. Russell. Efficient memory-bounded search methods. In: Proceedings of the 10th European conference on artificial intelligence, ECAI ’92. Wiley; 1992. p. 1-5.
[22] Semar Shahul, A. Z.; Sinnen, O., Scheduling task graphs optimally with A^{⁎}, Journal of Supercomputing, 51, 3, 310-332, (2010)
[23] Sinnen, O., Task scheduling for parallel systems, (2007), Wiley, May
[24] Sinnen O, Sousa L. Scheduling task graphs on arbitrary processor architectures considering contention. In: High performance computing and networking (HPCN’01), lecture notes in computer science. vol. 2110, Springer-Verlag; 2001. p. 373-82. · Zbl 0997.68699
[25] Sinnen, O.; Sousa, L., Experimental evaluation of task scheduling accuracyimplications for the scheduling model, IEICE Transactions on Information and Systems, E86-D, September (9), 1620-1627, (2003)
[26] Thanalapati, T.; Dandamudi, S., An efficient adaptive scheduling scheme for distributed memory multicomputer, IEEE Transactions on Parallel and Distributed Systems, 12, 7, 758-768, (2001)
[27] Topcuoglu, H.; Hariri, S.; Wu, M.-Y., Performance-effective and low complexity task scheduling for heterogeneous computing, IEEE Transactions on Parallel and Distributed Systems, 13, 3, 260-274, (2002)
[28] Veltman, B.; Lageweg, B. J.; Lenstra, J. K., Multiprocessor scheduling with communication delays, Parallel Computing, 16, 2-3, 173-182, (1990) · Zbl 0711.68017
[29] Wu, A. S.; Yu, H.; Jin, S.; Lin, K.; Schiavone, G., An incremental genetic algorithm approach to multiprocessor scheduling, IEEE Transactions on Parallel and Distributed Systems, 15, September (9), 824-834, (2004)
[30] Wu, M. Y.; Gajski, D. D., Hypertool: a programming aid for message-passing systems, IEEE Transactions on Parallel and Distributed Systems, 1, July (3), 330-343, (1990)
[31] Yang, T.; Gerasoulis, A., List scheduling with and without communication delays, Parallel Computing, 19, 12, 1321-1344, (1993) · Zbl 0797.68020
[32] Zomaya, A. Y.; Ward, C.; Macey, B. S., Genetic scheduling for parallel processor systemscomparative studies and performance issues, IEEE Transactions on Parallel and Distributed Systems, 10, August (8), 795-812, (1999)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.