微电子生产过程调度问题基于指标快速预报的分解算法

An indexes fast prediction based decomposition method for scheduling problem in microelectronic production process

微电子生产过程调度问题具有规模大和约束复杂等特点,如菜单、Setup时间和组批约束等,其优化调度具有一定难度.针对以最小化平均流经时间为调度目标的较大规模微电子生产过程调度问题,提出一种基于指标快速预报的分解方法(DM-IFP).首先,通过松弛不可中断约束,设计一种代理方法,即基于机器负载的操作完工时间快速预测方法(CTP-ML);其次,设计基于CTP-ML的问题分解方法,将原问题迭代分解为多个连续交迭的子问题;然后,提出一种基于双信息素的蚁群算法(ACO-D)用于求解分解后的子问题,其全局调度目标采用CTP-ML获取,有效保证了全局优化性能;最后,针对一些不同规模的仿真数据,将所提出方法与一些代表性的算法进行详尽的数值对比,计算结果表明所提出方法在所获解的质量和收敛性上均有改善.

The scheduling problem in the microelectronic production process has some characteristics including large scale and complex constraints,such as recipe constraint,Setup time,batch capacity and so on.It is difficult to obtain the optimal solution.For the problem with the objective of minimizing the mean cycle time,this paper proposes an indexes fast prediction based decomposition method(DM-IFP).Firstly,after relaxing the non-preemptive constraint,a surrogate method,i.e.,the fast prediction method of operation completion time based on the machine load(CTP-ML),is proposed.Then,a CTP-ML based problem decomposition method is designed to decompose the original problems into several consecutive and overlapped subproblems.A double pheromones based ant colony optimization(ACO)algorithm is proposed to solve the subproblem,in which the CTP-ML is applied to obtain the global scheduling objective of each subpropblem so that the original scheduling problem is optimized.Finally,based on some simulated data with different scale,sufficient computational comparisons are provided between the proposed DM-IFP and some representative algorithms.It is shown that the proposed method generates better results in terms of quality and convergence.