【调度算法】并行机调度问题遗传算法

这篇具有很好参考价值的文章主要介绍了【调度算法】并行机调度问题遗传算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

问题描述

m台相同的机器,n个工件,每个工件有1道工序,可按照任意的工序为每个工件分配一台机器进行加工

工件 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
到达时间 3 2 4 5 3 2 1 8 6
交货期 10 15 30 24 14 13 20 18 10

设备数目:3

目标函数

最小化交货期总延时时间

编码说明

记机器数为m,从0开始编号为0,1,...,m-1,记工件数为n,同样从0开始编号。

定义两个变量job_idjob,前者表示工件的加工顺序(不是严格意义上的先加工A再加工B这种顺序,这里的每个工件都是独立的,整一个id只是为了再分配完机器之后自然就能选出一种加工顺序),后者表示每个工件用哪台机器加工。

例如,job_id=[4, 0, 5, 8, 1, 6, 2, 7, 3]job=[0, 1, 2, 2, 1, 0, 2, 1, 0]表示“编号为4的工件被分配给了编号为0的机器”,“编号为0的工件被分配给了编号为1的机器”,编号为0的机器上工件加工的先后顺序为4,6,3,其余类推。

注意,并行机调度问题里边对于染色体的编码一般分为机器选择部分工件排序部分,机器选择部分,就是正常这里应该是先给工件分配机器,再对每台工件上分配的机器进行排序,但是我这个代码里就是先直接对工件进行乱序然后再选择机器,乍一听好像最后的效果差不多,但是看代码就会知道,我代码里是对job_id进行乱序之后,直接就一种群为单位进行选择交叉变异了。即,一个job_id值对应一个种群(而非一个个体,但是理论上应该是每个个体对对饮过一个不同的顺序),就可能会导致处理大规模问题的时候时间复杂度太高(这里确实是偷懒了但是我这两天看代码真的看麻了5555,菜是原罪),有能力的好兄弟改好了可以踢我一下。

具体思路可以看这篇:https://blog.csdn.net/qq_38361726/article/details/120669250

运算结果

最佳加工顺序: [4, 0, 5, 8, 1, 6, 2, 7, 3]
最佳调度分配: [0, 1, 2, 2, 1, 0, 2, 1, 0]
最小交货期延时时间: 7

【调度算法】并行机调度问题遗传算法

【调度算法】并行机调度问题遗传算法文章来源地址https://www.toymoban.com/news/detail-745969.html

python代码

import random
import numpy as np
import matplotlib.pyplot as plt
import copy


# 定义遗传算法参数
POP_SIZE = 100  # 种群大小
MAX_GEN = 100  # 最大迭代次数
CROSSOVER_RATE = 0.7  # 交叉概率
MUTATION_RATE = 0.2  # 变异概率


def sort_by_id(id, sequence):
    # 根据id对sequence进行排序
    new_sequence = sequence[:]
    for i in range(len(id)):
        sequence[i] = new_sequence[id[i]]


# 随机生成初始种群,这里的每个个体表示第i个工件选择在第choose[i]台机器进行加工,工件和机器编码都是从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


# 计算染色体的适应度(makespan) 以最小化交货期延时为目标函数,这里计算的是交货期总延时时间
def fitness(job):
    delay_times = [[] for _ in range(machine_num)]  # 每个工件超过交货期的延时时间
    finish_times = [[] for _ in range(machine_num)]  # 每个工件完成加工的时间点
    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]  # 以最小化交货期总延时为目标函数,这里把最小化问题转变为最大化问题
    total_fitness = sum(fitness_values)
    prob = [fitness_value / total_fitness for fitness_value in fitness_values]  # 轮盘赌,这里是每个适应度值被选中的概率
    # 按概率分布prob从区间[0,len(pop))中随机抽取size个元素,不允许重复抽取,即轮盘赌选择
    selected_indices = np.random.choice(len(pop), size=POP_SIZE // 2, p=prob, replace=False)
    return [pop[i] for i in selected_indices]


# 交叉操作 这里是单点交叉
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)  # 这样的话变异概率可以设置得大一点,因为实际的变异概率是MUTATION_RATE*(machine_num-1)/machine_num
    return job


# 主遗传算法循环
# 以最小化延迟交货时间为目标函数
# TODO: 没有考虑各机器的负载均衡
def GA(is_shuffle):  # 工件加工顺序是否为无序
    best_id = job_id  # 初始化job_id
    best_job = [0, 0, 0, 0, 0, 0, 0, 0, 0]  # 获得最佳个体
    # "makespan" 是指完成整个生产作业或生产订单所需的总时间,通常以单位时间(例如小时或分钟)来衡量。
    best_makespan = fitness(best_job)  # 获得最佳个体的适应度值
    # 创建一个空列表来存储每代的适应度值
    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)  # 不重复抽样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)  # 每一次迭代获得最佳个体的适应度值

        if best_gen_makespan < best_makespan:  # 更新最小fitness值
            best_makespan = best_gen_makespan
            best_job = copy.deepcopy(best_gen_job)  # TODO: 不用deepcopy的话不会迭代,但是这里应该有更好的方法
            best_id = copy.deepcopy(job_id)
        fitness_history.append(best_makespan)  # 把本次迭代结果保存到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):
    # 准备一系列颜色
    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))
    # 计算每个工件的开始时间和结束时间
    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]])

    # 创建图表和子图
    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)

    # 设置纵坐标轴刻度为机器编号
    machines = [f'Machine {i}' for i in range(len(start_time))]
    plt.yticks(range(len(machines)), machines)

    # 设置横坐标轴刻度为时间
    # 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')

    # 图表样式设置
    plt.ylabel('Machines')
    plt.title('Gantt Chart')
    # plt.grid(axis='x')

    # 自动调整图表布局
    plt.tight_layout()

    # 显示图表
    plt.show()


