Resource-Constrained Scheduling

A scheduling problem consists in determining the execution time interval for a number activities, taking into account the limited availability of production factors. In the planning of value creation processes, scheduling problems occur as project scheduling problems in research and development, and as problems of rough-cut capacity planning and machine scheduling in production planning. In a resource-constrained scheduling problem, processes typically require more than one unit of production factors each. The production factors are then termed "resources", the renewable resources corresponding to nonconsumable and the storage resources to consumable production factors.

In our research we are interested in structural issues for various types of resource-constrained scheduling problems. Based on the structural properties of the respective problem, we develop exact and heuristic solution procedures. In particular, we deal with rich resource-constrained scheduling problems comprising complex side constraints such as minimum and maximum time lags betweeen activities, overlap-dependent activity durations, preemptable activities. Our concept of storage resources permits the integration of material-availability and storage-capacity constraints, which play an important role in many practical scheduling problems. Scheduling problems with storage resources have gained entry worldwide into numerous research projects of other working groups and industrial planning systems.

PhD projects:

Benchmark instances: Project generator ProGen/max

Integrated Routing and Scheduling

In the scheduling of activities being distributed over several locations in a network and using common resources, decisions must be made about execution time intervals of the activities (scheduling problem) and the transfer of resource units between the locations (routing problem). Suchlike routing and scheduling problems occur, for example, in the planning of cross-location production processes in supply chains, of outpatient care, or of spatially spread project portfolios. Owing to the strong interdependency of scheduling and routing decisions, their hierarchical division into two subproblems often leads to inefficient solutions. If the two subproblems are considered through a common model, leads to an integrated routing and scheduling problem. Due to its greater inherent complexity such an integrated problem is more difficult to solve. It does, however, comprehensively include the potential of optimally coordinating scheduling and routing decisions.

With the resource transfer problem, we are developing in our research a generic modeling framework for integrated routing and scheduling problems. The resource transfer problem consists in scheduling distributed events that deplete and replenish the availabilty of renewable and of storage resources. Subset of suitable resource units are to be allocated to each event. For given pairs of events, minimum and maximum time lags between their occurrence times, transfer times for shared resource units, as well as incompatibility and inclusion constraints for the resource allocations must be observed. A large variety of problems from the areas of vehicle routing, machine scheduling, and project planning as well as their combinations are covered by this reference model, and numerous requirements of practical routing and scheduling problems can be taken into account. Beside the development of models, we are involved in the design of constraint-based algorithms for resource transfer problems.

PhD projects:

Batch and Continuous Process Scheduling

Process scheduling is concerned with the short-term resource planning of multistage process plants in which several products can be produced sequentially or simultaneously. Such facilities are dedicated to the production of high-grade fine and speciality chemicals as well as active ingredients, whose sales volume is comparatively low and fluctuating. With regard to the degree of standardization it is possible to distinguish between the make-to-stock continuous production of product variants on multi-product plants and the make-to-order batch production of diverse product families on multi-purpose plant. Thus, continuous production is typically characterized by continuous process control and production in sequential campaigns, whilst batch production is frequently associated with discontinuous process control and mixed operation of different processes.

Process scheduling starts from given primary requirements for final products, which are manufactured in a series of operations on the processing units of a chemical plant. It includes the generation of a suitable set of operations (operations planning) and their timing on the processing units of the plant (operations scheduling). Numerous technological contraints must be taken into account, such as convergent or divergent production processes, lower and upper bounds for batch sizes, flexible proportions of charge materials or outputs, variable production rates or durations of operations, sequence-dependent changeover and cleaning times, limited storage capacities, as well as shelflife and quarantine times for intermediate products. Thus, process scheduling problems exhibit considerable complexity.

