Production Scheduling with Genetic Algorithms

Introduction to Genetic Algorithms

Genetic algorithms (GAs) are a class of evolutionary algorithms that simulate the process of natural selection, wherein the fittest individuals are selected for reproduction in order to produce offspring of the next generation. These algorithms reflect the principles of genetic combination and survival of the fittest, facilitating a search through a large and potentially complex solution space.

Production Scheduling Challenges

Production scheduling involves the allocation of resources over time to perform a collection of tasks. It is critical in manufacturing operations and involves complex decision-making due to the interdependencies between tasks, variability in task durations, and constraints on resources. The goal is often to optimize one or more objectives, such as minimizing total production time (makespan), balancing workload, reducing costs, or enhancing throughput.

Application of Genetic Algorithms in Production Scheduling

Genetic algorithms are particularly suited to production scheduling due to their robustness in handling complex optimization problems characterized by nonlinear relationships and multiple competing objectives. The primary advantages of applying GAs to production scheduling include:

1. Flexibility and Robustness: GAs do not require gradient information or a linear problem structure, making them highly effective in navigating the complex, multimodal landscapes typical of production environments.
2. Multi-objectivity: GAs can naturally handle multiple objectives by simply adjusting fitness evaluation strategies, which is advantageous in production settings where trade-offs between various production goals are common.
3. Adaptability: GAs can adapt to changes in the production environment, such as the introduction of new products or equipment failures, ensuring that the scheduling system remains efficient under varying conditions.

In conclusion, genetic algorithms offer a potent and flexible approach for addressing the intricate and dynamic challenges of production scheduling. Through continuous evolution and adaptation, these algorithms facilitate the discovery of superior scheduling strategies that significantly enhance manufacturing efficiency and productivity.

Scenario

In manufacturing and production, efficiency is a necessity. One of the key challenges in this sector is production planning, which involves determining the optimal sequence and timing for a set of production tasks to minimize downtime and maximize throughput. This challenge is compounded by constraints such as limited machinery, specific sequence requirements for operations, and fixed labor availability.

Our problem scenario involves scheduling two different product types through three production phases (Assembly, Test and Packaging) using a limited number of machines. Each product type has specific time requirements for each stage and a set daily production target. The goal is to minimize the total time required to complete all tasks, which directly affects the efficiency and productivity of the production process.

Genetic Algorithm Approach
Genetic Algorithms (GA) offer a robust method for tackling complex optimization problems such as production scheduling. They use mechanisms inspired by biological evolution, such as selection, crossover and mutation, to evolve a sequence of solutions towards the best solution over generations.

Script Overview
Our code uses the DEAP (Distributed Evolutionary Algorithms in Python) library, a popular toolkit for prototyping and deploying evolutionary algorithms. It starts by defining the parameters of our problem: the processing times for each stage of production for both products, the demand for each product, the number of available machines and the total number of available time slots per day.

The core of the scenario includes the following:

• Identification of Fitness and Individual in DEAP: We create a custom individual as a list of tuples where each tuple represents a task (product type, process stage, machine used and start time). The fitness function is designed to minimize the makespan, which is calculated as the latest finish time among all tasks.
• Initialization and Population Setup: Each individual in the initialization population is created by randomly assigning tasks to time slots and machines, ensuring that no machine is booked twice at the same time.

Genetic Operators

• Crossover (Two-Point): This operator randomly swaps the segments between two parental individuals, hoping to create offspring that inherit the productive traits of both parents.
• Mutation (Shuffle Indices): This introduces randomness by shuffling parts of the solution, helping to explore new areas of the solution space and avoid local optima.
• Selection (Tournament): This selects the best from a randomly chosen subset of individuals to breed the next generation, focusing evolution on the most promising solutions.

Running the Genetic Algorithm

The algorithm progresses through several generations, selecting the best solutions each time, applying crossover and mutation, and evaluating the fitness of the new generation.

Problem and Approach
Initially, the genetic algorithm rapidly converged to a local optimum where all feasible solutions had similar makespans. This indicated a lack of diversity in the population and possibly suboptimal genetic operators that were unable to effectively explore the solution space.

We evaluated several strategies to address this:

• Improving genetic operators: Developing more specialized mutation and crossover functions that respect the unique constraints of production scheduling.
• Increasing population diversity: Experimenting with larger population sizes or different initialization strategies to cover more of the solution space.
• Hybrid approaches: Combining GA with other optimization techniques such as simulated annealing to escape local optima.
• Parameter tuning: Adjusting crossover and mutation rates and the number of generations to find a better balance between exploration and exploitation.

