【调度算法】单机调度问题遗传算法

简介: 【调度算法】单机调度问题遗传算法

问题描述

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

目标函数

最小化交货期总延时时间

运算结果

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

python代码

import math
import random
import numpy as np
import matplotlib.pyplot as plt
# 定义遗传算法参数
POP_SIZE = 100  # 种群大小
MAX_GEN = 100  # 最大迭代次数
CROSSOVER_RATE = 0.7  # 交叉概率
MUTATION_RATE = 0.2  # 变异概率
# 随机生成初始种群
def gen_init_pop(pop_size):
    population = []
    for _ in range(pop_size):
        random.shuffle(job)
        population.append(list(job))
    return population
# 计算染色体的适应度(makespan) 以最小化交货期延时为目标函数,这里计算的是交货期总延时时间
def fitness(job):
    n = len(job)
    accu_pro_times = [0] * n  # 累计加工时间
    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
# 选择父代,这里选择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] + [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
# 变异操作
def mutation(job):
    index1, index2 = random.sample(range(len(job)), 2)
    job[index1], job[index2] = job[index2], job[index1]
    return job
# 主遗传算法循环
def GA():
    # 创建一个空列表来存储每代的适应度值
    best_job = job  # 获得最佳个体
    # "makespan" 是指完成整个生产作业或生产订单所需的总时间,通常以单位时间(例如小时或分钟)来衡量。
    best_makespan = fitness(job)  # 获得最佳个体的适应度值
    fitness_history = [best_makespan]
    pop = gen_init_pop(POP_SIZE)
    for _ in range(1, MAX_GEN + 1):
        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 = best_gen_job
        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_job, best_makespan
def plot_gantt(job, pro_times, arr_times):
    # 计算每个工件的开始时间和结束时间
    start_time = [arr_times[0]]  # 第一个工件的开始时间为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])
    # # 绘制甘特图
    plt.figure(figsize=(10, 7))
    plt.barh(job, pro_times, left=start_time, color='b', label='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')  # 空闲时间
    plt.xlabel('Time')
    plt.ylabel('Jobs')
    plt.title('Gantt Chart')
    plt.legend()
    plt.grid(axis='x')
    # 显示甘特图
    plt.show()
if __name__ == '__main__':
    # 定义单机调度问题的工件和加工时间
    job = [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]  # 交货期
    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_job)
    print("最小交货期延时时间:", best_makespan)
    plot_gantt(best_job, best_pro_times, best_arr_times)


目录
相关文章
|
2天前
|
机器学习/深度学习 人工智能 分布式计算
算法金 | 最难的来了:超参数网格搜索、贝叶斯优化、遗传算法、模型特异化、Hyperopt、Optuna、多目标优化、异步并行优化
机器学习中的超参数调优是提升模型性能的关键步骤,包括网格搜索、随机搜索、贝叶斯优化和遗传算法等方法。网格搜索通过穷举所有可能的超参数组合找到最优,但计算成本高;随机搜索则在预设范围内随机采样,降低计算成本;贝叶斯优化使用代理模型智能选择超参数,效率高且适应性强;遗传算法模拟生物进化,全局搜索能力强。此外,还有多目标优化、异步并行优化等高级技术,以及Hyperopt、Optuna等优化库来提升调优效率。实践中,应结合模型类型、数据规模和计算资源选择合适的调优策略。
6 0
算法金 | 最难的来了:超参数网格搜索、贝叶斯优化、遗传算法、模型特异化、Hyperopt、Optuna、多目标优化、异步并行优化
|
13天前
|
算法 调度 云计算
操作系统中的调度算法:从理论到实践
在计算机科学领域,操作系统的调度算法是决定任务执行顺序的关键。本文首先概述了调度算法的基本概念和重要性,随后深入探讨了几种主要的调度算法,包括先来先服务、短作业优先、轮转与优先级调度等。通过引用最新的科研数据和实验证据,文章揭示了不同调度算法的性能表现和适用场景。此外,本文还讨论了现代操作系统中调度算法面临的挑战和未来的发展方向,强调了在多核处理器和云计算环境下调度策略的复杂性。最后,通过案例分析,展示了如何在实际系统中应用这些理论知识,以及在设计高效调度系统时需要考虑的因素。
|
8天前
|
机器学习/深度学习 算法 数据挖掘
操作系统调度算法的演进与性能分析
随着计算机科学的发展,操作系统作为硬件与软件之间的桥梁,其调度算法对系统性能有着举足轻重的影响。本文将探讨操作系统中调度算法的演变,从早期的简单调度策略到现代复杂的多级反馈队列和实时调度机制,并结合最新研究和实验数据,深入分析不同调度算法对系统吞吐量、响应时间及资源利用率的影响。通过对调度算法性能的定量评估,本文旨在为系统设计者提供优化决策的理论依据,同时为未来调度算法的研究指明方向。
12 0
|
8天前
|
算法 调度
【重磅】“一招”解决智能算法中不满足“预期”的问题【以微电网优化调度为例】
摘要(Markdown格式): 在对微电网优化调度的模型复现中,发现智能算法(如改进粒子群优化)得出的结果有时不符合预期。例如,电网在低电价时段未满负荷购电,而高电价设备出力未相应降低,可能由于算法陷入局部最优或约束条件设置不当。为解决此问题,采用了梯级罚函数方法改进代码,以更好地满足预期的逻辑关系和优化目标。更新后的程序结果显示设备出力和电价成本的关系更符合预期,降低了运行成本。详细分析和改进后的程序结果图表可见相关链接。
|
14天前
|
算法 物联网 调度
操作系统调度算法的演进与性能评估
本文深入探讨了操作系统中进程调度算法的发展轨迹,从早期的先来先服务(FCFS)到现代的多级队列和反馈控制理论。通过引用实验数据、模拟结果和理论分析,文章揭示了不同调度策略如何影响系统性能,特别是在响应时间、吞吐量和公平性方面。同时,本文也讨论了在云计算和物联网等新兴领域,调度算法面临的挑战和未来的发展方向。
|
15天前
|
机器学习/深度学习 人工智能 算法
操作系统调度算法的演变与性能分析
操作系统作为计算机硬件和软件之间的桥梁,其调度算法的效率直接影响到系统的响应速度和资源利用率。本文将探讨从简单到复杂的各类调度算法,包括先来先服务、短作业优先、轮转法以及多级反馈队列等,通过数据分析揭示各算法的性能特点,并结合现代操作系统设计的需求,讨论未来调度算法的发展趋势。
|
15天前
|
机器学习/深度学习 算法 大数据
操作系统调度算法的演变与优化
在计算机科学领域中,操作系统的调度算法是核心的研究课题之一。本文深入探讨了操作系统调度算法的发展历程、当前挑战以及未来趋势。通过引用最新的科研数据和实验证据,本文旨在揭示调度算法如何适应现代计算需求的变化。我们将从理论到实践,详细分析不同调度算法的性能表现,并讨论如何利用这些算法来提升系统的整体效率和响应速度。
11 0
|
16天前
|
算法 调度
【完全复现】基于改进粒子群算法的微电网多目标优化调度
该文档描述了一个使用改进粒子群算法实现的微电网多目标优化调度的Matlab程序。该模型旨在最小化运行成本和环境保护成本,将多目标问题通过权值转换为单目标问题解决。程序中定义了决策变量,如柴油发电机、微型燃气轮机、联络线和储能的输出,并使用全局变量处理电负荷、风力和光伏功率等数据。算法参数包括最大迭代次数和种群大小。代码调用了`PSOFUN`函数来执行优化计算,并展示了优化结果的图表。
|
22小时前
|
算法 数据挖掘
MATLAB数据分析、从算法到实现
MATLAB数据分析、从算法到实现
|
7天前
|
机器学习/深度学习 算法 调度
Matlab|基于改进鲸鱼优化算法的微网系统能量优化管理matlab-源码
基于改进鲸鱼优化算法的微网系统能量管理源码实现,结合LSTM预测可再生能源和负荷,优化微网运行成本与固定成本。方法应用于冷热电联供微网,结果显示经济成本平均降低4.03%,提高经济效益。代码包括数据分段、LSTM网络定义及训练,最终展示了一系列运行结果图表。