Satisfiability tests and time-bound adjustments for cumulative scheduling problems

P. Baptiste, C. Le Pape, W.P.M. Nuijten

    Research output: Contribution to journalArticleAcademicpeer-review

    85 Citations (Scopus)
    2 Downloads (Pure)


    This paper presents a set of satisfiability tests and timebound 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 resourceconstrained 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, awellknown lower bound of the mmachine problem. We also present three algorithms,based on the previously mentioned necessary conditions, to adjust release dates anddeadlines of activities. These algorithms extend the timebound adjustment techniquesdeveloped for the onemachine problem. They have been incorporated in a branch andbound procedure to solve the resourceconstrained project scheduling problem.Computational results are reported.
    Original languageEnglish
    Pages (from-to)305-333
    JournalAnnals of Operations Research
    Issue number0
    Publication statusPublished - 1999


    Dive into the research topics of 'Satisfiability tests and time-bound adjustments for cumulative scheduling problems'. Together they form a unique fingerprint.

    Cite this