Understanding Genetic Algorithms

There exist different ways how you can schedule (production, process, planned) orders in PP/DS. Orders can be scheduled interactively in the detailed scheduling planning board, in the background using heuristics, or by the DS Optimizer. When orders are scheduled interactively or in the background using heuristics, the scheduling follows local optimization criteria or a simple logic, that is defined in the Strategy Profile. For example, the Strategy Profile can define that the order should be scheduled in direction forward and the next available slot can be used to schedule the order. This kind of scheduling is executed immediately for the material, or resource, or order, that has been selected. The response time of such a scheduling step is typically very short.

In contrast, the DS Optimizer takes a different approach. It is not looking at scheduling individual orders, but can only be executed for a set of resources. Taking all orders that are to be scheduled on these selected resources into account. The DS Optimizer is guided by global optimization criteria. That means, it does look at the complete scheduling result of all orders and evaluates global fitness criteria like the sum of all order delays or the total setup time based on the sequence of all orders in the schedule. Depending on the number of orders that have been scheduled executing the DS Optimizer can take seconds, minutes, or even hours.

Why are optimization algorithms required for scheduling tasks? What makes scheduling difficult and why is it so difficult to obtain the best possible setup sequence? Actually, it can depend on your business requirements, whether an optimization algorithm is required to solve your scheduling tasks or whether a simple heuristic can suffice. If there are no significant setup operations required between the production of different products and your objective is to keep a high service level. That is to produce all orders on time, then the most simple logic is to sort all your orders by their requirement date to obtain the best possible sequence to match your objective.

However, in most cases, the scenario is not that simple and the objective cannot be accomplished that easily. There are typically many different objectives, which are conflicting. Conflicting means that improving one objective can deteriorate another objective. Objectives in scheduling can be:

• Choose the right sequence: setup optimization
• Produce at the lowest cost: mode selection
• Increase service levels: avoid delaying orders
• Improve margin: select most profitable orders

What makes scheduling difficult is its complexity.

Imagine a simple scheduling task. You must decide about the sequence of three orders A, B, and C on a single resource. There exist six potential schedules: ABC, ACB, BAC, BCA, CAB, and CBA. Mathematically, this is expressed as 3!. While it is simple to pick the best sequence in this case, it gets more difficult very soon. If you must schedule 10 orders on a single resource, there are already 3,628,800 potential sequences and with 15 orders, this number increases to more than 1,307 billion potential sequences. In real life, there are even more orders on more resources to schedule, which make the use of a smart algorithm mandatory.

How long does it take to count all potential solutions to select the best one?

Assume that it takes one millisecond to evaluate a single solution. Since there exist six potential solutions for three orders, it takes six milliseconds to evaluate all potential combinations. For five orders, this number increases to 0.12 seconds and for 10 orders it takes an hour. However, for 20 orders, it could not be computed anymore in due time. Based on the preceding assumptions, it would take more than 77 million years.

How are solutions generated and evaluated?

You can compare the search for a reasonable schedule with finding the right path in a maze. You must make sequential decisions on whether to turn left or right and, if you have made the decisions in the right sequence, you will eventually have found your way out. You can typically include probabilities into your decision-making. For example, you would change the direction at some point, if you have run in circles. Likewise, any smart scheduling algorithm has to consider knowledge derived from previous decisions and must evaluate the outcome.

Simply speaking, the DS optimization algorithm schedules all orders one by one in a random sequence. The resultant schedule is evaluated and based on this evaluation, the DS Optimizer can try another sequence. This process continues until a termination criteria is met.

What is the difference between heuristics and optimization?

Creating one solution can be done by a simple heuristic. Any sorting algorithm would be a heuristic that allows you to create a sequence of orders based on a predefined criteria. For example, you can sort all orders by their requirement date to minimize the delay of each individual order. Calculating all potential sequences and evaluating these to choose the best one would be an exact optimization algorithm. But based on the complexity and time required, this is not an option.

Therefore, an algorithm is needed that calculates many solutions in a smart way to obtain a better solution than a simple heuristic and comes as close as possible to the exact optimal solution. The PP/DS Optimizer represents such an algorithm. When designing it, the following considerations have been made:

