SMT生产延误，急需生产排程算法，求大牛指导

嘉立创-高先生

最近SMT贴片出现了交期延误的问题。一个很大的原因是，现在扩展库的物料越来越多。
现在我们有四条生产线，而我们工厂工人现在是同时把所有今天要贴的扩展库物料上到一条生产线上（减少上下料），
但这就导致了其他3条生产线闲着，而忙的这条却一直在排队。
现在我们需要有一个生产排程算法的问题来解决这个问题。核心就是，怎么让其他3条线也忙起来，但同时不要频繁的上下料。

生产排程算法需求：
假如某工厂有N条生产线（C1，C 2，。。。。，目前是4条），计划要生产P个不同的产品（就是线路板贴片，目前同一时间15个以内）。
同一条生产线，只能生产完一个产品后，才能接着生产另外一个产品。
而每个产品中，需要一些物料，如W1，W2，W3....（目前10种以内）。
不同的产品，可能会需要用到同一个物料。
有一个互斥的条件，同一个物料，不能同时出现在2个不同的生产线上。
如，N1生产线，正在生产产品P1，而P1产品，需要M1，M2，M3 这3个物料。
假如P2需要的物料中，有M1这个物料，那么P2这个产品就不能安排生产了，要等P1生产完才能进行安排。
假如P3需要的物料中，与正在生产的其他生产线所用到的物料没有相同的，那么就可以安排P3进行生产（假如有空闲的生产线情况下）。


换成一个吃饭问题来表达：

要贴片的线路板：理解成人
元器件：菜
生产线：放菜的饭桌

有P个人（一般是20人左右）同时来到饭堂要吃饭，饭堂总共有M个固定的菜（一般300个以内，炒好了，假设分量任何人都吃不完），然后有N个放菜的桌子（现在是4个桌子）。
这P个人，每个人要吃的菜可以有多个（一般6个以内），且可能多个人要吃相同的菜。
但是有2个局限：
（1）同一个菜只能送到一桌人（一桌最多5人）面前吃，且必须等这桌人需要的所有菜吃够了，才能安排下一桌人吃饭。
注意：一桌人所需要的菜，必须都送到了才可以开始吃，吃完了后，所有的菜才可以再分配给其他桌的人。
（2）这一桌子上的人，吃菜的时候，是一个人一个人轮流吃，一个菜一个菜的吃。且必须等必须等一桌人都吃完了，才能服务下一桌人。
如果2桌人，要吃的菜都不同，那么可以安排这2桌人同时吃饭（到不同饭桌）。

问题：怎么把这些要吃饭的人进行分组上桌吃饭，使得这些人总体吃饭的效率最快？

注意：
1、暂时不考虑每个人吃菜的速度，就当都一样。
2、暂不考虑服务员换菜的速度，但是一定是换菜的频率越低越好，尽可能不要把菜搬来搬去。

样本数据.zip (11.81 KB)

2018-11-8 17:00 上传

点击文件名下载附件

--------编辑原因-----------
增加了样本数据附件
  

wye11083

话说电阻电容可以每条线挂一盘吧。。贵重芯片确实是个头疼的问题。基本上排线优先排不重料的，然后就是穷举法，以总时间最短为最佳方案。

嘉立创-高先生

阻容这些是基础库的，每条生产线都有，这个不用考虑

nav

在PCB生产前就分开，没有扩展库排一起的半天;
有扩展库等两天排PCB,然后相同的扩展库排一起生产，晚两到三天交货。
这样行吗？

iamseer

一个问题，SMT既然是拼板生产，那么这个规划是发生在拼板前还是拼板后？ 这个问题的自由度会差不少

嘉立创-高先生

iamseer 发表于 2018-11-8 13:39
一个问题，SMT既然是拼板生产，那么这个规划是发生在拼板前还是拼板后？ 这个问题的自由度会差不少
...

PCB拼版不考虑元器件的问题，只是把需要贴片的板子尽量拼在一起。
因此，现在的问题是基于拼版后的。即，一个板子上多少器件，那些器件是已经固定的了

iamseer

20个板子，4条线，300种零件。每个板子还只有6种件，听起来重复料概率很低呀，

每个板子互相穷举一下找到重复的料，然后把有重复板子放到一条线上。在这个量级上好像不太有一次通不过的可能。

或者我考虑太简单了？能提供一些样例数据吗？

嘉立创-高先生