The mathematical model provided is designed to optimize production scheduling in a factory environment where multiple products go through several stages of processing using limited resources (machines). Here’s a breakdown of what the model represents and how it functions:

Components of the Mathematical Model

Indices and Sets

• Products (i): Represents different types of products being manufactured. In this case, there are two types, Product 1 and Product 2.
• Processes (j): Represents different stages each product must pass through, such as Assembly, Testing, and Packaging.
• Machines (k): Represents individual machines available for each process. Each type of process has two machines available.
• Time Slots (t): Represents discrete units of time available for scheduling during a workday. For example, 32 time slots might represent an 8-hour day with each slot being 15 minutes.

Parameters

• Processing Time (p_{ij}): The time required to complete process j for product i. This is defined in terms of time slots.
• Daily Demand (d_i): The quantity of each product that needs to be produced daily.
• Number of Machines (m_j): The number of machines available for each process type j.

Decision Variables

• x_{ijk}^t: A binary variable that equals 1 if product i is processed in process j on machine k at time slot t, and 0 otherwise.

Objective Function

The objective is to minimize the makespan, which is the total time required to complete all scheduled tasks. Mathematically, it’s expressed as maximizing the latest end time of all tasks.

Constraints

• Demand Fulfillment: Ensures that the daily production meets the demand for each product.
• Machine Capacity: Ensures that no machine is assigned more than one task at any time slot, preventing overlap.
• Processing Sequence: Ensures that the necessary sequence of processes for each product is respected.
• Non-Preemption: Ensures that once a process starts, it continues without interruption until completion.

import random
from deap import base, creator, tools, algorithms

# Constants for the problem
PROCESS_TIMES = {'Product 1': {'Assembly': 2, 'Testing': 1, 'Packaging': 1},  # Time slots required
                 'Product 2': {'Assembly': 3, 'Testing': 2, 'Packaging': 1}}
DEMAND = {'Product 1': 30, 'Product 2': 20}
MACHINES = {'Assembly': 2, 'Testing': 2, 'Packaging': 2}
TIME_SLOTS = 32  # Total time slots available per day

# Genetic Algorithm Parameters
POP_SIZE = 100
CXPB, MUTPB, NGEN = 0.7, 0.2, 50  # Crossover probability, mutation probability, and number of generations
# Define fitness and individual
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", list, fitness=creator.FitnessMin)

toolbox = base.Toolbox()

# Individual generator
def create_individual():
    schedule = []
    for product in PROCESS_TIMES:
        for process in PROCESS_TIMES[product]:
            for _ in range(DEMAND[product]):
                machine = random.randint(1, MACHINES[process])
                time_slot = random.randint(0, TIME_SLOTS - PROCESS_TIMES[product][process])
                schedule.append((product, process, machine, time_slot))
    return schedule

toolbox.register("individual", tools.initIterate, creator.Individual, create_individual)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
# Fitness function to minimize makespan
def evaluate(individual):
    end_times = [0] * (TIME_SLOTS + 1)
    for item in individual:
        product, process, machine, start_time = item
        duration = PROCESS_TIMES[product][process]
        end_time = start_time + duration
        end_times[end_time] = max(end_times[end_time], end_time)
    makespan = max(end_times)
    return (makespan,)

toolbox.register("evaluate", evaluate)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutShuffleIndexes, indpb=0.05)
toolbox.register("select", tools.selTournament, tournsize=3)
def main():
    random.seed(42)
    pop = toolbox.population(n=POP_SIZE)
    hof = tools.HallOfFame(1)

    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("avg", np.mean)
    stats.register("min", np.min)
    stats.register("max", np.max)

    pop, log = algorithms.eaSimple(pop, toolbox, cxpb=CXPB, mutpb=MUTPB, ngen=NGEN,
                                   stats=stats, halloffame=hof, verbose=True)

    return pop, log, hof

if __name__ == "__main__":
    pop, log, hof = main()
    best_ind = hof.items[0]
    print("Best schedule found:")
    print(best_ind)
    print("With makespan:", evaluate(best_ind)[0])

The code provided implements a genetic algorithm (GA) to solve the production scheduling problem described by the mathematical model. Let’s walk through each part of the code to understand its functionality and how it applies the genetic algorithm to find an optimal scheduling solution.

