Cycle time analysis for wafer revisiting process in scheduling of single-arm cluster tools

Some wafer fabrication processes performed by cluster tools require revisiting. With wafer revisiting, a cluster tool is very difficult to be scheduled due to a large number of possible schedules for the revisiting process. Atomic layer deposition (ALD) is a typical process with wafer revisiting that should be performed by cluster tools. This paper discusses the scheduling problem of single-arm cluster tools for the ALD process. In scheduling such a system, the most difficult part is to schedule the revisit...     

Rule-based scheduling in wafer fabrication with due date-based objectives

Wafer fabrication is a capital-intensive and highly complex manufacturing process. In the wafer fabrication facility (fab), wafers are grouped as a lot to go through repeated sequences of operations to build circuitry. Lot scheduling is an important task for manufacturers to improve production efficiency and meet customers’ requirements of on-time delivery. In this research we propose a dispatching rule for lot scheduling in wafer fabs, focusing on three due date-based objectives: on-time delivery rate, mean tardiness, and maximum tardiness. Although many dispatching rules have been proposed in the literature, they usually perform well in some objectives and bad in others. Our rule implements good principles in existing rules by means of (1) an urgency function for a single lot, (2) a priority index function considering total urgency of multiple waiting lots, (3) a due date extension procedure for dealing with tardy lots, and (4) a lot filtering procedure for selecting urgent lots. Simulation experiments are conducted using nine data sets of fabs. Six scenarios formed by two levels of load and three levels of due date tightness are tested for each fab. Performance verification of the proposed rule is achieved by comparing with nine benchmark rules. The experimental results show that the proposed rule outperforms the benchmark rules in terms of all concerned objective functions.     

Manufacturing cell design using simulated annealing: An industrial application

In this paper, we give a brief summary of simulated annealing (SA) procedures used to solve combinatorial optimization problems. We then present the manufacturing cell design problem which consists of designing cells of limited size in order to minimize inter-cell traffic. We show how to use a SA approach to obtain a good, if not optimum, solution to this problem. Finally, we apply this approach to an industrial problem and compare the results to the ones obtained using the so-called twofold heuristic algorithm.     

Flow-shop sequencing using hybrid simulated annealing

Simulated annealing (SA) heuristics have been successfully applied on a variety of complex optimization problems. This paper presents a new hybrid SA approach for the permutation flow-shop scheduling (FSS) problem. FSS is known to be NP-hard, and thus the right way to proceed is through the use of heuristics techniques. The proposed approach combines the characteristics of a canonical SA procedure together with features borrowed from the field of genetic algorithms (GAs), such as the use of a population of individuals and the use of a novel, non-standard recombination operator for generating solutions. The approach is easily implemented and performs near-optimal schedules in a rather short computation time. Experiments over multiple benchmarks test problems show that the developed approach has higher performance than that of other FSS meta-heuristic approaches, generating schedules of shorter makespans faster. The experiments include comparisons between the proposed hybrid model, a genetic algorithm, and two other standard simulated annealing approaches. The final solutions obtained by the method are within less than 1% in average from the optimal solutions obtained so far.     

Decomposition-based classified ant colony optimization algorithm for scheduling semiconductor wafer fabrication system

Due to its typical features, such as large-scale, multiple re-entrant flows, and hybrid machine types, the semiconductor wafer fabrication system (SWFS) is extremely difficult to schedule. In order to cope with this difficulty, the decomposition-based classified ant colony optimization (D-CACO) method is proposed and analyzed in this paper. The D-CACO method comprises decomposition procedure and classified ant colony optimization algorithm. In the decomposition procedure, a large and complicate scheduling problem is decomposed into several subproblems and these subproblems are scheduled in sequence. The classified ACO algorithm then groups all of the operations of the subproblems and schedules them according to machine type. To test the effect of the method, a set of simulations are conducted on a virtual fab simulation platform. The test results show that the proposed D-CACO algorithm works efficiently in scheduling SWFS.     

基于蚁群算法的半导体生产线调度方法研究

为了解决具有可重入特性的半导体生产线调度问题,提出基于蚁群算法的半导体生产线调度模型（ASWFSM）。在模型中,利用图论的方法把调度方案的寻优过程转换为蚂蚁对有向图的搜索,并且,引入专家系统作为推理机避免了寻优过程中对可行节点判断的复杂性。仿真试验证明,此模型具有良好的调度效果和稳定性。     

A simulated annealing algorithm for the job shop cell scheduling problem with intercellular moves and reentrant parts

