Abstract
This paper considers the problem of scheduling a set of time- and energy-constrained preemptive tasks on a discrete time horizon. At each time period, the total energy required by the tasks that are in process can be provided by two energy sources: a reversible one and a non-reversible one. The non-reversible energy source can provide an unlimited amount of energy for a given period but at the expense of a time-dependent piecewise linear cost. The reversible energy source is a storage resource. The goal is to schedule each task preemptively inside its time window and to dispatch the required energy to the sources at each time period, while satisfying the reversible source capacity constraints and minimizing the total cost. We propose a mixed integer linear program of pseudo-polynomial size to solve this NP-hard problem. Acknowledging the limits of this model for problem instances of modest size, we propose an iterative decomposition matheuristic to compute an upper bound. The method relies on an efficient branch-and-price method or on a local search procedure to solve the scheduling problem without storage. The energy source allocation problem for a fixed schedule can in turn be solved efficiently by dynamic programming as a particular lot-sizing problem. We also propose a lower bound obtained by solving the linear programming relaxation of a new extended formulation by column generation. Experimental results show the quality of the bounds compared to the ones obtained using mixed integer linear program.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Notes
In Neumann and Schwindt (2003), such resources are called cumulative resources
Detailed results including lower bounds, upper bounds and cpu times are available at http://homepages.laas.fr/sungueve/Data/SWRSFullResultsLBUBcpu.csv.
References
Absi, N., Artigues, C., Kedad-Sidhoum, S., Ngueveu, S.U., Saadi, O.: Lot-sizing models for energy management. In: International Workshop on Lot Sizing—IWLS’2017, pp. 45–48. Glasgow (2017)
Bambagini, M., Marinoni, M., Aydin, H., Buttazzo, G.: Energy-aware scheduling for real-time systems: a survey. ACM Trans. Embed. Comput. Syst. (TECS) 15(1), 1–34 (2016)
Beale, E.M.L., Forrest, J.J.H.: Global optimization using special ordered sets. Math. Program. 10(1), 52–69 (1976)
Beldiceanu, N., Poder, E.: A continuous multi-resources cumulative constraint with positive-negative resource consumption-production. In: International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming, pp. 214–228. Springer (2007)
Brahimi, N., Absi, N., Dauzère-Pérès, S., Nordli, A.: Single-item dynamic lot-sizing problems: an updated survey. Eur. J. Oper. Res. 263(3), 838–863 (2017)
Carlier, J., Moukrim, A.: Storage resources. In: Handbook on Project Management and Scheduling, Vol. 1, pp. 177–189. Springer (2015)
Carlier, J., Moukrim, A., Sahli, A.: Lower bounds for the event scheduling problem with consumption and production of resources. Discret. Appl. Math. 234, 178–194 (2018)
Carlier, J., Moukrim, A., Xu, H.: The project scheduling problem with production and consumption of resources: a list-scheduling based algorithm. Discret. Appl. Math. 157(17), 3631–3642 (2009)
Ji, K., Chi, C., Marahatta, A., Zhang, F., Liu, Z.: Energy efficient scheduling based on marginal cost and task grouping in data centers. In: Proceedings of the Eleventh ACM International Conference on Future Energy Systems, pp. 482–488 (2020)
Keha, A.B., de Farias Jr, I.R., Nemhauser, G.L.: A branch-and-cut algorithm without binary variables for nonconvex piecewise linear optimization. Oper. Res. 54(5), 847–858 (2006)
Koné, O., Artigues, C., Lopez, P., Mongeau, M.: Comparison of mixed integer linear programming models for the resource-constrained project scheduling problem with consumption and production of resources. Flex. Serv. Manuf. J. 25(1–2), 25–47 (2013)
Laborie, P.: Algorithms for propagating resource constraints in AI planning and scheduling: existing approaches and new results. Artif. Intell. 143(2), 151–188 (2003)
Meng, L., Sanseverino, E.R., Luna, A., Dragicevic, T., Vasquez, J.C., Guerrero, J.M.: Microgrid supervisory controllers and energy management systems: a literature review. Renew. Sustain. Energy Rev. 60, 1263–1273 (2016)
Merkert, L., Harjunkoski, I., Isaksson, A., Säynevirta, S., Saarela, A., Sand, G.: Scheduling and energy-industrial challenges and opportunities. Comput. Chem. Eng. 72, 183–198 (2015)
Mingozzi, A., Maniezzo, V., Ricciardelli, S., Bianco, L.: An exact algorithm for the resource-constrained project scheduling problem based on a new mathematical formulation. Manage. Sci. 44(5), 714–729 (1998)
Neumann, K., Schwindt, C.: Project scheduling with inventory constraints. Math. Methods Oper. Res. 56(3), 513–533 (2003)
Ngueveu, S.U., Artigues, C., Lopez, P.: Scheduling under a non-reversible energy source: an application of piecewise linear bounding of non-linear demand/cost functions. Discret. Appl. Math. 208, 98–113 (2016)
Olatomiwa, L., Mekhilef, S., Ismail, M.S., Moghavvemi, M.: Energy management strategies in hybrid renewable energy systems: a review. Renew. Sustain. Energy Rev. 62, 821–835 (2016)
Parisio, A., Rikos, E., Glielmo, L.: A model predictive control approach to microgrid operation optimization. IEEE Trans. Control Syst. Technol. 22(5), 1813–1827 (2014)
Sahli, A., Carlier, J., Moukrim, A.: Comparison of mixed integer linear programming models for the event scheduling problem with consumption and production of resources. IFAC-PapersOnLine 49(12), 1044–1049 (2016)
Schutt, A., Stuckey, P.J.: Explaining producer/consumer constraints. In: International Conference on Principles and Practice of Constraint Programming, pp. 438–454. Springer (2016)
Shaw, D.X., Wagelmans, A.P.: An algorithm for single-item capacitated economic lot sizing with piecewise linear production costs and general holding costs. Manage. Sci. 44(6), 831–838 (1998)
Sourd, F., Rogerie, J.: Continuous filling and emptying of storage systems in constraint-based scheduling. Eur. J. Oper. Res. 165(2), 510–524 (2005)
Wei, W., Liu, F., Mei, S.: Energy pricing and dispatch for smart grid retailers under demand response and market price uncertainty. IEEE Trans. Smart Grid 6(3), 1364–1374 (2014)
Zia, M.F., Elbouchikhi, E., Benbouzid, M.: Microgrids energy management systems: a critical review on methods, solutions, and prospects. Appl. Energy 222, 1033–1055 (2018)
Acknowledgements
This research benefited from the support of the FMJH “Program Gaspard Monge for optimization and operations research and their interactions with data science”, and from the support from EDF and/or Thales. This work was also supported by the ANR Project PICOMODALITE. The contribution of Félix Goupil, Janik Rannou and Omar Saadi in preliminary internships is gratefully acknowledged.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Ngueveu, S.U., Artigues, C., Absi, N. et al. Lower and upper bounds for scheduling energy-consuming tasks with storage resources and piecewise linear costs. J Heuristics 28, 93–120 (2022). https://doi.org/10.1007/s10732-021-09486-w
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10732-021-09486-w
Keywords
- Energy-aware scheduling
- Piecewise linear costs
- Storage resources
- Matheuristic
- Column generation
- Lot sizing
- Mixed integer programming