Home | deutsch  | Legals | Data Protection | Sitemap | KIT

Intralogistics and Production

Modeling of online problems and performance criteria for online algorithms
Lagersystem
Inventory and material flow systems bear many online problems, ...
Packungsproblem
... while in packing problems new items come along continuously, ...
Transportproblem
... and in routing and transportation problems new jobs are released over time.

Requirements in complex production and logistics environments

  • High utilization of (expensive) assets and efficient personnel usage
  • Regulatory requirements (working time regulations, ...)
  • Reaction on peaks / exception handling
  • Systems analysis and decision evaluation
  • Decision support in planning and operational execution

Typical research issues

  • Production planning (machine scheduling and order sequencing)
  • Inventory management (material flow control and order handling)
  • Spatial and temporal consolidation (planning of packings)
  • Service levels and delivery guarantees

Modeling of online problems and performance criteria for online algorithms

Online optimization is concerned with the optimization of systems that obey a continuous admission of information and data. In contrast to classical offline optimization which assumes all data are known before solution algorithms are applied, dynamically released data have to be incorporated into an online algorithm's proceeding. Online optimization has a wide variety of application areas from different domains including:

  • inventory and material flow systems
  • packing problems
  • transportation problems
  • rent-or-buy problems

The common performance criteria for online algorithms by now is the so-called competitive ratio. This ratio relates the objective function value of the online algorithm to the objective function value of an offline algorithm which would have known the complete sequence of input data. Since the competitive ratio is determined on the basis of a worst case analysis, its practical significance is not undisputable. In fact, often one observes the effect that an online algorithm with relatively good competitive ratio performs poorly for problem typical input sequences. The reason for this can be easily traced back to the design of such algorithms with the exclusive goal of achieving a good competitive ratio while ignoring typical input scenarios. A further shortcoming of competitive analysis is the disregard of real world requirements: In many practical problems, one postulates short computing times of soultion algorithms as well as limited computing resources.

The target of our research activites in the area of online optimization consists of the development of a comprehensive framework for modeling and analysis of online problems. On the one hand,this framework should capture basic structural properties of online problems; on the other hand the application of alternative performance criteria for online problems shall justify an online algorithm's practical applicability. Besides information, these performance criteria will also include computing time and space as a scarce resource of online optimization.

A further goal of our research activities lies in the incorporation of so-called lookaheads. This term expresses the existence of a set of future information that can be exploited by an online algorithm in performing its decision. Thus, online problems with lookahead stand between the two extreme cases of offline and online optimization. In theory, online algorithms with lookahead have not experienced much attention, although they verifiably lead to better objective function values in many problem instances, e.g., in transportation planning. In the course of our research activities, we analyze which dependencies exist between the problem formulation and expected lookahead effects.

Contact person

Fabian Dunke