IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v92y1999i0p305-33310.1023-a1018995000688.html
   My bibliography  Save this article

Satisfiability tests and time‐bound adjustmentsfor cumulative scheduling problems

Author

Listed:
  • Ph. Baptiste
  • C. Le Pape
  • W. Nuijten

Abstract

This paper presents a set of satisfiability tests and time‐bound adjustmentalgorithms that can be applied to cumulative scheduling problems. An instance of thecumulative scheduling problem (CuSP) consists of (1) one resource witha given capacity, and (2) a set of activities, each having a release date, adeadline, a processing time and a resource capacityrequirement. The problem is to decide whether there exists a start time assignment to allactivities such that at no point in time the capacity of the resource is exceeded and alltiming constraints are satisfied. The cumulative scheduling problem can be seen as a relaxationof the decision variant of the resource‐constrained project scheduling problem.We present three necessary conditions for the existence of a feasible schedule. Two ofthem are obtained by polynomial relaxations of the CuSP. The third is based on energeticreasoning. We show that the second condition is closely related to the subset bound, awell‐known lower bound of the m‐machine problem. We also present three algorithms,based on the previously mentioned necessary conditions, to adjust release dates anddeadlines of activities. These algorithms extend the time‐bound adjustment techniquesdeveloped for the one‐machine problem. They have been incorporated in a branch andbound procedure to solve the resource‐constrained project scheduling problem.Computational results are reported. Copyright Kluwer Academic Publishers 1999

Suggested Citation

  • Ph. Baptiste & C. Le Pape & W. Nuijten, 1999. "Satisfiability tests and time‐bound adjustmentsfor cumulative scheduling problems," Annals of Operations Research, Springer, vol. 92(0), pages 305-333, January.
    • Handle: RePEc:spr:annopr:v:92:y:1999:i:0:p:305-333:10.1023/a:1018995000688
    DOI: 10.1023/A:1018995000688
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1023/A:1018995000688
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1023/A:1018995000688?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Xiangtong Qi & Jonathan F. Bard & Gang Yu, 2004. "Class Scheduling for Pilot Training," Operations Research, INFORMS, vol. 52(1), pages 148-162, February.
    2. Guyon, O. & Lemaire, P. & Pinson, É. & Rivreau, D., 2010. "Cut generation for an integrated employee timetabling and production scheduling problem," European Journal of Operational Research, Elsevier, vol. 201(2), pages 557-567, March.
    3. Jacques Carlier & Claire Hanen, 2024. "Measuring the slack between lower bounds for scheduling on parallel machines," Annals of Operations Research, Springer, vol. 338(1), pages 347-377, July.
    4. Néron, Emmanuel & Baptiste, Philippe & Gupta, Jatinder N. D., 2001. "Solving hybrid flow shop problem using energetic reasoning and global operations," Omega, Elsevier, vol. 29(6), pages 501-511, December.
    5. Roland Braune, 2022. "Packing-based branch-and-bound for discrete malleable task scheduling," Journal of Scheduling, Springer, vol. 25(6), pages 675-704, December.
    6. Arkhipov, Dmitry & Battaïa, Olga & Lazarev, Alexander, 2019. "An efficient pseudo-polynomial algorithm for finding a lower bound on the makespan for the Resource Constrained Project Scheduling Problem," European Journal of Operational Research, Elsevier, vol. 275(1), pages 35-44.
    7. Carlier, J. & Neron, E., 2003. "On linear lower bounds for the resource constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 149(2), pages 314-324, September.
    8. Carlier, J. & Pinson, E. & Sahli, A. & Jouglet, A., 2020. "An O(n2) algorithm for time-bound adjustments for the cumulative scheduling problem," European Journal of Operational Research, Elsevier, vol. 286(2), pages 468-476.
    9. Nolz, Pamela C. & Absi, Nabil & Feillet, Dominique & Seragiotto, Clóvis, 2022. "The consistent electric-Vehicle routing problem with backhauls and charging management," European Journal of Operational Research, Elsevier, vol. 302(2), pages 700-716.
    10. Carlier, Jacques & Neron, Emmanuel, 2007. "Computing redundant resources for the resource constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 176(3), pages 1452-1463, February.
    11. Hartmann, Sönke & Briskorn, Dirk, 2010. "A survey of variants and extensions of the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 207(1), pages 1-14, November.
    12. Thierry Petit & Emmanuel Poder, 2011. "Global propagation of side constraints for solving over-constrained problems," Annals of Operations Research, Springer, vol. 184(1), pages 295-314, April.
    13. Carlier, Jacques & Neron, Emmanuel, 2000. "A new LP-based lower bound for the cumulative scheduling problem," European Journal of Operational Research, Elsevier, vol. 127(2), pages 363-382, December.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:annopr:v:92:y:1999:i:0:p:305-333:10.1023/a:1018995000688. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.