我现在正在为一个客户解决以下问题,该客户将创建最经济的时间表(使用最少的替代品),因为:
- 代课人员应连续代替教师工作尽可能(*不是大问题)
- 替补只能工作6个时段
到目前为止,我有一个教师课程(如下所示)和一个实际上创建最佳时间表的组织者课程。现在我只是让程序循环穿过网格填写每个替代品。
Teacher[] t= new Teacher[14];
Organizer o = new Organizer(t);
o.sort();
int[][] g = o.getGrid();
示例输入:
t[0] = new Teacher("Teacher 1", "Mr", new int[]{1,0,1,0,0,0,0});
t[1] = new Teacher("Teacher 2","Mr", new int[]{1,1,0,1,1,0,1});
t[2] = new Teacher("Teacher 3","Mr", new int[]{0,1,1,1,1,1,0});
t[3] = new Teacher("Teacher 4","Mr", new int[]{1,1,0,1,1,0,1});
t[4] = new Teacher("Teacher 5","Mr", new int[]{1,1,0,0,1,1,1});
t[5] = new Teacher("Teacher 6", "Mr", new int[]{1,1,1,0,0,1,1});
t[6] = new Teacher("Teacher 7", "Mr", new int[]{0,0,1,0,1,1,1});
t[7] = new Teacher("Teacher 8", "Mr", new int[]{1,1,0,0,1,1,1});
t[8] = new Teacher("Teacher 9", "Mr", new int[]{1,1,1,1,1,0,0});
t[9] = new Teacher("Teacher 10", "Mr", new int[]{0,0,0,1,1,1,0});
t[10] = new Teacher("Teacher 11", "Mr", new int[]{0,0,1,0,0,1,1});
t[11] = new Teacher("Teacher 12", "Mr", new int[]{0,0,1,1,0,1,0});
t[12] = new Teacher("Teacher 13", "Mr", new int[]{1,1,1,1,0,0,0});
t[13] = new Teacher("Teacher 14", "Mr", new int[]{1,1,0,1,1,0,1});
上述输出(使用我正在使用的算法):
P1 P2 P3 P4 P5 P6 P7
Teacher 1 1 - 1 - - - -
Teacher 2 2 1 - 1 1 - 1
Teacher 3 - 2 2 2 2 2 -
Teacher 4 3 3 - 3 3 - 3
Teacher 5 4 4 - - 4 3 4
Teacher 6 5 5 4 - - 4 5
Teacher 7 - - 5 - 5 5 6
Teacher 8 6 6 - - 6 6 7
Teacher 9 7 7 6 7 7 - -
Teacher 10 - - - 8 8 7 -
Teacher 11 - - 8 - - 8 8
Teacher 12 - - 9 9 - 9 -
Teacher 13 8 9 10 10 - - -
Teacher 14 9 10 - 11 9 - 10
如您所见,程序只是在有效空间中循环,用 subs 填充它们,直到 sub 达到其最大教学时间,然后开始一个新的 sub。问题是,我已经能够将手动使用的潜艇数量减少到 10 个,所以我一直在尝试找到一种更有效的算法,但无济于事。
对于此输入,使用的最小潜艇数量为 9(受 P2 列约束),因此我想看看是否有任何可能的方法可以完成该数字,或者至少 10 个订阅。提前感谢!
对于每一列,计算出有多少个开放空间。
首先将每个子放入具有最多开放空间的列中,然后随机放置。 该算法将解决您给定的 10 个潜艇问题。
在您的特定示例中,有 59 个空格。 鉴于每个 sub 只能填充 6 个空格,10 是可以工作的最小数量的 sub。 我相信它总能找到一个最佳解决方案。
(我忽略了你的连续天数规则。 "然后随机"规则可以用试图优化它的东西来代替......