序列问题如何仿真优化？

jimmyz

    最近接触到PCB制造行业中电镀工序的一个仿真问题，拿出来与大家一起讨论一下。
    先说背景：电镀池调度，学术上归纳为抓钩调度问题，抓钩需要在节拍时间内完成不同电镀池中的调转作业，是一类强NP约束问题。抓钩程序是写进PLC的，因此，如何安排PLC循环（亦即节拍时间），使得效率和产出最高，是优化目标。当然，我们这里不是要讨论PLC程序的设计问题，而是挂板的问题。PCB行业的电镀板分为正片和负片两种备选工艺，正片电镀40分钟，负片电镀90-180分钟，另外正片电镀结束了需要图形电镀，负片则不需要。在本案例中，抓钩循环时间为6分钟。排产甘特图见附件1所示。
    假设正片和负片分别有100片，正片电镀时间40分钟，负片90-180分钟（90,120,150,180）平均分布。因为电镀过程中，抓钩是程序写死的，只能6分钟上下板一次，因此合理的安排序列，最理想的状况是每到6分钟，即有不多不少的一挂板完成，利用率最高。但实际情况是，到了6分钟的周期，没有板电镀完，抓钩程序暂停，浪费产能；或者到了6分钟，有多挂板完工，而抓钩一次只能抓一挂板，另外的板需要等待抓钩，浪费电镀池产能。
    目标通过挂板时的优化正负片序列，使得正负片组合优化后，总体等待时间最短。
    解决方法1，如果使用APS高级计划排产工具，需要另行开发优化模块，但需要考虑的是计算规模太过庞大,2，使用排产工具，在不同的排产策略（静态规则）下，排定几组正负片序列，并用仿真运行统计等待时间，择优选用，3，使用仿真工具将正负片的选择定为0.5的随机过程，仿真在不同的随机数种子下（500个？）运行，统计结果并选取最优的序列。
    问题常用的仿真优化，是使用OPT-QUEST或者自己开发的优化模块（如遗传算法），对仿真模型的参数进行优化，是属于组合优化问题；而本案例属于序列优化，有没有办法将序列优化转化为组合优化建模？
   

jimmyz

taoyifei2000 发表于 2015-6-5 16:41
描述不是很详细，根据个人理解，说说你列举的解决方法：方法1，APS落实到具体问题，需要具体的模型和算法支 ...

恩，谢谢回复。
遗传算法我也考虑过，但是这个序列还有一个约束，正负片分别有100片（一天的任务量），那么简单表示为：0100010011100...来表示，其中100个0，100个1，我还没仔细想过遗传算法中基因编码与解码的问题，可能难点也就在这里。

jimmyz

taoyifei2000 发表于 2015-6-5 16:41
描述不是很详细，根据个人理解，说说你列举的解决方法：方法1，APS落实到具体问题，需要具体的模型和算法支 ...

另外一个方面，我用的是SIMIO软件，模型和优化插件之间怎么建立接口也是需要考虑的问题，可能还需要做一些开发，使模型和优化模块能交换数据。如果是参数优化，SIMIO软件中有自带的Experiment模块直接可用

rwj_238

比较适合用 数学规划类的软件来做。显然离散事件系统仿真不是一个最佳的方案，希望对您有所帮助。

yuge007

我也遇到过这个问题