Job shop scheduling is a challenging problem for mathematical programming. Yet, when applicable, the operational impact can be great. In today’s blog post I will contribute to this topic with a technical example covering genetic job scheduling.

A simple job shop machine task scheduling problem

The example that I suggest comprises 3 machines (M1, M2, and M3) and 5 tasks (T1, T2, T3, T4, and T5). The jobs must be processed in a job shop. Each task can be processed on any machine, but there are certain constraints that limit the possible sequence of tasks on each machine.

For example, the constraints might be as follows:

• T1 must be processed before T2 on M1
• T4 must be processed before T5 on M2
• T2 and T3 cannot be processed on the same machine

I now want to find a task schedule on each machine that minimizes the total processing time for all tasks.

Job shop task scheduling with genetic algorithms

To solve this problem using a genetic algorithm I represent a schedule as a sequence of integers. Each integer represents the task to be processed next. For example, a schedule [1, 2, 3, 4, 5] means that we process task 1 on machine 1, followed by task 2 on machine 2, followed by task 3 on machine 3, and so on.

We can use a simple fitness function that calculates the total processing time for a given schedule, taking into account the constraints. For example, we might calculate the processing time as follows:

• For each machine, calculate the processing time as the sum of the processing times of all tasks assigned to that machine.
• If there are any constraint violations (e.g., if T2 and T3 are assigned to the same machine), add a penalty to the processing time.
• The fitness of a schedule is the negative of the processing time.

We can then use a genetic algorithm to generate and evolve schedules until we find a good one.

Genetic scheduling algorithm example

Here’s an example of how the algorithm might work:

1. Generate an initial population of schedules, each consisting of a random sequence of tasks assigned to machines.
2. Calculate the fitness of each schedule using the fitness function.
3. Select a subset of the population to breed the next generation of schedules, using a selection method such as tournament selection.
4. Breed new schedules using crossover and mutation operators.
5. Replace the old population with the new population, and repeat steps 2-4 for a certain number of generations.
6. The best schedule found is the one with the highest fitness value.

Job shop scheduling problems are known to be NP-hard, which means that finding the optimal solution is computationally intractable for large problem instances. As a result, genetic algorithms may take a long time to converge, or may not be able to find the optimal solution at all.

Final remarks and related job shop scheduling content

Job shop scheduling is a challenging subject. Mathematical programming, and in this case, genetic algorithms, can be effective in some cases. In other cases problems can be too complex to solve analytically with reasonable effort. Should this be the case discrete-event simulation can help overcome some of the challenges of mathematical programming application. The following SCDA blog post describes the challenges of job shop scheduling:

• Link: Job shop scheduling challenges

You can read more about simulation, especially disrete-event simulation, in the following SCDA publications. Simulation modelling can implement scheduling solutions that can overcome those challenges of mathematical programming that make it unfit for application in real-world problems.

• Link: Job shop simulation with salabim in Python
• Link: Job shop simulation in SimPy
• Link: Visualizing SimPy job shop simulation

Constraint programming is another approach to job shop scheduling that you can take. Here is an example that can get you started:

• Link: Constraint programming with Google ortools

Linnart Felkl

Data scientist focusing on simulation, optimization and modeling in R, SQL, VBA and Python