Skip to content

Halfknow/Job-Scheduling

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

21 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

你已经提供了大量的C++代码,这是一个使用各种数据结构的项目,看起来是对特定任务的处理。这是一些你需要注意的主要部分:

数据结构: 这里定义了多种数据结构,比如 Job, GeneralJob, JobOverlap, generalJobOverlap, Block, generalJobBlock 等。它们包含了不同的字段,如 job, order, time 等,这些字段可能代表了任务的某些属性。

排序: 这里使用了C++的std::sort函数来按照一定规则对任务进行排序。这个规则是首先比较任务的发布时间(r),如果发布时间相同,则比较任务的完成时间(f)。

文件操作: 有一个名为 openfile 的函数,其主要目的是从一个名为 "JobList2.txt" 的文件中读取任务列表,并将其存储在名为 job 的vector中。在读取任务后,该函数会对任务列表进行排序,并初始化一些字段。

全局变量: 在代码中定义了多个全局变量,如 gJobNum, gGenerations 等。这些可能用于控制程序的某些方面,如任务的数量或生成的数量。

使用库: 代码中使用了多个库,包括 io.h, windows.h, gdiplus.h, iostream, fstream, string, queue, fmt/format.h, fmt/ostream.h, ctime, "GA/Galgo.hpp", filesystem, execution。这些库提供了文件输入/输出、字符串处理、日期/时间处理、遗传算法、文件系统操作和并行执行等功能。

重载操作符: 这段代码重载了输入和输出流操作符,以及小于操作符,以适应这些特定的数据结构。

没有主函数: 这段代码中没有主函数,因此,这可能只是一个更大程序的一部分。如果这是完整的程序,你需要添加一个主函数来启动程序的执行。

此外,还有两个函数声明 runTestFit 和 runTestTime,但是它们的具体实现没有在这段代码中提供。

这些新的C++函数基本上在完成以下几个主要的功能:

文件读取: 有三个名为 openGenreralUnitFile, openGenreralFile 和 openfile 的函数,它们打开不同的文本文件("GeneralUnitJobList1.txt","GeneralJobList1.txt" 和 "JobList2.txt"),并从中读取任务数据,然后保存到相应的 vector 数据结构中。它们还将任务按照发布时间(r)和完成时间(f)进行排序,并给每个任务赋予一个唯一的顺序编号。

图形绘制: 还有几个名为 drawFile, drawInitFile, drawGeneralUnitFile, drawGeneralUnitInitFile, drawGeneralFile 和 drawGeneralInitFile 的函数,这些函数都使用 Gdiplus 图形库在给定的 HDC(句柄到设备上下文)上绘制作业的图形表示。它们画出的是一条线,线的起点和终点分别代表任务的开始时间和结束时间。而不同的任务在垂直方向上被区分。此外,它们还绘制了一个尺子,用于在水平轴上显示时间单位。

这些函数允许你从不同的文件中读取任务数据,并在屏幕上以图形方式显示这些任务的时间安排。它们都是在使用 GDI+,这是 Windows 下的一个强大的2D图形编程接口,提供了许多基本的图形绘制功能,包括绘制直线、曲线、填充区域等。

值得注意的是,你已经在代码中使用了许多全局变量和数据结构。在大型项目中,这可能会引发一些问题,例如

这两段代码实现了两种不同的算法,都是为了解决一种称为Job Scheduling问题的任务调度问题。每个Job都有一个开始时间和结束时间,这两个算法的目标都是找出最优的Job调度策略,使得每个时间点被尽可能多的Job占用。

下面分别是每段代码的主要工作:

approAlgI(): 这是第一种算法。首先,该函数接受HDC hdc, HWND hWnd 和 RECT rect这三个参数,用于绘制结果。然后,对Jobs进行初始化,并用remainingJobs来记录所有未被删除的Jobs。接着,该算法会寻找当前所有Job中重叠程度最高的时间点,并删除这些重叠的Jobs,这一过程会重复进行,直到所有的Jobs都被删除。最后,用GDI+绘制每个Block。

