SMT生产排程算法演绎成聚类算法?
前面我发了一个帖子,讲述了SMT排程算法的问题。我觉得这个应该是一个聚类的问题。因此,我把这个问题变成下面的描述:https://www.amobbs.com/thread-5701844-1-1.html
集合分组问题:
有大概20个集合,每个集合里面有N个数字元素(数值范围为1~10000,N一般不超过10),举例如下:
集合1:{1,3,5,20 }
集合2:{3,5,9,100}
集合3:{13,15,39,40,99}
。。。。直到集合N。
集合组:由N个集合组成,如上面集合1和集合2组成的集合组就是:
{1,3,5,9,20,100}
求:在当前20个集合中,找出X个(X不大于4)集合组,每个集合组中的数字元素,与另外一个集合组没有相同的数字元素。
要求,每个集合组中的集合数量越多越好(但不能超过5个集合组成)。
这种问题,应该是用什么聚类算法来解决?
本帖最后由 yangff 于 2018-11-10 02:20 编辑
“每个集合组中的数字元素,与另外一个集合组没有相同的数字元素”这个条件反过来说就是,如果两个集合中有相同元素,他们在同一个集合集里,那么这就很好做了
1. 如果两个集合有相同元素,就把他们合并,这个可以用并查集做
2. 这样会得到若干个互不相交的集合的集合,这个情况下,每个集合中的元素都是最少的
3. 如果这时候有超过4个集合,可以任取两个合并,直到满足要求
“但不能超过5个集合组成”这个条件并不总能满足,例如,一开始20个集合中,每个都有"1",那么无论怎么分配,都只会有一种结果,也就是20个集合全被分配在一起。
但是,第三步的时候,每次选择包含集合最少的两组合并,可以保证最后结果中,包含集合最多的集合所包含的集合最少…… (真绕……
for all Set S in Sets
for all elements E in S
merge(E, S)
for all Set S in Sets
Group)].append(S)
while (Group.count > 4)
MergeSmallestGroups
以前学过都还给老师,去学习聚类分析吧,而且我记得是统计分析里比较好懂的 聚类需要计算所有元素之间的“距离”,先确定参数计算“距离”,就可以聚类了 yangff 发表于 2018-11-10 02:02
“每个集合组中的数字元素,与另外一个集合组没有相同的数字元素”这个条件反过来说就是,如果两个集合中有 ...
“1. 如果两个集合有相同元素,就把他们合并,这个可以用并查集做”,
这一步,从目前的数据来看,基本会把所有的集合都装进去 单纯的考虑肯定是不行的,这个要考虑的因素还是不少的,
上料时间,装板时间, 焊接时间,换料时间,
这是一个比较经典的生产排程, 最好还有动态规划可以解决产线出现的意外
运筹学中都已经有解决理论,只需要合适的建模就可以,不过要实际和生产对接起来,还是要数据接口 嘉立创-高先生 发表于 2018-11-10 09:59
“1. 如果两个集合有相同元素,就把他们合并,这个可以用并查集做”,
这一步,从目前的数据来看,基本会 ...
那你只能把“每个集合组中的数字元素,与另外一个集合组没有相同的数字元素”这个条件去掉 现在smt排程怎么样了,最近做板子好像时间最长的都是在smt 这边要将近2天+。之前好像基本一天之内 还在调整中,下周会有生产分组上线,应该能改善
页:
[1]