This paper addresses the problem of scheduling parts in job shop cellular manufacturing systems by considering exceptional parts that need to visit machines in different cells and reentrant parts which need to visit some machines more than once in non-consecutive manner. Initially, an integer linear programming (ILP) model is presented for the problem to minimize the makespan, which considers intercellular moves and non-consecutive multiple processing of parts on a machine. Due to the complexity of the model, a simulated annealing (SA) based solution approach is developed to solve the problem. To increase the efficiency of the search algorithm, a neighborhood structure based on the concept of blocks is applied. Subsequently, the efficiency of the ILP model and the performance of the proposed SA are assessed over a set of problem instances taken from the literature. The proposed ILP model was coded in Lingo 8.0 and the solution obtained by the proposed SA was compared to the optimal values. The computational results demonstrate that the proposed ILP model and SA algorithm are effective and efficient for this problem.     

Applying simulated annealing for designing cellular manufacturing systems using MDmTSP

The design of cellular manufacturing systems involves many structural and operational issues. One of the important design steps is the formation of part families and machine cells (cell formation). Despite a large number of papers on cell formation published worldwide, only a handful incorporates operation sequence in layout design (intra-cell move calculations). We propose a solution to solve the part-family and machine-cell formation problem considering the within-cell layout problem, simultaneously. In this paper, the cellular manufacturing system is formulated as a multiple departures single destination multiple travelling salesman problem (MDmTSP) and a solution methodology based on simulated annealing is proposed to solve the formulated model. Numerical examples show that the proposed method is efficient and effective in finding optimal solutions. The results also indicate that the proposed approach performs well compared to some well-known cell formation methods.     

基于eM-Plant的虚拟晶圆制造自动组合装置

针对难以用解析法验证半导体加工装置的调度可行性问题,提出仿真建模研究的新方法。利用仿真软件eM-Plant建立晶圆制造中单臂自动组合装置的参数化仿真模型,构建一个虚拟的晶圆制造系统。该系统为研究自动组合装置控制问题提供有效手段,是验证半导体制造生产调度可行性的仿真平台。     

融合K-调和均值和模拟退火粒子群的混合聚类算法

针对K-调和均值和模拟退火粒子群聚类算法的优缺点,提出了1种融合K-调和均值和模拟退火粒子群的混合聚类算法。首先通过K-调和均值方法将粒子群分成若干个子群,每个粒子根据其个体极值和所在子种群的全局极值来更新位置。同时引入模拟退火思想,抑制了早期收敛,提高了计算精度。本文使用Iris、Zoo、Wine和Image Segmentation,4个数据库,以F-measure为评价聚类效果的标准,对混合聚类算法进行了验证。研究发现,该混合聚类算法可以有效地避免陷入局部最优,在保证收敛速度的同时增强了算法的全局搜索能力,明显改善了聚类效果。该算法目前已用于无锡一淡水养殖基地的水产健康养殖水质分析系统,运行效果良好。     

遗传模拟退火算法在服装排料中的研究

提出了一种基于遗传模拟退火算法的启发式排样算法,并将这种算法应用于服装排样领域以减少原料的浪费。该算法通过基于遗传模拟退火算法的全局优化概率搜索,寻找排样件在排样时的最优次序及各自的旋转角度,然后采用基于左下角(BL)策略的启发式排样算法实现自动排样。     

聚类问题的自适应杂交差分演化模拟退火算法

针对K-均值聚类算法对初始值敏感和易陷入局部最优的缺点,提出了一个基于自适应杂交差分演化模拟退火的K-均值聚类算法。该算法以差分演化算法为基础,通过模拟退火算法的更新策略来增强全局搜索能力,并运用自适应技术来选择学习策略、确定算法的关键参数。实验结果表明,该算法能较好地克服传统K-均值聚类算法的缺点,具有较好的全局收敛能力,且算法稳定性强、收敛速度快,将新算法与传统的K-均值聚类算法以及最近提出的几个同类聚类算法进行了比较。     

改进的退火遗传优化策略应用研究

地震参数反演属于典型的非线性优化问题。针对遗传算法和模拟退火算法各自的优缺点,将改进的遗传算法与模拟退火算法相结合,提出了改进的退火遗传算法（ISAGA）。该方法通过筛选和修复进行初始种群的选择,采用允许父代参与竞争的退火选择机制,并根据模拟退火思想对交叉和变异概率进行自适应的调整,从而增加了种群的多样性并提高了收敛速度。该方法既具备了遗传算法强大的全局搜索能力,也拥有模拟退火算法强大的局部搜索能力。经理论模型试算结果表明,该方法不仅收敛速度快,优化精度高,抗干扰能力强,而且避免了局部收敛和依赖初始模型等问题,计算所得反演参数更接近于实际观测值。     

