Problem description
One machine, n workpieces, the machine can only process one workpiece at a time, find the optimal solution.
| Artifact | A | B | C | D | E | F | G | H | I |
|---|---|---|---|---|---|---|---|---|---|
| Workpiece number | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| Processing time | 4 | 7 | 6 | 5 | 8 | 3 | 5 | 5 | 10 |
| Arrival time | 3 | 2 | 4 | 5 | 3 | 2 | 1 | 8 | 6 |
| Delivery time | 10 | 15 | 30 | 24 | 14 | 13 | 20 | 18 | 10 |
Objective function
Minimize total delivery delay time
Operation results
Best scheduling order: [6, 5, 7, 3, 0, 2, 1, 4, 8] Minimum delivery delay time: 111
python code
import math
import random
import numpy as np
import matplotlib.pyplot as plt
#Define genetic algorithm parameters
POP_SIZE = 100 # Population size
MAX_GEN = 100 # Maximum number of iterations
CROSSOVER_RATE = 0.7 # Crossover probability
MUTATION_RATE = 0.2 # Mutation probability
# Randomly generate initial population
def gen_init_pop(pop_size):
population = []
for _ in range(pop_size):
random.shuffle(job)
population.append(list(job))
return population
# Calculate the fitness of the chromosome (makespan) with minimizing the delivery delay as the objective function. What is calculated here is the total delivery delay time.
def fitness(job):
n = len(job)
accu_pro_times = [0] * n # Accumulated processing time
accu_pro_times[0] = pro_times[job[0]] + arr_times[job[0]]
for i in range(1, n):
accu_pro_times[i] = pro_times[job[i]] + accu_pro_times[i - 1] if arr_times[job[i]] <= accu_pro_times[
i - 1] else arr_times[job[i]] + pro_times[job[i]]
delay_time = sum([max(accu_pro_times[i] - deadlines[i], 0) for i in range(n)])
return delay_time
# Select the parent generation, here select POP_SIZE/2 as the parent generation
def selection(pop):
fitness_values = [1 / fitness(job) for job in pop] # Taking minimizing the total delivery delay as the objective function, here the minimization problem is transformed into a maximization problem
total_fitness = sum(fitness_values)
prob = [fitness_value / total_fitness for fitness_value in fitness_values] # Roulette, here is the probability of each fitness value being selected
# Randomly extract size elements from the interval [0, len(pop)) according to the probability distribution prob, and repeated extraction is not allowed, that is, roulette selection
selected_indices = np.random.choice(len(pop), size=POP_SIZE // 2, p=prob, replace=False)
return [pop[i] for i in selected_indices]
# Crossover operation This is a single point crossover
def crossover(job_p1, job_p2):
cross_point = random.randint(1, len(job_p1) - 1)
job_c1 = job_p1[:cross_point] + [gene for gene in job_p2 if gene not in job_p1[:cross_point]]
job_c2 = job_p2[:cross_point] + [gene for gene in job_p1 if gene not in job_p2[:cross_point]]
return job_c1, job_c2
# Mutation operation
def mutation(job):
index1, index2 = random.sample(range(len(job)), 2)
job[index1], job[index2] = job[index2], job[index1]
return job
# Main genetic algorithm loop
def GA():
# Create an empty list to store the fitness value of each generation
best_job = job # Get the best individual
# "makespan" refers to the total time required to complete the entire production job or production order, usually measured in units of time (such as hours or minutes).
best_makespan = fitness(job) # Get the fitness value of the best individual
fitness_history = [best_makespan]
pop = gen_init_pop(POP_SIZE)
for _ in range(1, MAX_GEN + 1):
pop = selection(pop) # select
new_population = []
while len(new_population) < POP_SIZE:
parent1, parent2 = random.sample(pop, 2) # Sampling 2 without repeating
if random.random() < CROSSOVER_RATE:
child1, child2 = crossover(parent1, parent2) # crossover
new_population.extend([child1, child2])
else:
new_population.extend([parent1, parent2])
pop = [mutation(job) if random.random() < MUTATION_RATE else job for job in new_population]
best_gen_job = min(pop, key=lambda x: fitness(x))
best_gen_makespan = fitness(best_gen_job) # Obtain the fitness value of the best individual in each iteration
if best_gen_makespan < best_makespan: # Update the minimum fitness value
best_makespan = best_gen_makespan
best_job = best_gen_job
fitness_history.append(best_makespan) # Save the results of this iteration to fitness_history (used to draw the iteration curve)
# Draw iteration curve graph
plt.plot(range(MAX_GEN + 1), fitness_history)
plt.xlabel('Generation')
plt.ylabel('Fitness Value')
plt.title('Genetic Algorithm Convergence')
plt.show()
return best_job, best_makespan
def plot_gantt(job, pro_times, arr_times):
# Calculate the start time and end time of each workpiece
start_time = [arr_times[0]] # The start time of the first workpiece is 0
end_time = [start_time[0] + pro_times[0]]
for i in range(1, len(job)):
start_time.append(max(end_time[i - 1], arr_times[i]))
end_time.append(start_time[i] + pro_times[i])
# # Draw a Gantt chart
plt.figure(figsize=(10, 7))
plt.barh(job, pro_times, left=start_time, color='b', label='Processing Time') # Processing time
plt.barh(job, [st - ed for st, ed in zip(start_time, [0] + end_time[:-1])], left=start_time,
color='g', label='Idle Time') # Idle time
plt.xlabel('Time')
plt.ylabel('Jobs')
plt.title('Gantt Chart')
plt.legend()
plt.grid(axis='x')
# Display Gantt chart
plt.show()
if __name__ == '__main__':
# Define the workpiece and processing time of the single-machine scheduling problem
job = [0, 1, 2, 3, 4, 5, 6, 7, 8] # workpiece
pro_times = [4, 7, 6, 5, 8, 3, 5, 5, 10] # Processing time
arr_times = [3, 2, 4, 5, 3, 2, 1, 8, 6] # Arrival time
deadlines = [10, 15, 30, 24, 14, 13, 20, 18, 10] # Delivery date
best_job, best_makespan = GA()
best_pro_times = [pro_times[best_job[i]] for i in range(len(best_job))]
best_arr_times = [arr_times[best_job[i]] for i in range(len(best_job))]
print("Best scheduling order:", best_job)
print("Minimum delivery delay time:", best_makespan)
plot_gantt(best_job, best_pro_times, best_arr_times)