• How should solutions be generated?
• Which solutions are generated?
• How to allocate the available time to the different algorithmic steps?
• How can the algorithm improve generated solutions?

A genetic algorithm is a stochastic search algorithm based on the evolutionary process of natural systems. It has been applied to many optimization problems. For example traveling salesman problems, bin packing, scheduling, sequencing, facility layout problems, and facility location problems.

Different from local search strategies, genetic algorithms can accept temporary solutions with a worse objective function value, in comparison to the preceding solution to overcome local optima and to find the global one. However, since genetic algorithms are heuristics, the optimal solution is not necessarily found, but in most cases at least a very good feasible solution is obtained.

Since genetic algorithms are stochastic search algorithms working with probabilities, in general they can come up with different solutions, even if they are started with the same initial solution and the same parameter settings. This does not apply to the genetic algorithm used in the PP/DS optimizer. This algorithm is deterministic, that means it returns exactly the same solution, if it is started in the same planning situation with the same parameters. This is required to allow supportability, which means the behavior of the algorithm must be completely reproducible for any customer scenario and situation.

• Genetic algorithms are based on the evolutionary processes of natural systems.
• The algorithm creates a population of initial solutions.
• Based on initial solutions, the algorithm produces new ones.
• The process continues through many generations where, in general, the quality of the solution is improved.
• The algorithm ends when a specific termination criterion is reached (for example, when the runtime has reached its limit).
• Genetic algorithms are stochastic search algorithms.

Genetic algorithms work in the following way:

Genetic algorithms are population-based algorithms. A population consists of several individuals, where each individual represents a solution to the scheduling problem, for example a specific sequence of orders on a resource. A population of a specific size represents a generation. For each individual in a generation, the algorithm calculates its fitness value. The fitness value represents how much the individual (the solution of the scheduling problem) meets the objective criteria (the business requirements). If a metric is used that aims at minimizing the objective criteria (for example, minimization of delays or minimization of setup times) the individual is better, the lower its fitness value.

The genetic algorithm selects the best solutions for reproduction and discards the worst solutions. This principal is called survival of the fittest in evolutionary theory. From one generation, the next generation is created by keeping and modifying the best solutions and trying to generate even better solutions. This process of creating new generations with even better individuals (=solutions) is continued as long as time permits. The best individual (=solution) is returned at the end of the process.

Basic genetic operators to create a new individual for the next generation based on one or more individuals from the previous generation are mutation and crossover.

A mutation is typically a (small or minor) change to an existing solution. In a scheduling problem, a mutation can be the exchange of the position of two orders. A crossover is typically a more significant change of an individual. In a scheduling problem, a crossover can be a new solution, that takes the first half of the order sequence of one individual/parent and the second half of the order sequence of another individual/parent.

Next, the logic of a genetic algorithm is explained by a flow shop sequencing problem:

• N orders must be scheduled on M resources.
• Each order consists of M operations.
• Each of the operations requires a different resource.
• All orders are processed in the same processing order on all resources.

The following assumptions apply to the following example:

• All orders are available at time zero.
• Setup times for operations are included in processing times.
• The sequence of all operations is identical for all resources.
• The objective is to minimize makespan.

The genetic algorithm can proceed as follows: Assuming that the size of one generation is four, the algorithm would first create the initial population. This could be done randomly or using simple heuristics like applying various sorting criteria. The algorithm can come up with the following initial population:

• 1-3-4-5-2 → makespan: 11
• 1-2-3-4-5 → makespan: 12
• 2-4-5-3-1 → makespan: 13
• 2-3-5-4-1 → makespan: 15

Now, the algorithm must define how the next generation is created based on this information. Obviously, solutions that have a lower makespan are more likely to generate better solutions using mutation or crossover than solutions with a higher makespan. The selection of individuals which are used as "parents" can be done in different ways. Only one option is described here.

For all members in a population the value of the objective function (in this example, the makespan), is calculated. From this, the lowest makespan is determined and gets the highest fitness value fmax. The fitness values of each other member in the population result from the difference (d) to the fitness value of its direct predecessor in the sorted list. This is done to ensure that the probability of a selection for a schedule with lower makespan is high. The size of the decrement (d) influences the probability of the selection. The individual with the highest makespan has the lowest fitness value fmin. Note that for mathematical reasons, the value fmin must be larger than zero.

