×

zbMATH — the first resource for mathematics

Time and resource constrained scheduling. A constraint satisfaction approach. (English. Dutch summary) Zbl 0837.90068
Eindhoven: Univ. of Technology. x, 157 p. (1994).
The thesis is concerned with the time and resource constrained scheduling problem (TRCSP). The goal is to develop a solution method that is capable of handling the TRCSP in general, but that also has a good performance for problems that are special cases of the TRCSP. The TRCSP is modeled as a special case of the Constraint Satisfaction Problem (CSP). For this problem solution algorithms are designed. The TRCSP is NP-hard. The author only considers deterministic non-preemptive scheduling problems. To solve the CSP a tree search is discussed. The author considers consistency checking to shorten the search tree, variable and value selection to define branching and some backtrack procedures. Computational studies for theoretical (job shop scheduling, multiple capacitated job shop scheduling, job shop scheduling with resource set alternatives) and practical (examination time tabling, frit production scheduling, school time tabling) problems show the good performance of the chosen approach.
Reviewer: J.Terno (Dresden)

MSC:
90B35 Deterministic scheduling theory in operations research
PDF BibTeX XML Cite