approAlgII(): 这是第二种算法。与approAlgI()非常相似,主要的区别在于寻找最大重叠的方式。这个算法会对每一个Job进行检查,寻找这个Job在其存在的时间段内重叠程度最大的时间点,然后删除那些在该时间点重叠的Jobs。该过程会重复进行,直到所有的Jobs都被删除。最后,用GDI+绘制每个Block。

对于这两段代码,需要注意的关键概念包括:Job,开始时间(r)和结束时间(f),Block以及重叠。此外,这两段代码都使用了Windows的GDI+图形库来进行绘制。

这段代码主要包含两个函数 optAlg 和 approGeneralUnitAlg,它们使用的都是一些类似的数据结构和算法。

optAlg 函数 这个函数主要进行以下操作:

初始化 job_1 和 job_2 的作业向量,并使用 job 作业向量初始化 remainingJobs 作业队列。

使用贪婪策略选择工作,贪婪选择的标准是选择完成时间 f 最早的工作。选中的工作被添加到 remainingELI 队列中,并从 job_1 中删除。

使用 Gdiplus 的画图函数,在窗口上画出作业的开始和结束时间。

在所有工作都被选取后,该函数对每个阻塞进行迭代。对于每个阻塞,它首先找出所有与当前 remainingELI 队列头部作业重叠的作业,并将这些作业从 remainingJobs 和 job_2 中删除。然后,它计算这个阻塞的信息并打印出来。

在所有阻塞都被处理之后,最后再次绘制每个阻塞的开始和结束时间。

approGeneralUnitAlg 函数 这个函数的结构和 optAlg 非常类似,但它处理的是一般单元作业 generalUnitJob,并且它使用了2-近似算法。此外,此函数还处理了长度为1的情况。不过大部分操作(如初始化作业向量,使用贪婪策略选择作业,画图,处理阻塞等)都和 optAlg 函数相似。

在给出的代码中,有两个主要部分。第一个是一个名为 geneToBlocks 的函数,第二个是一个名为 MyObjective 的模板类,这两部分都与遗传算法有关。让我们来分别阅读和理解它们。

geneToBlocks函数: 这个函数将遗传算法的解(基因)映射到所称的GeneralJob和GeneralJobBlock对象中。在函数的输入参数中,ga 是遗传算法对象,generalJob_1 是一个 GeneralJob 类型的双端队列,generalBlocks 是一个 GeneralJobBlock 类型的双端队列,worstGenes 是一个指向 double 类型向量的指针。

函数中有两个主要的循环部分,它们都对 GeneralJob 的对象进行操作,一个是基于 worstGenes,一个是基于 ga。然后,它对 generalJob_1 进行调整,并在排序后,根据一些条件将其对象添加到 generalBlocks 中。

MyObjective类: 这是一个模板类,包含了一个静态成员函数 Objective,它计算并返回一个目标函数的值。目标函数中的逻辑包含了对 GeneralJob 对象的一系列操作,这与前面的 geneToBlocks 函数类似。它的目标是优化 generalBlocks 中的长度。

然后,我们看到一个 MyConstraint 函数,它似乎是在应用一些约束条件,但这里的条件并不明显,因为它只是简单地返回一个常数 -12。

总的来说,这段代码的目的是实现一个遗传算法来优化一些与 GeneralJob 和 GeneralJobBlock 相关的条件。如果需要更深入的理解,可能需要进一步查看 GeneralJob 和 GeneralJobBlock 类的定义,以及这个算法是如何在更大的上下文中应用的。

这是一个 C++ 的 Win32 应用程序,使用了 GDI+,fmt 和 galgo (一种遗传算法库)。它主要用于解决任务调度问题。

程序首先接收一组命令行参数,可以设置不同的选项,比如生成的代数、开始的任务、完成的任务、步骤、运行测试时间、运行测试适应度、测试号等。然后根据这些参数执行不同的测试。此外,还有 GDI+ 用于绘图的初始化代码。

函数 runTest_runningtime_jobnum 用于运行具有特定任务数量的测试。它首先生成随机任务集,然后运行遗传算法以找到最佳的任务调度。算法的结果(包括运行时间和调度的长度)然后被写入一个 CSV 文件。

