It’s developed by my best companions-Zibo Chan,Yifan Zhu,and me. We shared a fantastic week to complete this project and achieved 100 grade at 2018’s summer. Many thanks to my friends who once gave me advice on some details of this project. And many thanks to 张老师.
介绍
要解决的问题:现在有若干个商品等待加工,加工厂的加工机器有限,每一个商品都需要N道加工工序,并且在指定的机器加工指定市场完成整体加工,如何组织加工工作让这若干个商品加工时间最小化?
限制:
- 一旦开始加工就不能停止
- 存在较多机器冲突,要保证时间越短越好
- 需要基本的GUI,并且在命令行实时展示当前加工情况,最后能够生成加工任务的整体甘特图
- 有时候需要加入针对某台机器的检修指令,在命令行中加入指令
遗传算法
个人认为,遗传算法是一种随机化优化方法,这种思想的应用领域也很广。 在算法初始阶段,它会随机生成一组可行解,也就是第一代染色体。 然后采用适应度函数分别计算每一条染色体的适应度,并根据适应度计算每一条染色体在下一次进化中被选中的概率。 上面都是准备过程,下面正式进入进化过程。
通过交叉,生成N-M条染色体; 再对交叉后生成的N-M条染色体进行变异操作; 然后为了保留上一代优秀的染色体,使用复制的方式生成M条染色体; 到此为止,N条染色体生成完毕!紧接着分别计算N条染色体的适应度和下次被选中的概率。
这就是一次进化的过程,紧接着进行新一轮的进化。
任务分工
- (我)通过同步机制加入检修
- (我)通过ege图形库维护GUI
- (阿朱)辅助数据维护
- (陈博)主要算法编写
展示
- 任务概况
- 测试用例 每一行为:第1~N道工序,需要指定在哪个机器上加工多长时间
- Gantte图展示