Receive a 20% Discount on All Purchases Directly Through IGI Global's Online Bookstore

Nicolas Zufferey (University of Geneva, Switzerland), David Dal Molin (IPros, Switzerland), Rémy Glardon (IPros, Switzerland) and Christos Tsagkalidis (IPros, Switzerland)

Copyright: © 2018
|Pages: 15

DOI: 10.4018/978-1-5225-2944-6.ch013

Chapter Preview

TopAs presented in (Zufferey, 2015), let *f* be an objective function that has to be minimized (e.g., a production cost, a shortage function, a sum of lateness and/or earliness penalties) over a solution space (i.e., the set of all the possible solutions to a problem). A solution *s* is optimal for *f* if there is no better solution than it; that is, there is no solution *s’* such that *f(s’)* < *f(s)*. An *exact* method guarantees the optimality of the provided solution. However, for a large number of applications and most real-life optimization problems (as for the studied problem (P)), such methods need a prohibitive amount of time to find an optimal solution, because such problems are *NP-hard* (Garey & Johnson, 1979). For these difficult problems, one should prefer to quickly find a satisfying solution, which is the goal of heuristic and metaheuristic solution methods. The reader is referred to (Blum & Roli, 2003; Gendreau & Potvin, 2010) for accurate information on several metaheuristics, and to (Zufferey, 2012; Hertz & Widmer, 2003) for general guidelines on how to adapt them efficiently to various types of problems. There also exists a family of algorithms that efficiently integrate metaheuristics and exact methods in a single approach. For a survey on such methods, the reader is referred to (Dumitrescu & Stuezle, 2003) and to (Puchinger & Raidl, 2005).

Inventory Management: Policy used in a company to manage its stocks.

Meta/Heuristic: Method able to generate a satisfying solution to an optimization problem, without any guarantee on optimality, but in a reasonable amount of time. Such methods are appropriate for NP-hard problems.

Exact Method: Method able to find an optimal solution to an optimization problem. Such method are not appropriate for a NP-hard problem, except if its size (e.g., number of decision variables) is small.

Simulation: Computer tool used to reproduce a sequence of events, which are not all deterministic (i.e., some of these events are stochastic).

Local Search Algorithm: Meta/heuristic that starts from an initial solution, and then tries to improve is iteratively, by performing a sequence of modifications.

Job Scheduling: Problem for which various jobs have to be sequenced, for instance, on a production resource (typically a machine or a production line).

Stochasticity: Refers to the non-deterministic elements of a problem.

Reorder-Point Policy: Specific inventory management approach, where an order is triggered if the available stock reaches a specific level, called the reorder point.

Search this Book:

Reset

Copyright © 1988-2018, IGI Global - All Rights Reserved