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

Additionally, libraries can receive an extra 5% discount. Learn More

Additionally, libraries can receive an extra 5% discount. Learn More

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