Setting Up the Environment and Problem Parameters

Initially, the code defines the problem-specific parameters:

• PROCESS_TIMES: A dictionary specifying the time (in time slots) each product takes in each process.
• DEMAND: The required number of each product to be produced daily.
• MACHINES: The number of machines available for each process.
• TIME_SLOTS: Total available time slots in a day.

These parameters set the constraints and resources available for the scheduling problem.

DEAP Framework Setup

The code uses the DEAP (Distributed Evolutionary Algorithms in Python) library, which provides tools for implementing and running evolutionary algorithms:

Fitness and Individual Definition

• FitnessMin: A fitness strategy that aims to minimize a value, in this case, the makespan of the production schedule.
• Individual: Represents a potential solution in the GA. Here, an individual is a list of tuples, where each tuple represents a task scheduled on a machine at a specific time.

Toolbox Setup

• Population Initialization (create_individual): Generates an individual schedule by assigning tasks randomly to available machines and time slots, ensuring each task respects its process time and machine availability.
• Population Registration: Sets up a population of such individuals.

Fitness Function

• evaluate: This function calculates the fitness of an individual. It computes the makespan by identifying the latest time any task finishes. The fitness is the value to be minimized.

Genetic Operators

The GA uses three primary operators to evolve the population toward better solutions:

• Crossover (cxTwoPoint): A two-point crossover that swaps sections of two parents to create new offspring. This operator can mix traits from two good solutions to potentially produce a better one.
• Mutation (mutShuffleIndexes): Randomly shuffles the elements of an individual, which can introduce new variations into the population, helping to explore new areas of the solution space and avoid local optima.
• Selection (selTournament): A tournament selection method that selects the best out of a randomly chosen subset of individuals. This helps to ensure that better solutions have a higher chance of being retained for the next generation.

Running the Genetic Algorithm

• main Function:
• Initializes a random population.
• Defines a Hall of Fame to keep the best ever found individuals.
• Sets up statistical tracking to monitor the evolution process.
• Executes the GA using eaSimple, a simple evolutionary algorithm provided by DEAP, iterating through generations of selection, mating, and mutation.

Output

Results

After running the code, you will get an output like above. I have added only the last lines for simplicity.

Overview of Best Schedule Found

The output presents a list of scheduled tasks, where each task is represented as a tuple. Each tuple contains:

• The product type (Product 1 or Product 2),
• The process type (Assembly, Testing, Packaging),
• The machine number on which the task is scheduled,
• The start time slot for the task.

For example, the tuple ('Product 1', 'Assembly', 1, 13) means:

• Product 1 is scheduled for Assembly,
• On Machine 1,
• Starting at time slot 13.

Explanation of the Schedule

The output sequence lists tasks in no specific order, but each entry respects the constraints and aims to fill the demand while minimizing idle time and overlapping of tasks on the same machine. Below is a segmented view of how different processes for each product are distributed:

• Assembly of Product 1 is seen occurring multiple times across different machines and starting at various time slots such as 13, 24, 2, etc. This process distribution reflects the high demand for Product 1 and the need to utilize both available machines effectively.
• Testing and Packaging of Product 1 follow similar patterns, with testing often directly following assembly as required by the production flow. The packaging process is scheduled to ensure that all assembled and tested units are promptly packaged, avoiding any delays that might increase the makespan.
• For Product 2, the assembly starts at time slots like 4, 22, etc., reflecting a strategic spread across the available time to balance the load with Product 1’s schedule. Testing and packaging for Product 2 are also strategically placed to follow the assembly and testing stages immediately, ensuring a continuous flow.

Highlights of Efficient Scheduling

• Minimized Idle Times: By strategically scheduling tasks to start immediately after the preceding tasks finish, idle times are minimized. This effective use of available machine time contributes significantly to reducing the makespan.
• Balanced Machine Load: The algorithm schedules tasks in such a way that both machines for each process type are utilized without overloading any single machine.
• Sequence and Timing Compliance: The schedule respects the necessary sequence of processes (Assembly, then Testing, then Packaging) and ensures that the tasks do not overlap on the same machine, adhering to the operational constraints of the manufacturing process.

If you are interested in this content, you can check out my courses on Udemy and strengthen your CV with interesting projects.

Link : https://www.udemy.com/course/operations-research-optimization-projects-with-python/