Identifikation und Komponentenanalyse für geeignete Metaheuristiken für kapazitierte mehrstufige Losgrößenplanungsprobleme im Supply Chain Management

A very important task when planning supply chains is how to determine “when and how much of a product to produce such that the setup, production and handling costs are minimized” (i.e. a Lot Sizing Problem - LSP) (Karimi et al., 2003). A variant of this problem, that is even harder to solve (i.e. NP-Hard), takes into consideration multiple production levels and capacity constraints (Multi-Level Capacitated Lot Sizing Problems - MLCLSP). Given that exact methods can have prohibitive execution time, approximation methods (e.g. meta-heuristics) are an often used as an alternative. With regard to the latter method, there are currently tens or even hundreds of different metaphors and meta-heuristics (Baheshti & Shamsuddin, 2013) (Xing & Gao, 2014), which claim they have better results in certain types of problems. However, it is unclear how these better results are actually achieved. Therefore, it is argued in literature that a component analysis of current meta-heuristics should be performed for the different classes of problems (Sörensen, 2013), in order (i) to understand the contribution of each component (i.e. operators) for the search success, as well as (ii) to place this field on a more scientific foundation (Watson et al., 2006). Then, for example, it is possible to propose an optimized algorithm which contains the most relevant components for a specific class of problems.

Given the importance, necessity and possible consequences of such an analysis, this thesis should target at (i) the identification of suitable meta-heuristics to solve  MLCLSP problems – i.e. which achieve close-to-optimal solutions in a feasible timeframe; and, (ii) the component analysis of the identified meta-heuristic, following the methodology performed by Watson et al. (Watson et al., 2006). In order to realize this project, the following activities should be performed:

  1. Literature review to identify the most relevant meta-heuristics for MLCLSP problems and selection of one meta-heuristic for further usage;
  2. Selecting the components to investigate its relevance during the search process, taking into consideration two or more scenarios. In accordance to Watson’s methodology, the following steps must be performed:

    1. Select other three or more basic meta-heuristics to gradually extend them by incorporating the components of the meta-heuristic selected in step (i);
    2. Perform experiments on each of the basic meta-heuristics to determine the best parameter configuration for each scenario;
    3. Perform experiments on each meta-heuristic for every combination of the components and analyze (1) the run-time costs per iteration when considering different combinations of components; (2) the solution quality; (3) which components (or their combinations) collaborate more for intensification, diversification or both of them.
  3. Based on the analysis performed on step (ii), identifying the collaboration and relevance of each component to the search process in MLCLSPs.

The main contribution of this work is the identification of the components (which compose the most relevant meta-heuristics for MLCLSP) that significantly collaborate to achieve good results, as well as determining the role that each of them play during the search process.

References:

  1. Baheshti, Z. and Shamsuddin, S. M. H. (2013) A Review of Population-based Meta-Heuristic Algorithm, International Journal of Advanced Soft Computing Applications, v. 5, n. 1.
  2. Karimi, B., Ghomi, S.M.T.F., Wilson, J.M. (2003) The capacitated lot sizing problem: a review of models and algorithms, Omega – The international journal of Management Scince, v. 31, n. 5, pp. 365-378.
  3. Sörensen, K. (2013), Metaheuristics—the metaphor exposed, International Transactions in Operational Research, doi: 10.1111/itor.12001.
  4. Watson, J.-P., Howe, A.E. and Whitley, L.D. (2006) Deconstructing Nowicki and Smutnicki's i-TSAB Tabu Search Algorithm for the Job-Shop Scheduling Problem, Computers and Operations Research, v. 33, n. 9, pp. 2623-2644.
  5. Xing, B. and Gao, W.-J. (2014) Innovative Computational Intelligence: A Rough Guide to 134 Clever Algorithms, Intelligent Systems Reference Library, v. 62.