Two of the most complex activities in production and operations management (POM) are inventory planning and operations scheduling. This chapter presents two problems related to these activities, namely, the capacitated lot-sizing and scheduling problem and the capacitated vehicle routing problem. For each of these problems, the authors discuss several solution methods, present a competitive genetic algorithm, and describe its implementation in the Java Genetic Algorithm (JGA) framework. The purpose of this chapter is to illustrate how to use JGA to model and solve complex business problems arising in POM. The authors show that JGA-based solutions are quite competitive and easier to implement than widely used methods found in the literature.
Key Terms in this Chapter
Genotype: Genetic makeup of an individual.
CLSSP: Acronym for the capacitated lot-sizing and scheduling problem. The CLSS problem is to find the number of units of a given product to be produced at a given period (production orders), and the sequence in which the production orders are to be produced in each period.
Crossover: Genetic operator that combines (mates) chromosomes (parents) to produce new ones (offspring). It is analogous to the biological reproduction.
Fitness Function: Objective function that quantifies the adaptability of an individual. Solutions with better fitness values are more likely to survive and join the next generation in a genetic algorithm. It is analogous to the fitness concept in the natural selection process.
Chromosome: Data structure (genetic code) which encodes a solution (individual) to the problem that the genetic algorithm is trying to solve.
Genetic Algorithm (GA): Stochastic (population-based) search technique, inspired in the natural selection process and used to find approximate solutions to complex optimization problems.
JGA: Acronym for Java Genetic Algorithm, a flexible and extensible computational object-oriented framework for rapid development of evolutionary algorithms for solving complex optimization problems.
CVRP: Acronym for capacitated vehicle routing problem. The CVRP consists of finding a set of at most K vehicle routes of total minimum cost, such that every route starts and ends at the depot, each customer is visited exactly once, and the sum of the demands in each vehicle route does not exceed the vehicle’s capacity.
Mutation: Genetic operator that alters one or more genes in a chromosome. Mutation is used to maintain genetic diversity in the population of individuals. It is analogous to biological mutation.
Phenotype: Features or quantifiable measurements of an individual. In a genetic algorithm, the phenotype is the value associated with the fitness function evaluation.