主要观点:
- 介绍了热门手游《Hay Day》,包括其基本玩法、主要资源和订单系统等。
- 提出《Hay Day》中的调度问题,即随着游戏进程,货物和机器的排列组合增多,出现调度难题,目标是优化订单的制造跨度(makespan)。
- 讨论了解决该问题的方法,如遗传算法、退火、禁忌搜索、蚁群优化等,作者选择使用混合整数线性规划(MILP),并通过 Google OR-Tools 实现。
- 展示了使用 OR-Tools 解决 FJSP 问题的代码,包括导入库、加载任务数据、定义变量和约束、设置目标以及求解和输出结果等步骤,最终找到多个逐步优化的解决方案。
- 得出结论,通过整数规划和 OR-Tools 可以解决《Hay Day》中的调度问题,同时强调不能创建用于游戏的 bot,应享受游戏本身。
关键信息:
- 《Hay Day》是 2012 年 Supercell 创作的手游,可种植作物、饲养动物等,是免费游戏。
- 调度问题涉及订单、机器、货物及生产时间等,是一个灵活作业车间调度问题(FJSP)。
- MILP 是数学优化方法,OR-Tools 是用于解决组合优化问题的开源软件套件。
- 代码通过定义各种变量和约束,利用 OR-Tools 求解并输出多个解决方案及相关统计信息。
重要细节:
- 游戏中订单是需制造的货物集合,机器一次只能生产一种货物且需具备所需货物,货物只能在特定机器上生产。
- 示例展示了简单和复杂的调度情况,FJSP 是作业车间调度问题(JSSP)的变体。
- 代码中定义了
SolutionPrinter
类用于打印中间解决方案,加载任务数据并创建 CP 模型,添加各种约束条件,以最小化 makespan 为目标,最后求解并输出结果。 - 强调创建游戏 bot 违反游戏政策,应享受游戏本身。
- 提供了相关资源链接,如《Hay Day Good list》等。
**粗体** _斜体_ [链接](http://example.com) `代码` - 列表 > 引用
。你还可以使用@
来通知其他用户。