Fitness values in example (with fmax=20, d=5, fmin=5):

• f(1-3-4-5-2) = 20
• f(1-2-3-4-5) = 15
• f(2-4-5-3-1) = 10
• f(2-3-5-4-1) = 5

The total fitness of the population is 50 in this example (sum of fitness of all individuals in the population). The most common reproduction/selection probability is given as the quotient between the fitness value of the individual and the total fitness of the population. In this numerical example, the selection probability for the different individual is calculated as follows:

• Prob(1-3-4-5-2) = 20/50 = 40 %
• Prob(1-2-3-4-5) = 15/50 = 30 %
• Prob(2-4-5-3-1) = 10/50 = 20 %
• Prob(2-3-5-4-1) = 5/50 = 10 %

The selection probability represents the chance of an individual being selected to remain in the next generation. It is proportional to the fitness of the individual. The same holds for the selection of an individual as a parent for a crossover operator. Individuals with lower makespan have a higher survival/selection probability than those with low fitness values. Next, a random variable between 0 and 1 is generated, and, if it is below 0.4, then individual 1-3-4-5-2 is selected. If the random variable is between 0.4 and 0.7, then individual 1-2-3-4-5 is chosen. If it is between 0.7 and 0.9, the individual 2-4-5-3-1 is selected, and if it is larger than 0.9, then individual 2-3-5-4-1 is reproduced.

Next, the mutation operator must be chosen, that defines how a new individual (=solution) is created based on its parent. An example for a mutation operator is the following:

1. Choose one parent of the population (example: parent 1-2-3-4-5).
2. Choose randomly two positions in the order sequence of this parent (example: positions 2 and 4).
3. A new sequence of the values within this interval is randomly generated (example: old sequence 2-3-4 → new sequence 4-2-3).
4. Result: New individual with order sequence 1-4-2-3-5.

This process can continue for many generations. The algorithm terminates when a termination criteria (for example, a defined runtime or a specified number of generations) is reached. At the end of the process, the individual with the best fitness value is returned.

Advantages of genetic algorithms are a high performance in scheduling problems. The DS optimizer only generates feasible solutions with a few exceptions. Its termination criteria is runtime.

One approach to deal with complexity is decomposition. The idea of decomposition is to rather solve some (easier) smaller problems instead of one (difficult) big problem. To decompose an overall planning problem it must be divided into subproblems, then to solve these individual subproblems and combine their individual solutions to an overall solution.

The first task in a decomposition approach is to define the subproblem. Afterward, this subproblem must be solved. In principle, the same algorithmic approach can be used to tackle a subproblem than is suitable to solve the original problem. Typically, not the full solution of the subproblem, but only a part is considered as the basis for defining the next subproblem. Thus, its solution is then (partly) fixed and a second subproblem is defined based on the fixed solution of the first subproblem.

This process continues until an overall solution is found for the full problem.

This concept can be applied to the DS optimization algorithm in two dimensions. The first dimension is resource decomposition. In resource decomposition, the full problem is divided into one problem that includes only bottleneck resources and the rest.

This approach follows the theory of constraints, that optimization is only required on the bottleneck resource. The first subproblem would then be the scheduling of orders only on the bottleneck resource(s). The order sequence on the bottleneck resource(s) would afterward be fixed and the second subproblem would solve the scheduling of all resources, taking the sequence of the bottleneck resource(s) as an additional constraint into account. Theoretically, this should align the orders based on their sequence on the bottleneck(s).

The second dimension into which the decomposition approach can be applied in DS optimization is time decomposition.

In a time decomposition approach, the overall problem can be divided into time windows. The first time window has to deal with scheduling the earliest n operations. The second time window has to schedule the next n operations. This can continue until all operations have been scheduled. Typically, an overlap of time windows is defined to avoid artefacts being created at the border between time windows. That means, the second time window only considers n-m operations as planned by the first time window (the n-m earliest operations with m defining the number of operations that consecutive time windows overlap).