基于SA组合算法的SVM参数选取

针对传统方法的不足,提出将一种模拟退火组合算法用于支持向量机的参数选择,将优化指标设定为最大化SVM的泛化能力,并据此确立适当的目标函数;同时借鉴交叉检验的思想,建立以训练集和测试集中的数据分别选择模型和搜索最优参数组合的研究手段。最后,在仿真实验的基础上同基于遗传算法和精化网格法的选取方法进行了对比分析,结果表明该组合算法具有更好的全局搜索性能和收敛速度,是SVM参数选取的一种有效方法,具有较强的实用价值。     

Minimizing makespan in a flow shop with two batch-processing machines using simulated annealing

This paper aims at minimizing the makespan of two batch-processing machines in a flow shop. The processing times and the sizes of the jobs are known and non-identical. The machines can process a batch as long as its capacity is not exceeded. The processing time of a batch is the longest processing time among all the jobs in that batch. The problem under study is NP-hard for makespan objective. Consequently, a heuristic based on Johnson's algorithm and a simulated annealing (SA) algorithm is proposed. Random instances were generated to verify the effectiveness of the proposed approaches. The results obtained from SA were compared with the proposed heuristic and a commercial solver. The SA outperformed both the heuristic and the commercial solver. On larger problem instances, the heuristic outperformed the commercial solver.     

基于模拟退火的多标记数据特征选择

多标记数据有很多的冗余特征和数据,为了解决多标记数据中冗余和无关特征,提高多标记学习算法的泛化能力。提出一个基于模拟退火的卷积式特征选择方法——SAML(simulated annealing based feature selection for multi-label data),已有的算法只是使用了遗传算法来进行优化,新算法采用模拟退火来寻找最优子集,其效果在已有的工作中表现出比前者遗传算法更好的效果。在用于公开评测的Yahoo网页分类数据集上的实验结果表明,SAML算法的性能优于新近提出的一些流行的多标记特征选择方法。     

Metamodeling by symbolic regression and Pareto simulated annealing

The subject of this paper is a new approach to symbolic regression. Other publications on symbolic regression use genetic programming. This paper describes an alternative method based on Pareto simulated annealing. Our method is based on linear regression for the estimation of constants. Interval arithmetic is applied to ensure the consistency of a model. To prevent overfitting, we merit a model not only on predictions in the data points, but also on the complexity of a model. For the complexity, we introduce a new measure. We compare our new method with the Kriging metamodel and against a symbolic regression metamodel based on genetic programming. We conclude that Pareto-simulated-annealing-based symbolic regression is very competitive compared to the other metamodel approaches.     

基于自适应遗传模拟退火算法的矩形件排样

研究一种自适应遗传模拟退火算法,应用于矩形件优化排样问题。以整数编码矩形件的排样序列,采用经验选择与随机生成相结合的策略构造初始种群。运用自适应交叉和变异概率动态地控制遗传算法的收敛速度,通过模拟退火算法引导全局最优搜索,采用启发式最低水平线择优算法对排样序列进行解码,形成排样方式。多组对比实验结果表明,自适应遗传模拟退火算法求解速度较快,可以有效提高板材的利用率。     

基于模拟退火粒子群算法的FCM聚类方法

针对模糊C-均值（FCM）聚类算法易陷入局部极小值和对初始值敏感的缺点,提出了一种基于模拟退火粒子群优化的模糊聚类算法。该算法利用粒子群强大的全局寻优能力和模拟退火算法跳出局部极值的能力,克服了模糊C-均值聚类算法的不足。实验表明,该算法有很好的全局收敛性,能够较快地收敛到最优解。     

晶圆表面缺陷模式的在线探测与自适应识别研究

晶圆表面的缺陷通常反映了半导体制造过程存在的异常问题,通过探测与识别晶圆表面缺陷模式,可及时诊断故障源并进行在线调整。提出了一种晶圆表面缺陷模式的在线探测与自适应识别模型。首先该模型对晶圆表面的缺陷模式进行特征提取,基于特征集对每种晶圆模式构建相应的隐马尔科夫模型（Hidden Markov Model,HMM）,并提出基于HMM动态集成的晶圆缺陷在线探测与识别方法。提出的模型成功应用于WM-811K数据库的晶圆缺陷检测与识别中,实验结果充分证明了该模型的有效性与实用性。