WndProc 函数(虽然代码中没有给出)应该是用于处理窗口消息的回调函数。

遗传算法库 galgo 被用于求解问题,它实现了标准的遗传算法操作(选择、交叉、突变等)。在这个案例中,它的目标函数是 MyObjective::Objective,该函数没有在给定的代码片段中定义,但它应该是评估给定任务调度的质量(如完成时间、延迟等)的函数。

总的来说,这是一个通过命令行参数控制的程序,可以执行不同的测试,最终通过使用遗传算法来优化任务调度。 这些代码定义了一些函数,主要用于测试基于遗传算法的调度任务的优化过程。它们是以适应度和运行时间为基础的。

以下是每个函数的简要说明:

runTest_fitness_generation(std::filesystem::path mTestFolder, size_t jobnum):这个函数使用遗传算法对一个具有指定数量任务的调度问题进行优化,并将适应度数据保存到一个csv文件中。它使用了随机数生成器来创建一组任务,并用遗传算法找到最优解。然后,它记录了每一代的适应度,并将这些信息写入文件。

runTestFit():这个函数创建一个新的测试文件夹,并调用runTest_fitness_generation函数来对具有指定任务数量的调度问题进行遗传算法优化,并保存适应度数据。

runTestTime():这个函数创建一个新的测试文件夹,并根据设定的开始、结束和步长,为每个任务数量调用runTest_runningtime_jobnum函数来运行遗传算法并记录运行时间。

runTest_runningtime_jobnum(std::filesystem::path mTestFolder, size_t jobnum):这个函数使用遗传算法对一个具有指定数量任务的调度问题进行优化,并记录了算法的运行时间。这个函数与runTest_fitness_generation类似,不过除了记录每一代的适应度外,还记录了运行时间。

你的代码是一个 Windows 窗口程序的消息处理函数 (WndProc)。在 Windows 程序中,WndProc 用于接收和处理从操作系统发送给应用程序的各种消息,比如用户的鼠标点击、键盘输入、窗口尺寸改变等。这些消息是通过操作系统传递给 WndProc 函数进行处理的。

这个函数根据传入的消息 (message 参数),进行一系列的处理:

当 message 是 WM_PAINT (通常表示窗口需要重绘),它首先开始一个画布 (BeginPaint) ,清理窗口,然后根据输入的情况调用不同的绘图函数 (drawFile、approAlgI、approAlgII、optAlg 等等)。在输入为 5 或 14 的情况下,它会执行更复杂的操作,包括执行遗传算法、将遗传算法的结果转换成可绘制的数据结构,然后进行绘图,并最后将结果输出到一个 CSV 文件。

当 message 是 WM_DESTROY (通常表示窗口需要关闭),它发送一个退出消息 (PostQuitMessage),告知操作系统应用程序需要关闭。

当 message 是 WM_KEYDOWN (表示用户按下了一个键),它根据用户按下的键 (wParam 参数),修改 input 变量,并刷新窗口 (InvalidateRect 和 UpdateWindow),触发窗口重新绘制。

如果消息不是上述的任何一种,那么就会默认调用 DefWindowProc,让操作系统处理这个消息。

注意,这段代码调用了很多你没有提供的自定义函数 (如 drawFile、approAlgI、optAlg 等),这使得在阅读代码时难以完全理解其运行逻辑。同时,代码中使用了多个没有定义的全局变量,如 input、gGenerations、generalJob 等,这也会对阅读代码带来一定的困难。

概述

你的 main.cpp 文件似乎是一个运用遗传算法解决某类问题的图形化应用程序。其中包含一个 Windows 程序的主入口函数 WinMain,创建了一个应用程序窗口并初始化了一些用于绘图的组件。而窗口消息处理函数 WndProc 则负责根据用户的键盘输入或者其他消息来执行不同的操作。

WinMain:这是应用程序的主入口函数。在这个函数中,首先进行了初始化GDI+的操作,然后设置了窗口的类名和标题,以及窗口的长宽等属性。然后创建窗口并显示,并进入消息循环。

