Abstract
This paper addresses a scheduling problem with a cumulative continuous resource and energy constraints. Given a set of non-preemptive tasks, each task requires a continuously-divisible resource. The instantaneous resource usage of a task is limited by a minimum and maximum resource requirement. Its processing has to lie within a time-window and the total energy received obtained by integrating a function f i of the instantaneous resource usage over the processing interval must reach a required value (where f i is a non-decreasing, continuous function). The problem is to find a feasible schedule of the tasks, which satisfies all the constraints. This problem, which is a generalization of the well-known cumulative scheduling problem, is NP-complete. For the case where all functions f i are linear, we exhibit structural properties of the feasible solutions and we present a Mixed Integer Linear Program (MILP) based on an event-based formulation. We also adapt the famous “left-shift/right-shift” satisfiability test (energetic reasoning) and the associated time-window adjustments to our problem. To achieve this test, we present three different ways for computing the relevant intervals. Finally, we present a hybrid branch-and-bound method to solve the problem, which performs, at each node, the satisfiability test and time-window adjustments and, when the domains of all start and end times are small enough, the remaining solution space is searched via the event-based MILP.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Artigues, C., Lopez, P., & Haït, A. (2013). The energy scheduling problem: industrial case-study and constraint propagation techniques. International Journal of Production Economics, 143(1), 13–23.
Artigues, C., & Lopez, P. Energetic reasoning for energy-constrained scheduling with a continuous resource. Journal of Scheduling. doi:10.1007/s10951-014-0404-y.
Baptiste, P., Le Pape, C., & Nuijten, W. (2001). Constraint-based scheduling. Boston/Dordrecht/London: Kluwer Academic Publishers.
BlaZewicz, J., Ecker, K.H., Pesch, E., Schmidt, G., & Weglarz, J. (2001). Scheduling computer and manufacturing processes. Berlin/Heidelberg: Springer-Verlag.
BlaZewicz, J., Machowiak, M., Weglarz, J., Kovalyov, M., & Trystram, D. (2004). Scheduling malleable tasks on parallel processors to minimize the makespan. Annals of Operations Research, 129(1-4), 65–80.
Bentley, J.L., & Ottmann, T.A. (1979). Algorithms for reporting and counting geometric intersections. IEEE Transactions on Computers, 28(9), 643–647.
Bonifas, N. (2014). Fast propagation for the energy reasoning. In Doctoral program of the 20th international conference on principles and practice of constraint programming (CP) (pp. 16–22).
Carlier, J., & Latapie, B. (1991). Une méthode arborescente pour résoudre les problèmes cumulatifs. RAIRO Recherche opérationnelle, 25(3), 311–340.
Derrien, A., & Petit, T. (2014). A new characterization of relevant intervals for energetic reasoning. Principles and practice of constraint programming. Lecture Notes in Computer Science, 8656, 289–297.
Fündeling, C.-U., & Trautmann, N. (2010). A priority-rule method for project scheduling with work-content constraints. European Journal of Operational Research, 203(3), 568–574.
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, France.
Józefowska, J., Mika, M., RóZycki, R., Waligóra, G., & Weglarz, J. (1999). Project scheduling under discrete and continuous resources. In Weglarz, J. (Ed.) Project scheduling: recent models, algorithms, and applications (pp. 289–308). Boston: Kluwer Academic Publishers.
Kis, T. (2005). A branch-and-cut algorithm for scheduling of project with variable-intensity activities. Mathematical Programming Series A, 103, 515–539.
Koné, O., Artigues, C., Lopez, P., & Mongeau, M. (2011). Event-based MILP models for resource-constrained project scheduling problems. Computers & Operations Research, 38(1), 3–13.
Naber, A., & Kolisch, R. (2014). MIP models for resource-constrained project scheduling with flexible resource profiles. European Journal of Operational Research, 239, 335–348.
Naber, A., & Kolisch, R. (2014). A continuous time model for the resource-constrained project scheduling with flexible resource profiles. In Proceedings of the 14th international conference on project management and scheduling (pp. 166–168). Munich, Germany.
Nattaf, M., Artigues, C., & Lopez, P. (2014). A polynomial satisfiability test using energetic reasoning for energy constraint scheduling. In 14th international workshop on project management and scheduling (pp. 169–172). Munich, Germany.
Weglarz, J., Józefowska, J., Mika, M., & Waligóra, G. (2009). Project scheduling with finite or infinite number of activity processing modes - A survey. European Journal of Operational Research, 208, 177–205.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
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). https://doi.org/10.1007/s10601-015-9192-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10601-015-9192-z