×

zbMATH — the first resource for mathematics

Allocation and scheduling of conditional task graphs. (English) Zbl 1186.90054
Summary: We propose an original, complete and efficient approach to the allocation and scheduling of Conditional Task Graphs (CTGs). In CTGs, nodes represent activities, some of them are branches and are labeled with a condition, arcs rooted in branch nodes are labeled with condition outcomes and a corresponding probability. A task is executed at run time if the condition outcomes that label the arcs in the path to the task hold at schedule execution time; this can be captured off-line by adopting a stochastic model. Tasks need for their execution either unary or cumulative resources and some tasks can be executed on alternative resources. The solution to the problem is a single assignment of a resource and of a start time to each task so that the allocation and schedule is feasible in each scenario and the expected value of a given objective function is optimized. For this problem we need to extend traditional constraint-based scheduling techniques in two directions: (i) compute the probability of sets of scenarios in polynomial time, in order to get the expected value of the objective function; (ii) define conditional constraints that ensure feasibility in all scenarios. We show the application of this framework on problems with objective functions depending either on the allocation of resources to tasks or on the scheduling part. Also, we present the conditional extension to the timetable global constraint. Experimental results show the effectiveness of the approach on a set of benchmarks taken from the field of embedded system design. Comparing our solver with a scenario based solver proposed in the literature, we show the advantages of our approach both in terms of execution time and solution quality.
MSC:
90B35 Deterministic scheduling theory in operations research
90C35 Programming involving graphs or networks
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] van der Aalst, W.M.P.; Schonenberg, M.H.; Song, M., Time prediction based on process mining, BPM Center Report BPM-09-04, BPMcenter.org, 2009
[2] S. Ahmed, A. Shapiro, The sample average approximation method for stochastic programs with integer recourse, in: Optimization on Line, 2002
[3] Baptiste, P.; Le Pape, C., Constraint propagation and decomposition techniques for highly disjunctive and highly cumulative project scheduling problems, Constraints, 5, 1/2, 119-139, (2000) · Zbl 0941.90030
[4] Baptiste, P.; Le Pape, C.; Nuijten, W., Constraint-based scheduling, (2003), Kluwer Academic Publisher
[5] R. Bartak, Ondrej Cepek, Temporal networks with alternatives: Complexity and model, in: FLAIRS 2007, 2007, pp. 641-646 · Zbl 1176.68194
[6] R. Bartak, O. Cepek, P. Surynek, Modelling alternatives in temporal networks, in: IEEE Symposium on Computational Intelligence in Scheduling, SCIS07, 2007, pp. 129-136
[7] Beck, J.C.; Fox, M.S., Constraint-directed techniques for scheduling alternative activities, Journal of artificial intelligence (AI), 121, 1/2, 211-250, (2000) · Zbl 0948.68009
[8] Benders, J.F., Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik, 4, 238-252, (1962) · Zbl 0109.38302
[9] J. Bidot, T. Vidal, P. Laborie, J.C. Beck, A general framework for scheduling in a stochastic environment, in: Proc. of the Intl. Joint Conference on Artificial Intelligence, IJCAI 2007, 2007, pp. 56-61 · Zbl 1185.90109
[10] Cox, D.R.; Smith, W.L., Queues, (1961), Chapman & Hall
[11] Dechter, R., Constraint processing, (2003), Morgan Kaufmann
[12] Eles, P.; Peng, Z., Bus access optimization for distributed embedded systems based on schedulability analysis, ()
[13] Faraboschi, P.; Fisher, J.A.; Young, C., Instruction scheduling for instruction level parallel processors, Proceedings of the IEEE, 89, 11, 1638-1659, (2001)
[14] Gittins, J.C.; Jones, D.M., A dynamic allocation index for the sequential design of experiments, Progress of statistics, Colloq. math. soc. janos bolyai, 9, 241-255, (1974) · Zbl 0303.62064
[15] Guerri, A.; Lombardi, M.; Milano, M., Challenging scheduling problem in the field of system design, in the “Task Graph Generator” section
[16] Hooker, J.N.; Ottosson, G., Logic-based benders decomposition, Mathematical programming, 96, 33-60, (2003) · Zbl 1023.90082
[17] Kennedy, K.; Allen, R., Optimizing compilers for modern architectures: A dependence-based approach, (2001), Morgan Kaufmann
[18] Kuchcinski, K., Constraints-driven scheduling and resource assignment, ACM transactions on design automation of electronic systems, 8, (2003)
[19] Kuchcinski, K.; Wolinski, C., Global approach to assignment and scheduling of complex behaviors based on HCDG and constraint programming, Journal of systems architecture, 49, 12-15, 489-503, (2003)
[20] J. Kuster, D. Jannach, G. Friedrich, Handling alternative activities in resource constrained project scheduling problems, in: Proc. of the Intl. Joint Conference on Artificial Intelligence, 2007, pp. 1960-1965
[21] Laborie, P., Algorithms for propagating resource constraints in AI planning and scheduling: existing approaches and new results, Journal of artificial intelligence, 143, 151-188, (2003) · Zbl 1079.68622
[22] Laporte, G.; Louveaux, F.V., The integer l-shaped method for stochastic integer programs with complete recourse, Operations research letters, 13, (1993) · Zbl 0793.90043
[23] Le Pape, C., Implementation of resource constraints in ILOG SCHEDULE: A library for the development of constraint-based scheduling systems, Intelligent systems engineering, 3, 2, 55-66, (1994)
[24] M. Lombardi, M. Milano, Scheduling conditional task graphs, in: Proc. of CP 2007, 2007, pp. 468-482 · Zbl 1145.68524
[25] M. Lombardi, M. Milano, Stochastic allocation and scheduling for conditional task graphs in MPSoCs, in: Proc. of CP 2006, 2006, pp. 299-313
[26] Norkin, V.I.; Pflug, G.; Ruszczynski, A., A branch and bound method for stochastic global optimization, Mathematical programming, 83, (1998) · Zbl 0920.90111
[27] Organization for the Advancement of Structured Information Standards (OASIS), Web Services Business Process Execution Language Version 2.0, OASIS Standard, 2007
[28] M.A. Peot, D.E. Smith, Conditional nonlinear planning, in: Proc. of Intl. Conference on AI Planning and Scheduling, 1992, pp. 189-197
[29] RothKopf, M.H., Scheduling with random service times, Management science, 12, 707-713, (1966) · Zbl 0199.23302
[30] N. Russell, W.M.P. van der Aalst, A.H.M. ter Hofstede, D. Edmond, Workflow data patterns: Identification, representation and tool support, in: Proc. of the 17th Intl. Conference on Advanced Information Systems Engineering, 2005, pp. 216-232
[31] Shin, D.; Kim, J., Power-aware scheduling of conditional task graphs in real-time multiprocessor systems, (), 408-413
[32] Smith, W.E., Various optimizer for single stage production, Naval research logistic quarterly, 3, 59-66, (1956)
[33] Tarim, A.; Manandhar, S.; Walsh, T., Stochastic constraint programming: A scenario-based approach, Constraints, 11, 53-80, (2006) · Zbl 1103.68828
[34] Ter Hofstede, A.H.M.; Weske, M., Business process management: A survey, (), 1-12
[35] I. Tsamardinos, M.E. Pollack, J.F. Horty, Merging plans with quantitative temporal constraints, temporally extended actions, and conditional branches, in: Proc. of the 5th International Conference on AI Planning Systems, 2000, pp. 264-272
[36] Tsamardinos, I.; Vidal, T.; Pollack, M.E., CTP: A new constraint-based formalism for conditional temporal planning, Constraints, 8, 4, 365-388, (2003) · Zbl 1074.68616
[37] Vidal, T.; Fargier, H., Handling contingencies in temporal constraint network: from consistency to controllability, Journal of experimental and theoretical artificial intelligence, 11, 23-45, (1999)
[38] Vilim, P.; Bartak, R.; Cepek, O., Extension of \(o(n . \log n)\) filtering algorithms for the unary resource constraint to optional activities, Constraints, 10, 403-425, (2005) · Zbl 1122.90045
[39] Y. Xie, W. Wolf, Allocation and scheduling of conditional task graph in hardware/software co-synthesis, in: Proc. of Design, Automation and Test in Europe, DATE2001, 2001, pp. 620-625
[40] T. Walsh, Stochastic constraint programming, in: Proc. of the European Conference on Artificial Intelligence, ECAI, 2002
[41] Weske, M., Business process management: concepts, languages, architectures, (2007), Springer Berlin
[42] Wu, D.; Al-Hashimi, B.; Eles, P., Scheduling and mapping of conditional task graph for the synthesis of low power embedded systems, Computers and digital techniques, IEEE Proceedings, 150, 5, 262-273, (2003)
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.