WndProc:这是窗口消息处理函数,主要负责处理窗口接收到的各种消息,包括创建、销毁、重绘、按键等消息。

WM_CREATE消息:窗口被创建时会收到这个消息,在处理这个消息时,进行了初始化操作,包括创建画刷,设置字体,初始化种群等。

WM_DESTROY消息:窗口被销毁时会收到这个消息,在处理这个消息时,进行了一些清理工作,然后发送了退出消息,使得消息循环退出,程序结束。

WM_PAINT消息:窗口需要重绘时会收到这个消息,在处理这个消息时,会绘制背景,绘制种群,以及绘制一些文本信息。

WM_KEYDOWN消息:当按下某个按键时会收到这个消息,在处理这个消息时,会根据按键的不同进行不同的操作,如改变速度,保存种群等。

MyRegisterClass:这个函数用于注册窗口类。在Windows应用程序中,每个窗口都需要有一个对应的窗口类,窗口类定义了窗口的基本行为,如窗口的样式,背景,光标,以及窗口消息处理函数等。

InitInstance:这个函数用于创建和显示窗口。

savePopulation:这个函数用于保存种群到文件。在这个函数中,首先打开文件,然后将种群的信息写入文件,最后关闭文件。

loadPopulation:这个函数用于从文件加载种群。在这个函数中,首先打开文件,然后读取文件中的种群信息,最后关闭文件。

evolve:这个函数用于进化种群,实现遗传算法。在这个函数中,首先根据适应度进行选择,然后进行交叉和变异,最后更新种群。

display:这个函数用于显示种群。在这个函数中,将种群的各个个体绘制到窗口中。

init:这个函数用于初始化种群。在这个函数中,首先创建一些随机的个体,然后将这些个体添加到种群中。

approAlgI 函数

approAlgI 函数实现了一个作业调度问题的近似算法。它采用了一个“工作-阻塞”模型,将重叠的作业集群组合成块,并将其调度为在特定时间开始执行。这个算法的主要目标是尽量减少在给定时间内重叠的作业数量。

下面是每个关键步骤的详细概述:

初始化:这个函数首先创建了几个用于处理作业和块的向量和队列。它还初始化了图形对象和一个画笔,用于在应用程序的窗口上绘制输出结果。

作业和剩余作业的设置:接着,函数设置了job_1向量和remainingJobs队列,job_1包含了所有的作业,而remainingJobs包含了待处理的作业。

最大完成时间的确定:然后,函数确定了所有作业的最大完成时间。

主循环:函数接下来进入一个主循环,该循环持续进行,直到所有的作业都被处理。在每次迭代中,函数计算了在每个时间点上的重叠作业数量,并在每个时间点生成了一个JobOverlap对象。然后,它找出了重叠作业数量最大的时间点,并将此时点的所有重叠作业移除。同时,这些被移除的作业被组合成一个块,并添加到blocks向量中。

信息打印:对于每个生成的块,函数打印出它的信息,包括它的时间和包含的作业。

画图:最后,函数使用Gdiplus库在窗口上绘制了每个块的线图。

虽然这个函数在其当前状态下可以工作,但是它可能在性能和结构上进行一些改进:

重构:这个函数尝试做了很多事情。考虑将它拆分成几个更小的函数,以增加代码的可读性和可维护性。

优化:在主循环中,每次迭代都会清除和重新填充job_overlap向量,这可能会导致不必要的性能开销。考虑其他方式来管理这个向量,或者找出是否有可能避免在每次迭代中都进行这种操作。

错误处理:函数似乎没有错误处理。例如,如果job向量为空,函数可能会出现问题。考虑添加适当的错误处理机制,以防出现这种情况。

approAlgII 函数

approAlgII函数与前面的approAlgI函数在某些方面是相似的,但在实现策略上有些不同。approAlgII函数实现了一个稍微不同的作业调度问题的近似算法,但仍然是基于“工作-阻塞”的模型,将重叠的作业集群组合成块,并将其调度为在特定时间开始执行。这两个函数都是为了尽量减少在给定时间内重叠的作业数量。

