Filters

Settings

Now showing1 - 2 of 2
  • Some of the metrics are blocked by your 
    consent settings
    Item type:Publication, Access status: without files ,
    Problems, Models and Complexity. Part II: Application to the DLSP
    (Springer, 2003)
    Brüggemann, Wolfgang
    ;
    Fischer, Kathrin
    ;
    Jahnke, Hermann
    In Part I of this study, we suggest to identify an operations research (OR) problem with the equivalence class of models describing the problem and enhance the standard computer-science theory of computational complexity to be applicable to this situation of an often model-based OR context. The Discrete Lot-sizing and Scheduling Problem (DLSP) is analysed here in detail to demonstrate the difficulties which can arise if these aspects are neglected and to illustrate the new theoretical concept. In addition, a new minimal model is introduced for the DLSP which makes this problem eventually amenable to a rigorous analysis of its computational complexity.Publishers.
    Publicationtype: Journal Article
      49
  • Some of the metrics are blocked by your 
    consent settings
    Item type:Publication, Access status: without files ,
    Problems, Models and Complexity. Part I: Theory
    (Springer, 2003)
    Brüggemann, Wolfgang
    ;
    Fischer, Kathrin
    ;
    Jahnke, Hermann
    The meaning of the term 'problem' in operations research (OR) deviates from the understanding in the theoretical computer sciences: While an OR problem is often conceived to be stated or represented by model formulations, a computer-science problem can be viewed as a mapping from encoded instances to solutions. Such a computer-science problem turns out to be rather similar to an OR model formulation. This ambiguity may cause difficulties if the computer-science theory of computational complexity is applied in the OR context. In OR, a specific model formulation is commonly used in the analysis of the underlying problem and the results obtained for this model are simply lifted to the problem level. But this may lead to erroneous results, if the model used is not appropriate for such an analysis of the problem. To resolve this issue, we first suggest a new precise formal definition of the term problem which is identified with an equivalence class of models describing it. Afterwards, a new definition is suggested for the size of a model which depends on the assumed encoding scheme. Only models which exhibit a minimal size with respect to a 'reasonable' encoding scheme finally turn out to be suitable for the model-based complexity analysis of an OR problem. Therefore, the appropriate choice (or if necessary the construction) of a suitable representative of an OR problem becomes an important theoretical aspect of the modelling process.
    Publicationtype: Journal Article
      48