if __name__ == '__main__':
    # 定义多机调度问题的工件和加工时间
    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]  # 到达时间
    deadlines = [10, 15, 30, 24, 14, 13, 20, 18, 10]  # 交货期
    machine_num = 3  # 3台完全相同的并行机,编号为0,1,2

    job_id, best_job, best_makespan = GA(True)

    print("最佳加工顺序:", job_id)
    print("最佳调度分配:", best_job)
    print("最小交货期延时时间:", best_makespan)
    plot_gantt(job_id, best_job)

到了这里,关于【调度算法】并行机调度问题遗传算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 基于遗传算法的柔性生产调度研究(Matlab代码实现)

    💥💥💞💞 欢迎来到本博客 ❤️❤️💥💥 🏆博主优势: 🌞🌞🌞 博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️ 座右铭: 行百里者,半于九十。 📋📋📋 本文目录如下: 🎁🎁🎁 目录 💥1 概述 📚2 运行结果 🎉3 参考文献 🌈4 Matlab代码实现 摘要:针

    2024年02月08日
    浏览(57)
  • 【水光互补优化调度】基于非支配排序遗传算法的多目标水光互补优化调度(Matlab代码实现)

    💥💥💞💞 欢迎来到本博客 ❤️❤️💥💥 🏆博主优势: 🌞🌞🌞 博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️ 座右铭: 行百里者,半于九十。 📋📋📋 本文目录如下: 🎁🎁🎁 目录 💥1 概述 1.1 水光互补 1.2 水光互补模型——目标函数和约束条件

    2024年02月01日
    浏览(66)
  • 基于自适应遗传算法的车间调度matlab仿真,可以任意调整工件数和机器数,输出甘特图

    目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.本算法原理 4.1 编码与初始化 4.2 适应度函数 4.3 遗传操作 4.4 自适应机制 4.5 终止条件 5.完整程序         基于自适应遗传算法的车间调度matlab仿真,可以任意调整工件数和机器数,输出甘特图和优化算法的适应

    2024年02月01日
    浏览(51)
  • 遗传算法解决旅行商问题

    一、问题描述 旅行商问题(Travelling Salesman Problem, 简记TSP,亦称货郎担问题):设有n个城市和距离矩阵D=[dij],其中dij表示城市i到城市j的距离,i,j=1,2 … n,则问题是要找出遍访每个城市恰好一次的一条回路并使其路径长度为最短。 初始问题图像如下: 近似理想结果图像如

    2024年02月07日
    浏览(43)
  • TSP问题的遗传算法实现

    一.实验目的 本实验课程是计算机、智能、物联网等专业学生的一门专业课程,通过实验,帮助学生更好地掌握人工智能相关概念、技术、原理、应用等;通过实验提高学生编写实验报告、总结实验结果的能力;使学生对智能程序、智能算法等有比较深入的认识。要掌握的知

    2024年02月03日
    浏览(39)
  • 遗传算法及基于该算法的典型问题的求解实践

        遗传算法是一个很有用的工具,它可以帮我们解决生活和科研中的诸多问题。最近在看波束形成相关内容时了解到可以用这个算法来优化阵元激励以压低旁瓣,于是特地了解和学习了一下这个算法,觉得蛮有意思的,于是把这两天关于该算法的学习和实践的内容总结成了

    2024年03月21日
    浏览(47)
  • 遗传算法解决tsp问题(基于python)

    目录 1.遗传算法简要介绍 2.tsp问题简要介绍 3.遗传算法解决tsp问题的几个特殊点 4.源码         简单来说,遗传算法是用于解决最优化问题的一种搜索算法。其核心基于自然界种群进化的规律,即初始种群进行交配,在基因层面上,其中会发生交叉互换、基因突变等变异

    2023年04月12日
    浏览(75)
  • 路径规划问题的遗传算法实现(python代码)

        遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。该算法通过数学的方式,利用计算机仿真运算,将问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程。     路径

    2024年02月04日
    浏览(42)
  • 人工智能导论——遗传算法求解TSP问题实验

    一、实验目的: 熟悉和掌握遗传算法的原理、流程和编码策略,并利用遗传算法求解组合优化问题,理解求解TSP问题的流程并测试主要参数对结果的影响。 二、实验原理: 旅行商问题,即TSP问题(Traveling Salesman Problem)是数学领域中著名问题之一。假设有一个旅行商人要拜

    2023年04月13日
    浏览(42)
  • 模拟退火算法与遗传算法求解多目标优化问题的算法实现(数学建模)

    模拟退火算法是一种全局优化算法,解决的问题通常是找到一个最小化(或最大化)某个函数的全局最优解。它通过模拟物理退火的过程来搜索解空间,在开始时以一定的温度随机生成初始解,然后一步步降低温度,同时在当前解的周围随机搜索新的解,并根据一定概率接受

    2024年02月02日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包