我们找了一天的扩展物料，生成了这个关系图

iamseer

你这图图例呢？ 我猜橙色是板绿色是料？
图片倒是能看出问题的复杂性，但是就一张图片，怎么帮你测试数据呢？

KunShan_a_dai

外行人提个疑问，为啥不能把三个车间的贴片机拼成1条线？

hzpyl

外行人提个疑问，为啥不能把三个车间的贴片机拼成1条线？
+1

嘉立创-高先生

hzpyl 发表于 2018-11-8 15:49
外行人提个疑问，为啥不能把三个车间的贴片机拼成1条线？
+1

那就是都在排队了，不能并行生产

sibin

又是一个时间换空间, 空间换时间的问题!

Vmao

用3+1 方案,就是三条贴通用物料和基础物料,剩余一条包含其他三条线共有的物料之外的所有物料.这样前三条把80%的物料都贴完了,最后一条线贴剩余的

祥子

可以内部统计下使用扩展库的多不。

根据比例，如果一半一半的话（或者其它合适比例）， 那就 在拼板前区分开。

这样 只使用基础库的不受影响。  用了扩展库的，可以延长1天交货好了

嘉立创-高先生

上面讨论的方向都不对，基础库我们每条线都有。这个不讨论基础库。讨论的是扩展库的问题。
扩展库，不可能在拼pcb的时候考虑，因为这个会导致拼版算法的复杂度会呈几何级别的上升。
而且，不管拼版算法怎么高级，也避免不了不同大板之间，物料相互占用的问题。最终到了SMT贴片环节，这个问题还是要面对

嘉立创-高先生

楼主位增加样本数据附件

wwoneway

可以这么理解这个问题不？
四条生产线都有基础物料库，但是每一款扩展物料库是需要每天开工之前加载到其中一条生产线上
那么是不是可以这样考虑？把所有今天需要贴片的板子的扩展物料按照订单编号提取出来建立目录（提取每个订单需要的扩展物料的种类，建立订单与扩展物料之间的一对多的对应关系），同时建立今天需要用到的所有扩展物料种类的总目录A,然后按照所需要的扩展物料种类从多到少的顺序对所有订单进行排序，排好之后取出第1号订单安排到1号生产线，这样就需要把1号订单用到的所有扩展物料都加载到1号生产线上，这时候1号生产线需要的扩展物料目录就出来了，然后从排序表中找到所有能够在1号生产线上生产的订单也全部排到1号生产线上，然后剔除扩展物料库目录A中已经加载到1号生产线上的物料，建立一个新的物料库，称为B物料库，再从剩余订单中找到所有能够在B物料库中生产的订单，按照所需要的扩展物料种类从多到少的顺序对这些订单进行再排序，再取出新的1号订单，连同新1号订单的扩展物料都加载到2号生产线上，然后把剩余订单中能够在2号生产线上生产的所有订单都排到2号生产线上，然后再剔除扩展物料库B中已经用到的扩展物料，建立一个新的剩余扩展物料库C，用类似的方法筛选3号生产线的扩展物料库，最后把剩余订单中剔除了1、2、3号生产线用到的扩展物料库之后还能够生产的订单全部放在4号生产线上。
特殊情况，只需要基础物料库的订单可以合理分配给4条生产线，用来平衡生产效率。
最后再把没排上生产线的订单跟四条生产线的扩展物料库作对比，按缺额最小的方式（暂时闲置的扩展物料不算缺额）排在每条生产线的后面，比如说如果把10号订单排在1号生产线缺1样物料，排在2号生产线缺3样物料，排在2号生产线缺2样物料，排在4号生产线缺5样物料，那就把10号订单排在1号生产线的后面，同时把10号订单缺少的扩展物料所在的生产线上面，用到了缺少的这个扩展物料的所有订单的生产顺序排在最前面，等到这些订单都生产完了，而且1号生产线也闲置下来了，就可以把10号订单缺少的这个物料取下来挂载到1号生产线上了，10号订单就可以生产了

嘉立创-高先生

wwoneway 发表于 2018-11-8 17:13
可以这么理解这个问题不？
四条生产线都有基础物料库，但是每一款扩展物料库是需要每天开工之前加载到其中 ...

你这个是穷举法，算法效率可能是个问题，且不一定是最优的

深圳嘉立创-SMT

