Article ID: | iaor20013887 |
Country: | Netherlands |
Volume: | 92 |
Start Page Number: | 305 |
End Page Number: | 333 |
Publication Date: | Nov 1999 |
Journal: | Annals of Operations Research |
Authors: | Nuijten Wim, Pape Claude Le, Baptiste Philippe |
This paper presents a set of satisfiability tests and time-bound adjustment algorithms that can be applied to cumulative scheduling problems. An instance of the cumulative scheduling problem (CuSP) consists of (1) one resource with a given capacity, and (2) a set of activities, each having a release date, a deadline, a processing time and a resource capacity requirement. The problem is to decide whether there exists a start time assignment to all activities such that at no point in time the capacity of the resource is exceeded and all timing constraints are satisfied. The cumulative scheduling problem can be seen as a relaxation of the decision variant of the resource-constrained project scheduling problem. We present three necessary conditions for the existence of a feasible schedule. Two of them are obtained by polynomial relaxations of the CuSP. The third is based on energetic reasoning. We show that the second condition is closely related to the subset bound, a well-known lower bound of the