Diz 51 en
Scheduling with Alternative Process Plans
Author: Čapek Roman
This thesis is dedicated to the design of practical and efficient models and algorithms for the production processes. The key addressed issue are the alternative process plans, supporting much more flexible definition of the scheduling problems.
With respect to the state of the art in the scheduling area, this thesis aims to cover the gap for the solution approaches that incorporate both the selection of process plan and the fine scheduling within a single model. Consequently, there are two main goals of the thesis - first, to propose a suitable mathematical model capable to cover standard scheduling problems together with the definition of the alternative process plans and second, to design, implement and evaluate algorithms for three different problems with alternative process plans, emerging from real production processes.
The mathematical model for the considered scheduling problems is based on the well known Resource Constrained Project Scheduling Problem (RCPSP) which is combined with the formalism of Nested Temporal Networks With Alternatives (NTNA). Such a model reflects the typical structure of the production processes and it keeps most of the assumptions and constraints from the powerful RCPSP framework. The proposed model involves renewable resources with non-unary capacity, sequence dependent setup times, release times and deadlines of activities and generalized temporal constraints. Thus, it allows very general and flexible definition of the scheduling problems with many realistic constraints.
Three different scheduling problems with alternative process plans are then in more detail. The first studied problem involves negative time-lags and the goal is to minimize the total schedule length. For such a problem we have developed constructive heuristic algorithm where the activities are being scheduled and un-scheduled according to their dynamic priorities. The second studied problem is motivated by the production processes where the goal is to utilize the expensive machines as much as possible and, therefore, the time spent by setting up such machines is minimized. The solution approach is based on the iterative method with separation of a schedule into time-disjunctive parts where the local search is applied. The criterion for the third considered problem is the minimization of the total production cost consisting of the costs corresponding to the selected production operations (activities) and penalization for late jobs. Two different evolutionary based heuristic algorithms are used to solve such a problem and their results are thoroughly compared in extensive performance evaluation.
Since there are no standard benchmarks for the proposed scheduling model, we have used the new generated instances specific for each problem under study as well as the existing instances for the similar problems from the literature. Although the available instances usually cover only a part of our approach, all the designed algorithms showed very good performance. In most cases, the results were competitive or even better when compared to the algorithms designed to the specific sub-problems of the general concept used in this thesis.
- Roman Čapek, mailto:capekrom@fel.cvut.cz