iamseer 发表于 2018-11-8 15:34
你这图图例呢？ 我猜橙色是板绿色是料？
图片倒是能看出问题的复杂性，但是就一张图片，怎么帮你测试数据呢 ...

绿色是用使用的元器件.

红色是要贴的板子编号

wkman

  我的看法就是：头痛砍头，脚痛砍脚，，，，，jlc基于客户20多年的pcb文件，做一下数据分析，贴片库去掉不常用的ic元器件，只做最大量部分的了事

xstt

类似有1000个单要做，要是只开1条产线应该可以计算出大概用时，然后是否决定开第2条产线来解决产能问题了。
(生产企业应该用适当的时间和最小的消耗来做完订单?4条全开当我没说啊)

解决点应该是如何评定某个订单过完产线的用时然后对订单进行预排产分析计算了
（只是分析算法内规定了某些订单如果用了相同扩展库就必须用回这条生产线）
1.优先分析出本批订单使用较多的共用扩展库
2.按设定的1/2/3/4产进行调节分配，然后得出生产总用时。

元器件编号        订单使用数
C81598        8
C84256        8
C14445        6
C8678        6
C7248        5
C59782        5
C1934        5
C63855        5
C64982        5
C84062        5
C84170        5
C16422        4
C24452        4
C32565        4
C9378        4
C20526        4
C72037        4
C84635        4
C18536        4
C87992        4

LQS1200

不如想下,能不能自动上飞达

像松下的旧款高速机能装很多飞达

如果能将整个飞达仓自动替换那就完美了

jao317

为什么不两条线贴普料，两条线贴扩展库，或者三条线普料，一条线扩展呢

canspider

用纯数学来表达吧
有M个集合P1 = {1，2，3}， P2={3,4,5},  P3={1,4,6}, P4 ={7,5,9},  ... PM = {5,8,7}
现在要把这些集合重新组合成N个Q，要求Q集合间不能有相同的数，并且Q集合间数字数量尽可能相近
有一些P集合不能放进任何Q集合中，这些不能放进去的P集合数量要最少

上面的例子如果N取2
Q1 = {P1, P3} = {1,2,3,4,6},
Q2 = {P4, PM} = {5,7,8,9},
P2 = {3,4,5}
不能放到任何一个集合中

这类问题和线路板布局是一样的，把没有太大关联的元件尽量放在一起，中间用尽可能少的线连接（剩余的P2）
这类问题没有快速算法，剪除一些不可能的分支后穷举更合适

canspider

那还真不如把 大板编号 做成芯片，元器件编号做成引脚并加上网表
把这一堆芯片扔到PCB画板软件里面去，看看怎么布局连线最干净
这个问题解决了可以作为lceda的一大亮点功能

liliuqun

目前还没发展到这个程度

深圳嘉立创-SMT

canspider 发表于 2018-11-8 20:21
那还真不如把 大板编号 做成芯片，元器件编号做成引脚并加上网表
把这一堆芯片扔到PCB画板软件里面去，看看 ...

做关系图,第一反应我也是想做成PCB图.. 我还真的 做了准便,  做成网络表. 导入到原理图中.   后来发现网络表格式太复杂了,一下子搞不定..
上面的示意图就是我找软件生成的.

liliuqun

上点伟创力SMT车间换拉场景图并介绍下伟创力的换拉作业，伟创力的转拉分在线转拉和离线转拉，在线转拉一般是物殊情况才采用，绝大多数都是离线转拉，转拉部门提前把飞达安装好，换线时整区更换，换线时间在几分钟内

yangff

你这个最优条件是有点问题的（怎么让其他3条线也忙起来，但同时不要频繁的上下料）：
1. 要让上下料次数最少，那就是你说的所有料都上到一条产线上
2. 要让产线利用率最高，那就是要尽可能地调整分配物料让产线尽可能利用

你需要定义，什么叫让3条线忙起来，同时不要频繁上下料。

忙起来是多忙，让总的生产时间最短？如果是这样的话，上下料的时间惩罚是多少？在为了达到总的生产时间最短的这个前提下，我可不可以让你每生产一次就换一下料？上下料的总次数有没有限定？还是说上下料的频率不超过一定的值，但是总的上下料次数可以很多？又或者我希望尽可能少，或者是一开始就把物料规划好，在这个条件下达到一个最优就可以了？

475627406

(2)一个人一个人轮流吃？为嘛不一桌人一起吃，菜都齐了呀。一个大版上的多款只能一款一款做么

