For classical non-cyclic scheduling problems, we are given a set of operations,each of which has to be processed exactly once. The aim is to minimize or maximizea given objective function such as makespan or sum of all (weighted) completion times for a given set of constraints. The set of constraints is usually given by precedence constraints between the operations. In contrast to these problems, for cyclic scheduling problems we are given a set of operations, each of which has to be processed infinitely often. Such types of scheduling problems arise in different application areas like compiler design, manufacturing, digital signal processing, railway scheduling, timetabling, etc. The problem is to find a periodic schedule which minimizes a given objective function. There exist two objective functions which are important in this area of cyclic scheduling. The objective which is considered throughout this work is to minimize the time difference between two succeeding occurrences of one operation for a given set of constraints. This time difference is called cycle time. In this thesis, we develop a general framework to model and to describe cyclic scheduling problems with resource constraints. Furthermore, we extend the model to describe blocking constraints for cyclic scheduling problems. In order to solve the problem, we develop a local search approach.
| Identifer | oai:union.ndltd.org:uni-osnabrueck.de/oai:repositorium.ub.uni-osnabrueck.de:urn:nbn:de:gbv:700-2006071418 |
| Date | 13 July 2006 |
| Creators | Kampmeyer, Thomas |
| Contributors | Prof. Dr. Peter Brucker, Prof. Ph.D. Eugene Levner |
| Source Sets | Universität Osnabrück |
| Language | English |
| Detected Language | English |
| Type | doc-type:doctoralThesis |
| Format | application/zip, application/pdf |
| Rights | http://rightsstatements.org/vocab/InC/1.0/ |
Page generated in 0.0051 seconds