Philipp Benke

Abstract

Due to fast innovation cycles and a volatile market environment the competitiveness of a semiconductor memory company relies on its ability to place new products at optimal market-entry times. While the number of qualified engineers available is limited, the number of products which need to be developed in parallel is continuously augmenting. A common approach to speed up development processes in industry is the concurrent engineering concept, which aims at parallelizing the different phases of development projects. In general, the overlapping of development phases incurs additional integration and coordination efforts. That is why the relationship between parallelization and additional workload needs to be taken into account when scheduling development projects.

Each development project can be decomposed into a number of activities requiring time and resources for their completion. In our model we regard each development project as a sub-project of an overall project combining all development activities of the firm. The activities of this project are connected by temporal constraints arising from technical or organizational precedence relationships. Each activity of the project requires specialized engineers of different qualifications. Engineers of the same qualification are modeled as a renewable resource of limited capacity. The completion of the sub-projects has to be scheduled as close as possible to their given due dates for the market entry. Hence, the objective function of our scheduling problem is chosen to be the total weighted earlinesstardiness with respect to those due dates.

To allow for the consideration of the tradeoffs between parallelization and workload, we propose a generalization of classical project scheduling models. It is assumed that any two precedence-related activities may overlap in time and that such an overlapping leads to an increase in the duration of the second activity. The amount of this prolongation depends on the degree of overlapping between the activities. We suppose that the duration of an activity can be represented as a continuous and nondecreasing function of the overlap times with its predecessor activities. The project scheduling problem then consists in determining the completion times and the durations of the activities of the project in such a way that all temporal and resource constraints are taken into account and the total weighted earliness-tardiness of the project is minimized.

In the first part of the thesis we deal with the temporal scheduling computations providing the earliest and latest time-feasible start and completion times of the activities. We show that the set of all time-feasible completion times possesses a unique minimal point, which coincides with the earliest completion schedule. In difference to classical project scheduling, however, the vectors of earliest start, latest start, and latest completion times do not represent time-feasible schedules. Furthermore, it turns out that the set of all time-feasible start times generally decomposes into several disjoints sets, whereas the set of all time-feasible completion times is always connected. For the calculation of the earliest and latest completion times, a generalized label-correcting algorithm is devised, which iteratively evaluates first-order conditions for the optimal overlap times of the activities.

In the second part, we develop a multi-pass priority-rule method for the resource-constrained scheduling problem. In each iteration of the algorithm an activity is scheduled at a locally optimal time- and resource-feasible completion time and the earliest and latest completion times of the activities not yet scheduled are updated using the label-correcting method for the temporal scheduling. The algorithms are tested on a set of randomly generated test instances. The results indicate that compared to traditional project scheduling models, the new approach is able to achieve significant savings by optimally balancing overlap times and activity durations.