嘉立创-高先生

475627406 发表于 2018-11-8 21:27
(2)一个人一个人轮流吃？为嘛不一桌人一起吃，菜都齐了呀。一个大版上的多款只能一款一款做么 ...

这个约束是模拟真实的生产应用场景，这个板子是一片一片的贴。

嘉立创-高先生

yangff 发表于 2018-11-8 20:49
你这个最优条件是有点问题的（怎么让其他3条线也忙起来，但同时不要频繁的上下料）：
1. 要让上下料次数最 ...

这个排产存在两个极端，一个极端就是现在我们产线工人用的方式，把所有的扩展库料全部加到一条生产线上去，这种情形就会导致所有的板子要一个一个的排队。好处呢，就是说它不需要去换料，上料下料。反方向的极端，就是就把一个编号当成一个组，然后去找根这个编号没有相同扩展物料的编号，上到不同的生产线。现在呢，我们要做的事情就是说在这两个极端之中找到一种平衡，就是说几个编号当成一个组，然后呢上到生产线上去，再找几个其他的编号跟他们前面几个编号没有共用物料的，再上到另外一个生产线上去。现在问题就是说怎么分组？

yangff

嘉立创-高先生 发表于 2018-11-8 22:03
这个排产存在两个极端，一个极端就是现在我们产线工人用的方式，把所有的扩展库料全部加到一条生产线上去 ...

我知道你的意思，但是要做算法的话，你需要对这个平衡做出定义。

嘉立创-高先生

yangff 发表于 2018-11-9 02:23
我知道你的意思，但是要做算法的话，你需要对这个平衡做出定义。

这个平衡无法给出定义，只能设置某个变量。如设置某个组里面，编号（大板）的数量N为这个变量。
假设3~5个编号（大板）为最佳组合，然后根据实际的运作效果和数据的情况，来调整这个变量N。可能不是最优，只能是较优

嘉立创-高先生

我觉得这个问题，更像是一个聚类的问题。我另外开了一个帖子
https://www.amobbs.com/thread-5701885-1-1.html?_dsign=f36cdfc3

yplin27

既然物料都是互斥的，那个一个直观的算法就是依次将最热门的物料先放到机器上：

假定
物料为E1,E2,E3...Em
板为B1,B2,B3...Bn
机器为M1,M2,M3...Mo

算法：优先选热门物料，每一轮尽量使更多的物料上到机器上，使用蛮力法

1、从所有物料中选中最热物料 Ei，以及对应的板 Bi1 Bi2 ...
2、分别假设 Bi1 Bi2... 放到第一台机器，算出剩余物料
3、在剩余物料中选出可以贴片的板，算出在可贴片板中最热门物料 Ei2，以及对应的板 Bi21 Bi22...
4、分别假设 Bi21 Bi22...放到第二台机器，算出剩余物料
...
5、重复以上步骤 算出 M1,M2,M3,M4对应组合，选出组合中使用物料数最多的

跑了一下样例数据的结果：

{'396251H4', '396250H2', '396246H2', '396297WH2'}
{'396272H2', '396292WH2', '396244H2', '396296WH2'}
{'396291H2', '396299H2', '396248H2', '396249H2'}
{'396171H2', '396172H2', '396270H2', '396173H2'}
{'396302H4', '396295WH2', '396247H2', '396271H2'}
{'396293WH2', '396294WH2', '396170H2', '396252H4'}
{'396300WH2', '396462G4', '396301WH4', '396298H2'}
{'396273H4', '396416G2', '396455WH4', '396396G2'}
{'396425G4', '396274H4', '396174H2', '396245H2'}

-------------------------------------------

编辑：第一次貌似理解错误了

szman5108

这个骚脑的工作只有大牛能解决，哈哈

xylx1219

请看这样是否可以？
1、先把要生产的每一个产品，计算出跟其他产品有共同使用的元器件数量，暂称为“共用数”。将产品按共用数做降序排列，例如20个产品排序为P1~P20。
2、C1、C2、C3、C4四条生产线，原则是让C1线永远做共用数最高的产品。第一轮生产，C1线贴产品P1，C2线安排生产与P1无共用原件的其他产品中共用数最高的。C3、C4线依次类推。
3、假定C1~C4同时完成生产，即第一轮生产完成。第二轮开始从剩余16个产品中选择共用数最高的产品交给C1线，C2~C4依次排产与前面无交集的共用数最高的产品。

