The work of the thesis is motivated by an industrial project which dealt with the development and implementation of a system for production planning and control (PPC) for the brewery and beverage industry. This thesis consists of two parts. In the first part we give a in-depth theoretical analysis of efficient algorithms for production planning. We obtain best possible approximation results for two scheduling problems and provide additional performance analysis of simple (online) scheduling algorithms. The second part of this thesis considers the implementation of planning algorithms into our PPC-Solution and discusses resulting problems concerning the system integration. The research in the theoretical part of the thesis is motivated by the application in the brewery and beverage industries. We consider variants of classic scheduling problems, that are - in contrary to the classical problems - closer related to industrial practice. More precisely, we consider problems where resource may be unavailable over time. This approach is suitable to model system faults, maintenance services and disruptions. Secondly, such an approach reflects a "planning during production" where machines are partially used and continuously obtain additional jobs. We were able to develop new scheduling algorithms that have almost the same performance guarantees as the best algorithms for the classic variants of the problems. Our theoretical research also deals with the performance of algorithms. We consider the question in which way a "good" performance of an algorithm can be measured. We leave the classic analysis that computes the behavior of the algorithm in the worst case. Instead we use an average-case-analysis in order to describe the typical behavior of the algorithm. We use a stochastic model where processing times of the jobs are given by random variables. In the second part of the thesis we bridge theory and practice. For our application in the brewery and beverage industry we provide a business model that describes typical information and data flow in an abstract manner. This model can be seen as a representative for the process industry in general, as it includes typical elements of the process industry such as batch production, inventory orientation and multi-level production. Based on our model we indicate the limits of the theoretical results obtained in the first part of the thesis. Consequently, new approaches are necessary. It turns out that the planning problems can be solved best possible from an theoretical point of view, however the algorithms may not work in the given application. The system concept developed in this thesis is suitable for the requirements in the brewing and beverage industry. The system architecture is hierarchic and it vertically combines the higher management level with the production level. Horizontally it follows the arrangement of a brewery factory into several production levels. The scheduling algorithms are built accordingly, such that they can plan in multi stages and only use the information that is accessible according to their hierarchical level. We describe the system integration of the algorithms into the planning system. The challenge is mainly the combination of distinct system components and in the integration of the planning algorithms into the data flow of the company.     «

The work of the thesis is motivated by an industrial project which dealt with the development and implementation of a system for production planning and control (PPC) for the brewery and beverage industry. This thesis consists of two parts. In the first part we give a in-depth theoretical analysis of efficient algorithms for production planning. We obtain best possible approximation results for two scheduling problems and provide additional performance analysis of simple (online) scheduling algo...     »