×

zbMATH — the first resource for mathematics

Cumulative scheduling with variable task profiles and concave piecewise linear processing rate functions. (English) Zbl 1384.90047
Summary: We consider a cumulative scheduling problem where a task duration and resource consumption are not fixed. The consumption profile of the task, which can vary continuously over time, is a decision variable of the problem to be determined and a task is completed as soon as the integration over its time window of a non-decreasing and continuous processing rate function of the consumption profile has reached a predefined amount of energy. The goal is to find a feasible schedule, which is an NP-hard problem. For the case where functions are concave and piecewise linear, we present two propagation algorithms. The first one is the adaptation to concave functions of the variant of the energetic reasoning previously established for linear functions. Furthermore, a full characterization of the relevant intervals for time-window adjustments is provided. The second algorithm combines a flow-based checker with time-bound adjustments derived from the time-table disjunctive reasoning for the cumulative constraint. Complementarity of the algorithms is assessed via their integration in a hybrid branch-and-bound and computational experiments on small-size instances.

MSC:
90B35 Deterministic scheduling theory in operations research
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Artigues, C; Lopez, P; Haït, A, The energy scheduling problem: industrial case study and constraint propagation techniques, International Journal of Production Economics, 143, 13-23, (2013)
[2] Artigues, C; Lopez, P, Energetic reasoning for energy-constrained scheduling with a continuous resource, Journal of Scheduling, 18, 225-241, (2015) · Zbl 1320.90022
[3] BłaŻewicz, J; Machowiak, M; Wȩglarz, J; Kovalyov, M; Trystram, D, Scheduling malleable tasks on parallel processors to minimize the makespan, Annals of Operations Research, 129, 65-80, (2004) · Zbl 1056.90055
[4] Derrien, A., & Petit, T. (2014). A new characterization of relevant intervals for energetic reasoning. In International conference on principles and practice of constraint programming, CP 2014 vol. 8656 of lecture notes in computer science (289-297). Springer International Publishing. · Zbl 0491.90053
[5] Erschler, J., & Lopez, P. (1990). Energy-based approach for task scheduling under time and resources constraints. In 2nd International workshop on project management and scheduling (pp 115-121). Compiègne. · Zbl 1320.90022
[6] Gay, S., Hartert, R., & Schaus, P. (2015). Time-table disjunctive reasoning for the cumulative constraint. In International conference on AI and OR techniques in constraint programming for combinatorial optimization problems, CPAIOR 2015, vol. 9075 of lecture notes in computer science (pp. 157-172). Springer International Publishing. · Zbl 06605754
[7] Ngueveu, SU; Artigues, C; Lopez, P, Scheduling under a non-reversible energy source: an application of piecewise linear bounding of non-linear demand/cost functions, Discrete Applied Mathematics, 208, 98-113, (2016) · Zbl 1343.90039
[8] Hung, M.N., Le Van, C., & Michel, P. (2005). Non-convex aggregative technology and optimal economic growth. Cahiers de la Maison des Sciences Économiques 2005.95 - ISSN : 1624-0340. · Zbl 0491.90053
[9] Jensen, JLWV, Sur LES fonctions convexes et LES inégalités entre LES valeurs moyennes, Acta Mathematica, 30, 175-193, (1906) · JFM 37.0422.02
[10] Lahrichi, A, Ordonnancements. la notion de parties obligatoires et son application aux problèmes cumulatifs, RAIRO - Operations Research, 16, 241-262, (1982) · Zbl 0491.90053
[11] Lewis, J. Algebra symposium: optimizing fuel consumption. http://homepages.math.uic.edu/ jlewis/math165/asavgcost.pdf.
[12] Nattaf, M., Artigues, C., Lopez, P., & Rivreau, D. (2015). Energetic reasoning and mixed-integer linear programming for scheduling with a continuous resource and linear efficiency functions. OR Spectrum, 1-34. · Zbl 1339.90147
[13] Nattaf, M; Artigues, C; Lopez, P, A hybrid exact method for a scheduling problem with a continuous resource and energy constraints, Constraints, 20, 304-324, (2015) · Zbl 1327.90073
[14] Nattaf, M., Artigues, C., & Lopez, P. (2015). Flow and energy based satisfiability tests for the continuous energy-constrained scheduling problem with concave piecewise linear functions. In CP Doctoral Program 2015 (pp. 70-81). Cork. · Zbl 1056.90055
[15] Vilím, P, Timetable edge finding filtering algorithm for discrete cumulative resources, (2011), Berlin · Zbl 1302.90090
[16] Wolf, A., & Schrader, G. (2006). \(O\)(\(n\)\(n\)) overload checking for the cumulative constraint and its application. In Umeda, M., Wolf, A., Bartenstein, O., Geske, U., Seipel, D., & Takata, O. (Eds.), Declarative programming for knowledge management. INAP 2005 lecture notes in computer science, Vol. 4369. Berlin: Springer. · Zbl 1302.90090
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.