这样，先把共用数高的产品生产完，越往后越有利于四条线的利用率提升。核心原则是排产的重要性（繁忙程度）C1>C2>C3>C4，

前提是假定四条线生产一款产品的时间是相同的，第二轮开始的时候四个产品都生产完了。实际上可能完成有先后，但核心原则是一样的，只是计算更复杂一些。C1生产完马上安排未上线的共用数最高的产品上线，其次C2，再次C3、最后C4。

嘉立创-高先生

xylx1219 发表于 2018-11-9 11:50
请看这样是否可以？
1、先把要生产的每一个产品，计算出跟其他产品有共同使用的元器件数量，暂称为“共用数 ...

楼上兄弟的思路跟我们的思路不谋而合，我们开发团队现在是按照这个思路在做实现

嘉立创-高先生

xylx1219 发表于 2018-11-9 11:50
请看这样是否可以？
1、先把要生产的每一个产品，计算出跟其他产品有共同使用的元器件数量，暂称为“共用数 ...

这个思路不一定是最优解，但是一定是一个可行的方案

javabean

建议搞成4条线串行模式，即一条线贴基础，剩下2条线全部是附加元器件包，最后一条给特殊器件，然后挨个过一遍，可能单PCB时间长了，但总体简单

wowangru

你要的是最优解！！！ 不是完美接    得综合考虑物料换线时间， 板子贴装时间，  机器效率！！！ 达到百分百是不可能，总会有冲突，  算法把冲突降低到最小。 就是找平衡点的问题。一点不换料那就在一条线搞定了。  多线平衡肯定就要换线。     所以你要列出物料换线成本，板子贴装时间，  机器效率损失成本！！！

wowangru

这个算法应该很好计算！！！！穷举 最好的办法  数据量也不大

yplin27

wowangru 发表于 2018-11-9 13:38
这个算法应该很好计算！！！！穷举 最好的办法  数据量也不大

数据量并不小，样本数据36块板，如果不做任何限制条件的排到生产线上的可能性应该是有36!/4!次吧

就算是根据可行性条件进行约束，可能性的排序的量级大概还会有 10e14

wanggoals

先加个基本功能，能否让用户选择只用基础库，我每次都担心加进去扩展库，一个二极管20块钱的费用还是不舍得掏，虽然钱不是我出。
打样追求速度，如果要延时太久了，有时干脆就拿回来自己焊接。

wowangru

yplin27 发表于 2018-11-9 15:36
数据量并不小，样本数据36块板，如果不做任何限制条件的排到生产线上的可能性应该是有36!/4!次吧

就算是 ...

36个大板    4条线，  穷举次数为1632960次！  这点数据量很轻松  另外加上一些额外的运算  也不会高哪去

假设是108个大板4条线，穷举次数是134 789 184次。 也不大！


















以上是错误的算法！！ ， 你说的是正确的可能性有36!/4!次

wowangru

yplin27 发表于 2018-11-9 15:36
数据量并不小，样本数据36块板，如果不做任何限制条件的排到生产线上的可能性应该是有36!/4!次吧

就算是 ...

这是上板的排序穷举！！！ 如果非得进行上料的穷举，那是没法算的， 假设每个大板100种料，进行穷举，会成天文数字，但是这里的穷举意义并不是很大，，无非是解决四条线在这个时刻有同时对一种料有需求，整体最优解中这种情况会很少，如果出现过多这种情况，那肯定不会是最优解， 因为这种情况无论如何都会换料，换料无论先后都会影响到本次的时间。最快的方式肯定是用量最少的先上。这样运算会有点误差，但基本接近本次最优解。  另外一个就是实际换料时间，板生产时间要和软件设定一致，如果四条线没按照软件计算节拍。那软件就白算了。。。。

yj_yulin

这只是一个简单地想法而已,根本不是最优,假如今天的产品全部都有物料M1,那又会变成排队了

nav

wanggoals 发表于 2018-11-9 15:49
先加个基本功能，能否让用户选择只用基础库，我每次都担心加进去扩展库，一个二极管20块钱的费用还是不舍得 ...

支持+1

我理解现在做Pcb时分两种：有贴片，无贴片，改为分三种：无贴片，基础贴片，扩展贴片。
然后基础贴片保证交期，扩展的随他去吧

771749862

这样不是更好么