Satisfiability tests and time-bound adjustments for cumulative scheduling problems

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.