【算法学习笔记】5：基于蚁群算法的柔性作业车间调度问题(FJSP)快速求解

简述 这是《深度学习与人工智能》课程中很普通的一道作业题，但因为发现了一个更巧妙的搜索目标的形式，让求解过程快了很多，代码实现起来也简单了非常多，而且最终的搜索效果也更好。 关于蚁群算法和柔性作业车间调度问题不再赘述。 求解策略比较 如果用这篇文章中的方法，求解这个问题会很困难。因为同Job的不同工序是有先后顺序的，如果直接在上面这张表里搜索解，也就是说搜索出的是这张表里每一行标一个机器，那么接下来的时间计算就非常麻烦，需要从这张表去计算一个最优的调度顺序，这个过程代价很高，而且程序很难写。 在这篇文章中看到了一种搜索目标的表示形式，这篇文章虽然是讲遗传算法而不是蚁群算法，但是它对遗传算法染 【算法学习笔记】这篇笔记主要讨论了如何利用蚁群算法高效地解决柔性作业车间调度问题（Flexible Job-shop Scheduling Problem, FJSP）。在《深度学习与人工智能》课程中，这个问题通常作为作业出现，但通过引入创新的搜索目标表示方法，使得求解过程大大简化，代码实现变得更加容易，同时优化了搜索效果。 柔性作业车间调度问题涉及到多个任务（Job）在多台机器上按特定顺序进行加工，每个任务由若干个工序组成，且工序间存在严格的前后关系。传统的方法可能直接在工序表中搜索解决方案，但这会导致时间计算复杂且程序编写困难。 文中提到的改进策略是将搜索目标分为两部分：topo_jobs 和 process2machine。topo_jobs 是一个列表，它表示所有工序的顺序，确保工序间的先后关系得以保持；process2machine 是一个二维列表，存储每个工序应分配到的机器。这种编码方式使得时间计算变得简单，只需模拟多台机器的栈，按照工序顺序压入栈中，根据栈顶状态确定工序的开始时间。在实际编程时，并不需要真正创建栈结构。 在蚁群算法的框架下，需要两张与搜索目标相对应的信息素浓度表，每轮迭代后更新这些表。程序实现中假设所有任务的工序数量相同，若情况更复杂，只需将 process_num 改为列表并相应调整代码。 代码示例中，定义了作业数、工序数和机器数，以及各个任务在不同机器上的加工时间。此外，还包含了一个生成拓扑序 Job 的函数，该函数依据信息素浓度随机生成序列，确保工序顺序的正确性。在这个过程中，为了避免同一个 Job 被重复使用，还设置了记录每个 Job 使用次数的变量。 通过这种方式，不仅优化了求解过程，而且降低了程序实现的难度，提高了算法的效率。这种方法的运用展示了在面对复杂问题时，采用合适的表示方法和算法设计可以显著提升问题求解的性能。在实际应用中，尤其是在调度和优化问题中，类似的策略可以广泛借鉴。