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

“每个集合组中的数字元素，与另外一个集合组没有相同的数字元素”这个条件反过来说就是，如果两个集合中有相同元素，他们在同一个集合集里，那么这就很好做了

1. 如果两个集合有相同元素，就把他们合并，这个可以用并查集做
2. 这样会得到若干个互不相交的集合的集合，这个情况下，每个集合中的元素都是最少的
3. 如果这时候有超过4个集合，可以任取两个合并，直到满足要求

“但不能超过5个集合组成”这个条件并不总能满足，例如，一开始20个集合中，每个都有"1"，那么无论怎么分配，都只会有一种结果，也就是20个集合全被分配在一起。

但是，第三步的时候，每次选择包含集合最少的两组合并，可以保证最后结果中，包含集合最多的集合所包含的集合最少…… （真绕……

1. for all Set S in Sets
   
2.   for all elements E in S
   
3.     merge(E, S[0])
   
4. 
   
5. for all Set S in Sets
   
6.   Group[findparent(S[0])].append(S)
   
7. 
   
8. while (Group.count > 4)
   
9.   MergeSmallestGroups
   
10. 
    

复制代码

myxiaonia

以前学过都还给老师，去学习聚类分析吧，而且我记得是统计分析里比较好懂的

gongxd

聚类需要计算所有元素之间的“距离”，先确定参数计算“距离”，就可以聚类了

嘉立创-高先生

yangff 发表于 2018-11-10 02:02
“每个集合组中的数字元素，与另外一个集合组没有相同的数字元素”这个条件反过来说就是，如果两个集合中有 ...

“1. 如果两个集合有相同元素，就把他们合并，这个可以用并查集做”，
这一步，从目前的数据来看，基本会把所有的集合都装进去

yj_yulin

单纯的考虑肯定是不行的,这个要考虑的因素还是不少的,
上料时间,装板时间, 焊接时间,换料时间,
这是一个比较经典的生产排程, 最好还有动态规划可以解决产线出现的意外
运筹学中都已经有解决理论,只需要合适的建模就可以,不过要实际和生产对接起来,还是要数据接口

yangff

嘉立创-高先生 发表于 2018-11-10 09:59
“1. 如果两个集合有相同元素，就把他们合并，这个可以用并查集做”，
这一步，从目前的数据来看，基本会 ...

那你只能把“每个集合组中的数字元素，与另外一个集合组没有相同的数字元素”这个条件去掉

xiaoergao

现在smt排程怎么样了，最近做板子好像时间最长的都是在smt 这边要将近2天+。之前好像基本一天之内

嘉立创-高先生

还在调整中，下周会有生产分组上线，应该能改善