以下是approAlgII函数的关键步骤,我将特别关注它与approAlgI函数的主要区别:

初始化:这部分与approAlgI函数中的步骤基本相同。函数首先创建了几个用于处理作业和块的向量和队列。然后它初始化了图形对象和一个画笔,用于在应用程序的窗口上绘制输出结果。

作业和剩余作业的设置:这部分也与approAlgI函数相同,函数设置了job_1向量和remainingJobs队列,job_1包含了所有的作业,而remainingJobs包含了待处理的作业。

主循环:这部分是这两个函数的主要区别。在approAlgII中,每次迭代的开始,它会查找第一个未被移除的作业,并检查它的每个可能的结束时间点,找到重叠作业数量最大的时间点。然后,它将此时间点的所有重叠作业移除,并将这些作业组合成一个块,并添加到blocks向量中。与approAlgI不同的是,approAlgII每次迭代都会针对一个特定的作业来查找最大重叠,而approAlgI则在所有作业的整个时间范围内查找最大重叠。

信息打印:对于每个生成的块,函数打印出它的信息,包括它的时间和包含的作业。

画图:最后,函数使用Gdiplus库在窗口上绘制了每个块的线图。

与approAlgI函数相比,approAlgII的主循环更为复杂,因为它在每个迭代中都要对一个特定的作业进行计算。这可能使approAlgII在处理大量作业时性能较差。然而,这也可能使得approAlgII在某些情况下能找到更优的解,因为它考虑了每个作业的具体时间范围。

approGeneralUnitAlg 函数

这个函数 approGeneralUnitAlg 是对于处理"General Unit Jobs"问题的一个2-近似算法。根据输入,它主要处理的是有不同执行时间(或称处理时间)的任务。

定义变量:它首先创建了一些矢量,队列和其他必要的变量来存储处理过程中的数据。

初始化:在初始化阶段,该函数使用来自全局generalUnitJob变量的数据来填充job_1和job_2矢量。然后,它初始化了remainingJobs队列,包括generalUnitJob向量中的所有元素。

计算:函数接下来执行一个循环,选择结束时间最早的任务,并且对于所有结束时间早于此任务的任务,进行删除操作。然后它用线将所有这样的任务连接起来。

输出图像:函数在屏幕上绘制"General Unit Job 2-Approximation Algorithm"的文本。

计算块信息:之后,函数进入到一个循环中,计算每个块的信息,包括它的长度,以及和它重叠的任务。对于每个块,它都记录了与该块重叠的任务,并且从remainingJobs和job_2中删除了它们。

信息打印:接着,函数在屏幕上打印出每个块的信息,包括块的时间,块内的任务等。

最后,它在屏幕上绘制每个块的线条,代表每个块在时间线上的位置。

这个函数与前两个函数的区别在于,它适用于处理长度不同的任务,而前两个函数则主要处理相同长度的任务。在处理任务的方式上,这个函数采取的是选择结束时间最早的任务,并删除所有结束时间早于此任务的任务的方式,而前两个函数是选择最多重叠任务的方式。在输出上,它除了打印出块的信息,还绘制了代表每个块的线条,可视化了每个块在时间线上的位置。

optAlg 函数

首先,从一个宏观的角度看,这三个函数都看起来是针对某种作业调度问题的解决方案,具体的问题可能涉及作业的开始时间、结束时间、以及其他一些因素。所有的这些函数都在处理一个作业队列,并使用GDI+库将作业的处理情况可视化。

现在我们来看看这三个函数的主要区别:

approAlgI:这个函数通过遍历所有的作业并找出其中最早结束的作业(也就是结束时间最小的作业),然后将这个作业以及它之前的所有作业从待处理列表中移除。接着,它使用GDI+画出了每个作业的执行时间线。

approAlgII:这个函数的主要处理逻辑与approAlgI函数类似,都是找出最早结束的作业并将其以及它之前的所有作业从待处理列表中移除。然而,不同之处在于它还计算了与当前作业重叠的其他作业,并将这些作业也从待处理列表中移除。同时,它还记录了每个时间块(Block)的信息,包括时间块中作业的数量以及结束时间等。

