問題描述
m臺相同的機(jī)器，n個工件，每個工件有1道工序，可按照任意的工序?yàn)槊總€工件分配一臺機(jī)器進(jìn)行加工
| 工件 | A | B | C | D | E | F | G | H | I |
|---|---|---|---|---|---|---|---|---|---|
| 工件編號 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 加工時間 | 4 | 7 | 6 | 5 | 8 | 3 | 5 | 5 | 10 |
| 到達(dá)時間 | 3 | 2 | 4 | 5 | 3 | 2 | 1 | 8 | 6 |
| 交貨期 | 10 | 15 | 30 | 24 | 14 | 13 | 20 | 18 | 10 |
設(shè)備數(shù)目：3
目標(biāo)函數(shù)
最小化交貨期總延時時間
編碼說明
記機(jī)器數(shù)為m，從0開始編號為0,1,...,m-1，記工件數(shù)為n，同樣從0開始編號。
定義兩個變量job_id和job，前者表示工件的加工順序（不是嚴(yán)格意義上的先加工A再加工B這種順序，這里的每個工件都是獨(dú)立的，整一個id只是為了再分配完機(jī)器之后自然就能選出一種加工順序），后者表示每個工件用哪臺機(jī)器加工。
例如，job_id=[4, 0, 5, 8, 1, 6, 2, 7, 3]，job=[0, 1, 2, 2, 1, 0, 2, 1, 0]表示“編號為4的工件被分配給了編號為0的機(jī)器”，“編號為0的工件被分配給了編號為1的機(jī)器”，編號為0的機(jī)器上工件加工的先后順序?yàn)?code>4,6,3，其余類推。
注意，并行機(jī)調(diào)度問題里邊對于染色體的編碼一般分為機(jī)器選擇部分和工件排序部分，機(jī)器選擇部分，就是正常這里應(yīng)該是先給工件分配機(jī)器，再對每臺工件上分配的機(jī)器進(jìn)行排序，但是我這個代碼里就是先直接對工件進(jìn)行亂序然后再選擇機(jī)器，乍一聽好像最后的效果差不多，但是看代碼就會知道，我代碼里是對job_id進(jìn)行亂序之后，直接就一種群為單位進(jìn)行選擇交叉變異了。即，一個job_id值對應(yīng)一個種群（而非一個個體，但是理論上應(yīng)該是每個個體對對飲過一個不同的順序），就可能會導(dǎo)致處理大規(guī)模問題的時候時間復(fù)雜度太高（這里確實(shí)是偷懶了但是我這兩天看代碼真的看麻了5555，菜是原罪），有能力的好兄弟改好了可以踢我一下。
具體思路可以看這篇：https://blog.csdn.net/qq_38361726/article/details/120669250
運(yùn)算結(jié)果
最佳加工順序： [4, 0, 5, 8, 1, 6, 2, 7, 3]
最佳調(diào)度分配： [0, 1, 2, 2, 1, 0, 2, 1, 0]
最小交貨期延時時間： 7
文章來源：http://www.zghlxwxcb.cn/news/detail-745969.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-745969.html
python代碼
import random
import numpy as np
import matplotlib.pyplot as plt
import copy
# 定義遺傳算法參數(shù)
POP_SIZE = 100 # 種群大小
MAX_GEN = 100 # 最大迭代次數(shù)
CROSSOVER_RATE = 0.7 # 交叉概率
MUTATION_RATE = 0.2 # 變異概率
def sort_by_id(id, sequence):
# 根據(jù)id對sequence進(jìn)行排序
new_sequence = sequence[:]
for i in range(len(id)):
sequence[i] = new_sequence[id[i]]
# 隨機(jī)生成初始種群，這里的每個個體表示第i個工件選擇在第choose[i]臺機(jī)器進(jìn)行加工，工件和機(jī)器編碼都是從0開始
def get_init_pop(pop_size):
pop = []
for _ in range(pop_size):
choose = []
for _ in range(len(job_id)):
choose.append(random.randint(0, machine_num - 1))
pop.append(list(choose))
return pop
# 計(jì)算染色體的適應(yīng)度（makespan） 以最小化交貨期延時為目標(biāo)函數(shù)，這里計(jì)算的是交貨期總延時時間
def fitness(job):
delay_times = [[] for _ in range(machine_num)] # 每個工件超過交貨期的延時時間
finish_times = [[] for _ in range(machine_num)] # 每個工件完成加工的時間點(diǎn)
for i in range(len(job)):
if finish_times[job[i]]:
finish_times[job[i]].append(
pro_times[job_id[i]] + max(finish_times[job[i]][-1], arr_times[job_id[i]]))
else:
finish_times[job[i]].append(pro_times[job_id[i]] + arr_times[job_id[i]])
delay_times[job[i]].append(max(finish_times[job[i]][-1] - deadlines[job_id[i]], 0))
return sum(element for sublist in delay_times for element in sublist)
# 選擇父代，這里選擇POP_SIZE/2個作為父代
def selection(pop):
fitness_values = [1 / fitness(job) for job in pop] # 以最小化交貨期總延時為目標(biāo)函數(shù)，這里把最小化問題轉(zhuǎn)變?yōu)樽畲蠡瘑栴}
total_fitness = sum(fitness_values)
prob = [fitness_value / total_fitness for fitness_value in fitness_values] # 輪盤賭，這里是每個適應(yīng)度值被選中的概率
# 按概率分布prob從區(qū)間[0,len(pop))中隨機(jī)抽取size個元素，不允許重復(fù)抽取，即輪盤賭選擇
selected_indices = np.random.choice(len(pop), size=POP_SIZE // 2, p=prob, replace=False)
return [pop[i] for i in selected_indices]
# 交叉操作 這里是單點(diǎn)交叉
def crossover(job_p1, job_p2):
cross_point = random.randint(1, len(job_p1) - 1)
job_c1 = job_p1[:cross_point] + job_p2[cross_point:]
job_c2 = job_p2[:cross_point] + job_p1[cross_point:]
return job_c1, job_c2
# 變異操作
def mutation(job):
index = random.randint(0, len(job) - 1)
job[index] = random.randint(0, machine_num - 1) # 這樣的話變異概率可以設(shè)置得大一點(diǎn)，因?yàn)閷?shí)際的變異概率是MUTATION_RATE*(machine_num-1)/machine_num
return job
# 主遺傳算法循環(huán)
# 以最小化延遲交貨時間為目標(biāo)函數(shù)
# TODO: 沒有考慮各機(jī)器的負(fù)載均衡
def GA(is_shuffle): # 工件加工順序是否為無序
best_id = job_id # 初始化job_id
best_job = [0, 0, 0, 0, 0, 0, 0, 0, 0] # 獲得最佳個體
# "makespan" 是指完成整個生產(chǎn)作業(yè)或生產(chǎn)訂單所需的總時間，通常以單位時間（例如小時或分鐘）來衡量。
best_makespan = fitness(best_job) # 獲得最佳個體的適應(yīng)度值
# 創(chuàng)建一個空列表來存儲每代的適應(yīng)度值
fitness_history = [best_makespan]
pop = get_init_pop(POP_SIZE)
for _ in range(1, MAX_GEN + 1):
if is_shuffle:
random.shuffle(job_id)
pop = selection(pop) # 選擇
new_population = []
while len(new_population) < POP_SIZE:
parent1, parent2 = random.sample(pop, 2) # 不重復(fù)抽樣2個
if random.random() < CROSSOVER_RATE:
child1, child2 = crossover(parent1, parent2) # 交叉
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) # 每一次迭代獲得最佳個體的適應(yīng)度值
if best_gen_makespan < best_makespan: # 更新最小fitness值
best_makespan = best_gen_makespan
best_job = copy.deepcopy(best_gen_job) # TODO: 不用deepcopy的話不會迭代，但是這里應(yīng)該有更好的方法
best_id = copy.deepcopy(job_id)
fitness_history.append(best_makespan) # 把本次迭代結(jié)果保存到fitness_history中（用于繪迭代曲線）
# 繪制迭代曲線圖
plt.plot(range(MAX_GEN + 1), fitness_history)
plt.xlabel('Generation')
plt.ylabel('Fitness Value')
plt.title('Genetic Algorithm Convergence')
plt.show()
return best_id, best_job, best_makespan
def plot_gantt(job_id, job):
# 準(zhǔn)備一系列顏色
colors = ['blue', 'yellow', 'orange', 'green', 'palegoldenrod', 'purple', 'pink', 'Thistle', 'Magenta', 'SlateBlue',
'RoyalBlue', 'Cyan', 'Aqua', 'floralwhite', 'ghostwhite', 'goldenrod', 'mediumslateblue', 'navajowhite',
'moccasin', 'white', 'navy', 'sandybrown', 'moccasin']
job_colors = random.sample(colors, len(job))
# 計(jì)算每個工件的開始時間和結(jié)束時間
start_time = [[] for _ in range(machine_num)]
end_time = [[] for _ in range(machine_num)]
id = [[] for _ in range(machine_num)]
job_color = [[] for _ in range(machine_num)]
for i in range(len(job)):
if start_time[job[i]]:
start_time[job[i]].append(max(end_time[job[i]][-1], arr_times[job_id[i]]))
end_time[job[i]].append(start_time[job[i]][-1] + pro_times[job_id[i]])
else:
start_time[job[i]].append(arr_times[job_id[i]])
end_time[job[i]].append(start_time[job[i]][-1] + pro_times[job_id[i]])
id[job[i]].append(job_id[i])
job_color[job[i]].append(job_colors[job_id[i]])
# 創(chuàng)建圖表和子圖
plt.figure(figsize=(12, 6))
# 繪制工序的甘特圖
for i in range(len(start_time)):
for j in range(len(start_time[i])):
plt.barh(i, end_time[i][j] - start_time[i][j], height=0.5, left=start_time[i][j], color=job_color[i][j],
edgecolor='black')
plt.text(x=(start_time[i][j] + end_time[i][j]) / 2, y=i, s=id[i][j], fontsize=14)
# 設(shè)置縱坐標(biāo)軸刻度為機(jī)器編號
machines = [f'Machine {i}' for i in range(len(start_time))]
plt.yticks(range(len(machines)), machines)
# 設(shè)置橫坐標(biāo)軸刻度為時間
# start = min([min(row) for row in start_time])
start = 0
end = max([max(row) for row in end_time])
plt.xticks(range(start, end + 1))
plt.xlabel('Time')
# 圖表樣式設(shè)置
plt.ylabel('Machines')
plt.title('Gantt Chart')
# plt.grid(axis='x')
# 自動調(diào)整圖表布局
plt.tight_layout()
# 顯示圖表
plt.show()
if __name__ == '__main__':
# 定義多機(jī)調(diào)度問題的工件和加工時間
job_id = [0, 1, 2, 3, 4, 5, 6, 7, 8] # 工件編號
pro_times = [4, 7, 6, 5, 8, 3, 5, 5, 10] # 加工時間
arr_times = [3, 2, 4, 5, 3, 2, 1, 8, 6] # 到達(dá)時間
deadlines = [10, 15, 30, 24, 14, 13, 20, 18, 10] # 交貨期
machine_num = 3 # 3臺完全相同的并行機(jī)，編號為0,1,2
job_id, best_job, best_makespan = GA(True)
print("最佳加工順序：", job_id)
print("最佳調(diào)度分配：", best_job)
print("最小交貨期延時時間：", best_makespan)
plot_gantt(job_id, best_job)
到了這里，關(guān)于【調(diào)度算法】并行機(jī)調(diào)度問題遺傳算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