In our research we are developing efficient methods for the process scheduling of flexible multi-purpose and multi-product batch or continuous plants. By contrast to the monolithic models of mixed-integer programming documented in the literature, we pursue a hierarchical decomposition approach, which breaks down process scheduling into operations planning and operations scheduling. For operations planning, advanced modeling techniques and methods of mixed-integer linear and non-linear optimization are employed, whereas operations scheduling is performed using exact models and efficient heuristics. Furthermore, we investigate predictive-reactive planning approaches for process scheduling under uncertainty, which appropriately combine stochastic planning and robust scheduling procedures. For realtime applications like capable-to-promise calculations in order promising, we propose priority-rule based methods, which allow for a particularly efficient incremental dispatching of production orders.


PhD projects:

Preventive and Condition-Based Maintenance Planning

According to DIN 31051, maintenance includes "all measures for the conservation and recovery of the nominal condition as well as for the diagnosis and assessment of the actual condition of the technical devices of a system". Maintenance comprises reactive measures such as the repair or replacement of defective systems or components as well as proactive measures like inspection and preventive or condition-based maintenance or replacement. In general, the condition of a system's component can be improved upon through maintenance action. The extent of  improvement depends on the type and scope of maintenance. By maintaining a component, the system evolves into a non-deteriorated condition that is given by the structural function of the system. Maintenance planning is concerned with the decisions under which circumstances and on which components which maintenance measures should be carried out in which scope, so that an objective system in the stochastic process of system states is optimized over a finite or infinite planning horizon.

In our research we develop efficient algorithms of combinatorial as well as stochastic and simulation-based optimization for maintenance planning of complex technical systems that consist of multiple connected components. Examples of such systems are infrastructural networks such as for communication, electricity, gas, water, or traffic, but also modular systems like machines or facilities whose system performance uniquely depends on the condition of the individual components. Maintenance planning provides flexible strategies for the maintenance of individual components. More specifically, the determined maintenance policy establishes for each component and each period, dependent upon the monitored state of all the components, whether, and if so, which maintenance activities should be carried out in which scope. Assuming a finite planning horizon, we consider the cases of both binary and multi-state systems as well as deterministic and stochastic wear processes. Whilst binary systems are subject to sudden failure, which should for the most part be avoided with the help of preventive maintenance, we are investigating the case of parameter drifts in multi-state systems, which permits the modeling of continuous wear processes. For multi-state systems, condition-based maintenance policies are being researched.

PhD projects:

Warehouse Design

A project of warehouse design can be outlined in five primary phases:

  1. Establishment of the storage location policy
  2. Sizing and allocation of storage capacity to (groups of) SKUs
  3. Selection of bearing technology and layout planning
  4. Conception of the storage and retrieval strategy
  5. Technical design of the storage and retrieval system

Whilst the storage location policy defines the rules for assigning suitable storage locations to SKUs, the sizing and allocation of storage capacity determines the total number of storage bins available and assigns a set of storage bins to each SKU. Subsequently, the storage facilities and storage devices have to be chosen (bearing technology) and a physical positioning is to be assigned to each storage bin and each I/O point (layout planning). The storage and retrieval strategy defines the principles of how storage and retrieval orders are to be carried out during warehouse operation. This includes the rules for the creation of operation cycles for the conveyors and the rules applied when selecting suitable storage bins for the storage and retrieval orders. Finally, in the configuration of the physical S/R system, one has to set up the type, number, and performance parameters of the conveyors.

In our research we are developing models and methods for the capacity sizing and allocation and the S/R design phases for various combinations of storage location policies and storage and retrieval strategies. The requirements for storage capacity of the SKUs are modeled as random variables, and the arrivals of storage and retrieval orders constitute stochastic processes. For the resulting stochastic models of optimization and performance evaluation we are developing efficient mathematical programming algorithms and tailored methods for the analysis of stationary Markov processes. In further research we are investigating the interdependencies between the individual planning phases of warehouse design and the ways of linking them in a closed-loop planning approach.

PhD projects:

 

Contact  Sitemap  Imprint
© TU Clausthal 2018