approGeneralUnitAlg:这个函数首先按照作业的结束时间对作业进行排序,并将其存储在一个优先队列中。然后,它遍历这个优先队列并根据作业的结束时间将作业添加到了一个新的优先队列中。在处理过程中,如果遇到了结束时间比当前时间还早的作业,就会将这个作业跳过。最后,这个函数也是使用GDI+将每个作业的执行时间线画出来。

总结一下,这三个函数都是在处理类似的作业调度问题,但是它们使用了不同的策略和算法。approAlgI函数和approAlgII函数都是通过找出最早结束的作业并排除掉与它重叠的作业来解决问题,而approGeneralUnitAlg函数则是通过使用优先队列和对作业进行排序来处理问题。在处理过程中,所有的函数都将处理结果用图形的方式可视化出来。

optAlg函数同样是处理作业调度问题的算法,根据代码的内容,该函数可以被分解为一下几个主要的部分:

数据初始化:函数首先复制了两份工作列表,job_1和job_2。此外,它创建了三个队列:remainingELI,remainingJobs和remainingJobs_2,以及两个向量job_overlap和blocks,以存储作业的执行信息和相应的绘图信息。

寻找最早结束的作业:函数接下来进入了一个循环,该循环会持续到job_1列表为空为止。在循环中,它寻找结束时间最早的作业,将其存储在队列remainingELI中,并将在这个作业结束前开始的所有作业从job_1列表中删除。它还使用GDI+将每个作业的执行时间线画出。

创建时间块并处理重叠的作业:函数接着处理remainingJobs队列中的作业。它首先检查每个作业是否在remainingELI队列中的作业结束之前开始。如果是,它将这个作业添加到job_overlap列表中,并从remainingJobs和job_2队列中删除。然后它将处理过的作业存储在blocks向量中,并使用GDI+将它们画出。

绘制时间块的边界:函数最后通过绘制每个时间块的开始和结束时间的直线,表示了每个时间块的边界。

optAlg函数在处理作业调度问题时,也是使用了一种贪心的策略,即寻找结束时间最早的作业并将与它有重叠的作业排除掉。然后,它将所有处理过的作业按照它们的执行时间分组,并将每一组作业的执行时间范围可视化出来。

GPT4 的性能优化建议

你的代码可能在以下几个方面进行性能优化:

减少全局变量的使用:全局变量可能导致代码难以理解和维护,因为你需要知道全局变量在整个程序的生命周期中的所有状态和修改。尽可能将全局变量替换为局部变量或者类的成员变量。

减少重复的代码:你的代码中存在很多重复的部分,比如在 WndProc 函数的 WM_KEYDOWN 消息处理中,不同按键的处理逻辑大部分是一样的。你可以将这部分代码提取出来,减少重复。

优化遗传算法的实现:你的代码中使用了遗传算法,遗传算法有很多可以调节的参数,比如种群大小、选择、交叉和变异的策略等,你可以根据你的问题特性尝试调整这些参数以获取更好的性能。

异步处理:你的代码在处理 WM_PAINT 消息时,会执行一些可能非常耗时的操作,如遗传算法。这可能会导致你的应用程序在执行这些操作时无响应。你可以考虑将这些耗时操作放在单独的线程中执行,这样就可以防止应用程序界面冻结。

内存管理:在你的代码中创建了一些 GDI 和 GDI+ 对象,但没有看到对应的删除操作。如果不适当地管理这些资源,可能会导致内存泄露。例如,CreateSolidBrush 创建的画刷需要用 DeleteObject 删除。

使用更现代的图形库:你的代码使用了旧版的 GDI 和 GDI+ 来进行绘图,这些库的性能和功能都比较有限。你可以考虑使用更现代的图形库,如 DirectX、OpenGL 或者 Vulkan。

文件操作优化:在你的代码中,每次需要输出结果时都会打开文件、写入数据然后关闭文件。这种频繁的文件操作会造成不小的开销。你可以考虑一次性写入数据或者使用缓存,减少文件操作的次数。

About

No description, website, or topics provided.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages