Modelling and analysis of wafer fabrication scheduling via generalized stochastic Petri net and simulated annealing

Some of the important characteristics of the semiconductor wafer fabrication factories are re-entrant process flows, a dynamic and uncertain environment, stringent production control requirements, etc. that pose a major challenge to the scheduling decisions in integrated circuit wafer fabrication process. Keeping in view the high capital investment and quick response to the market changes, it is essential for the integrated circuit fabrication process to exercise effective control on its production operations so that production resources can be employed in a flexible and efficient manner. The present research has focussed on the development of a generalized stochastic Petri net model that faithfully captures dynamic behaviours such as re-entrant processing, machine failures, loading and unloading, etc., pertaining to wafer fabrication. A simulated annealing-based scheduling strategy using mean cycle time and tardiness as performance measures was also developed to obtain an efficient and robust schedule for a known hard problem. Analysis of variance was applied to examine the interaction effects of various scheduling rules and to identify the main as well as the interaction effects of dispatching rules, dispatching rules and set-up rules, and set-up rules and batching rules. Paired t-tests were applied to assess the performance of rule combinations for lot and batch scheduling. The proposed simulated annealing-based solution methodology was tested on a well-known data set adopted from the literature and its performance reveals that simulated annealing-based scheduling rules work better than existing rules in terms of the two performance measures mean cycle time and tardiness.     

A study of scheduling rules of flexible manufacturing systems: A simulation approach

This study examines the effects of scheduling rules on the performance of flexible manufacturing systems (FMSs). Several machine and AGV scheduling rules are tested against the mean flowtime criterion. In general, scheduling rules are widely used in practice ranging from direct applications as a stand-alone scheduling scheme to indirect application as a part of complicated scheduling systems. In this paper, we compare the rules under various experimental conditions by using an FMS simulation model. Our objective is to measure sensitivity of the rules to changes in processing time distributions, various levels of breakdown rates, and types of AGV priority schemes. A comprehensive bibliography is also presented in the paper.     

A heuristic model for dynamic flexible job shop scheduling problem considering variable processing times

In real scheduling problems, unexpected changes may occur frequently such as changes in task features. These changes cause deviation from primary scheduling. In this article, a heuristic model, inspired from Artificial Bee Colony algorithm, is proposed for a dynamic flexible job-shop scheduling (DFJSP) problem. This problem consists of n jobs that should be processed by m machines and the processing time of jobs deviates from estimated times. The objective is near-optimal scheduling after any change in tasks in order to minimise the maximal completion time (Makespan). In the proposed model, first, scheduling is done according to the estimated processing times and then re-scheduling is performed after determining the exact ones considering machine set-up. In order to evaluate the performance of the proposed model, some numerical experiments are designed in small, medium and large sizes in different levels of changes in processing times and statistical results illustrate the efficiency of the proposed algorithm.     

An improved imperialist competitive algorithm based photolithography machines scheduling

Abstract: Photolithography machine is one of the most expensive equipment in semiconductor manufacturing system, and as such is often the bottleneck for processing wafers. This paper focuses on photolithography machines scheduling with the objective of total completion time minimisation. In contrast to classic parallel machines scheduling, it is characterised by dynamical arrival wafers, re-entrant process flows, dedicated machine constraints and auxiliary resources constraints. We propose an improved imperialist competitive algorithm (ICA) within the framework of a rolling horizon strategy for the problem. We develop a variable time interval-based rolling horizon strategy to decide the scheduling point. We address the global optimisation in every local scheduling by proposing a mixed cost function. Moreover, an adaptive assimilation operator and a sociopolitical competition operator are used to prevent premature convergence of ICA to local optima. A chaotic sequence-based local search method is presented to accelerate the rate of convergence. Computational experiments are carried out comparing the proposed algorithm with ILOG CPLEX, dispatching rules and meta-heuristic algorithms in the literature. It is observed that the algorithm proposed shows an excellent behaviour on cycle time minimisation while with a good on time delivery rate and machine utilisation rate.     

Scheduling a dynamic flexible flow line with sequence-dependent setup times: a simulation analysis

This paper presents a simulation-based experimental study of scheduling rules for scheduling a dynamic flexible flow line problem considering sequence-dependent setup times. A discrete-event simulation model is presented as well as eight adapted heuristic algorithms, including seven dispatching rules and one constructive heuristic, from the literature. In addition, six new proposed heuristics are implemented in the simulation model. Simulation experiments are conducted under various conditions such as setup time ratio and shop utilisation percentage. One of the proposed rules performs better for the mean flow time measure and another one performs better for the mean tardiness measure. Finally, multiple linear regression based meta-models are developed for the best performing scheduling rules.     

Modified drum–buffer–rope scheduling mechanism for a non-identical parallel machine flow shop with processing-time variation

The drum–buffer–rope (DBR) is a scheduling mechanism under the Theory of Constraints (TOC) philosophy. In DBR, ‘drum’ is a production schedule on the capacity-constrained resources (CCRs), which controls the speed of production for the whole system; ‘rope’ is a mechanism to release the required material to the CCRs; and ‘buffer’ is used to protect the CCRs from starvation due to statistical fluctuations. For a non-identical parallel machine flow-shop environment, estimating an efficient rope and time buffer for DBR implementation is not an easy task because of the complexity of non-identical parallel machine loading. This paper proposes a new scheduling method, which is called the modified DBR (MOD-DBR). It applies a backward finite capacity scheduling technique, including machine loadings and detail scheduling, instead of the rope mechanism in DBR. The scheduling performances of MOD-DBR are evaluated under variable processing time situations. The experimental results indicate that the MOD-DBR without a time buffer outperformed the DBR with a considerable level of buffer on the average flow time, while they have the same performance on tardiness, constraint resource utilization, and throughput.     

Extracting priority rules for dynamic multi-objective flexible job shop scheduling problems using gene expression programming

In this paper, two new approaches are proposed for extracting composite priority rules for scheduling problems. The suggested approaches use simulation and gene expression programming and are able to evolve specific priority rules for all dynamic scheduling problems in accordance with their features. The methods are based on the idea that both the proper design of the function and terminal sets and the structure of the gene expression programming approach significantly affect the results. In the first proposed approach, modified and operational features of the scheduling environment are added to the terminal set, and a multigenic system is used, whereas in the second approach, priority rules are used as automatically defined functions, which are combined with the cellular system for gene expression programming. A comparison shows that the second approach generates better results than the first; however, all of the extracted rules yield better results than the rules from the literature, especially for the defined multi-objective function consisting of makespan, mean lateness and mean flow time. The presented methods and the generated priority rules are robust and can be applied to all real and large-scale dynamic scheduling problems.     

Dynamic state-dependent dispatching for wafer fabrication

A dynamic state-dependent dispatching (DSDD) heuristic for a wafer fabrication plant is presented. The DSDD heuristic dynamically uses different dispatching rules according to the state of a production system. Rather than developing new rules, the DSDD heuristic combines and modifies existing rules. This heuristic first classifies workstations into dynamic bottlenecks and non-dynamic bottlenecks. Dynamic bottleneck workstations apply a revised two-boundary dispatching rule when their queue length exceeds the average obtained from simulation using constant lot-release policy and first-in, first-out dispatching rule. Otherwise, the shortest expected processing time until next visit dispatching rule is used. A revised FGCA (FGCA+) dispatching rule is used for all non-dynamic bottlenecks workstations. Simulation results demonstrate that the DSDD heuristic obtains the best performance among the compared six dispatching rules in terms of average and standard deviation of cycle time and work-in-process.     

New approximation algorithms for flow shop total completion time problem

This article addresses the flow shop scheduling problem to minimize the sum of the completion times. On the basis of the properties in job sequencing, the triangular shortest processing time (TSPT) first and dynamic triangular shortest processing time first heuristics are designed to solve the static and dynamic versions of this problem, respectively. Moreover, an improvement scheme is provided for these heuristics to enhance the quality of the original solutions. For further numerical evaluation of the heuristics, two new lower bounds with performance guarantees are presented for the two versions of the problem. At the end of the article, a series of numerical experiments is conducted to demonstrate the effectiveness of the algorithms.     

基于蚁群算法的试验流程优化研究

水中兵器的海上试验涉及许多人员、兵力、被试产品、测量设备等，试验周期长、消耗大，因此如何缩短试验周期是亟待研究解决的问题．文中首先将试验流程优化问题转化为车间调度问题，建立了相应的数学模型，再应用蚁群算法转移规则得到中间结果并进行排队以对各种资源约束进行处理．最后将结果利用局部搜索算法优化后作为蚁群算法信息素更新的基础．实例计算结果表明，该方法优化效果良好．     

基于规则和仿真的多机并行作业车间生产调度研究

资源分派和能力分派是作业车间生产调度中的重要问题,路径选择规则和分派规则是解决上述问题的有效途径。采用基于规则的仿真研究多机并行作业车间资源分派和能力分派问题,分析工件加工时间、到达率以及机器加工速率对调度结果的影响,以平均完工时间、平均延迟交货率以及平均资源利用率为评价指标,通过对4种路径选择规则和6种分派规则的仿真试验,确定不同性能指标下最佳的调度规则。仿真研究表明:调度规则的选用取决于车间资源配置和调度目标,应避免仅凭借经验或偏好选择规则的调度方法。     

改进遗传算法求解多时间约束的柔性作业车间调度问题

将加工时间、调整时间和移动时间分别作为独立时间因素考虑到柔性作业车间调度模型中,建立以最大完工时间最小、总调整时间最小、总移动时间最小为目标的考虑多时间约束的柔性作业车间调度模型,并提出改进的遗传算法求解该模型。通过测试标准数据集,并对比其他文献算法,验证了改进的遗传算法的可行性和有效性。     

基于目标规划的手术排程规则的比较

手术室是医院的重要医疗服务部门,其运营管理对医疗服务质量有重要影响。为减少加班时间、平衡医务人员工作负荷,本文以手术排程规则为研究对象,运用目标规划方法构建手术排程模型,利用天津市某心脑血管病医院导管室手术排程的实际数据和Simio软件进行仿真模拟,对常用的手术排程规则进行分析比较。结果表明,最短队列的排程方法能够更好地均衡各手术室的工作时间、减少加班次数、提高医务人员满意度。     

Permutation flow-shop scheduling problem to optimize a quadratic objective function

A flow-shop scheduling model enables appropriate sequencing for each job and for processing on a set of machines in compliance with identical processing orders. The objective is to achieve a feasible schedule for optimizing a given criterion. Permutation is a special setting of the model in which the processing order of the jobs on the machines is identical for each subsequent step of processing. This article addresses the permutation flow-shop scheduling problem to minimize the criterion of total weighted quadratic completion time. With a probability hypothesis, the asymptotic optimality of the weighted shortest processing time schedule under a consistency condition (WSPT-CC) is proven for sufficiently large-scale problems. However, the worst case performance ratio of the WSPT-CC schedule is the square of the number of machines in certain situations. A discrete differential evolution algorithm, where a new crossover method with multiple-point insertion is used to improve the final outcome, is presented to obtain high-quality solutions for moderate-scale problems. A sequence-independent lower bound is designed for pruning in a branch-and-bound algorithm for small-scale problems. A set of random experiments demonstrates the performance of the lower bound and the effectiveness of the proposed algorithms.     

Asymptotic optimality of shortest processing time-based algorithms for flow shop and open shop problems with nonlinear objective functions

This article investigates the criterion of minimizing total k-power completion time (TKCT) in flow shop and open shop scheduling. For these NP-hard problems, the asymptotic optimality of the shortest processing time-based algorithms is proven for a sufficiently large problem scale. To numerically evaluate the convergence of the algorithms, new lower bounds with performance guarantees are presented for the flow shop TKCT problem. Computational results demonstrate the performance of the proposed algorithms and the effectiveness of the nonlinear objective. In addition, theoretical results on the single-machine TKCT problem are obtained for mathematical deduction.     

Family based dispatching with batch availability

Family based dispatching rules seek to lower set-up frequencies by grouping (batching) similar types of jobs for joint processing. Hence shop flow times may be improved, as less time is spent on set-ups. Motivated by an industrial project we study the control of machines with batch availability, i.e. all the jobs of the same batch become available for processing and leave the machine together. So far the literature seems to have neglected this type of shop by restricting its focus on machines with item availability, i.e. assuming machine operations concern single jobs. We address this gap by proposing extensions to existing family based dispatching rules. Extended rules are tested by an extensive simulation study. Best performance is found for non-exhaustive rules, which allow for alternative choices of batch size. Performance gains are highest for low set-up to run-time ratios and/or high workloads.     

Single machine batch scheduling with sequential job processing

The problem of scheduling n jobs on a single machine in batches to minimize some regular cost functions is studied. Jobs within each batch are processed sequentially so that the processing time of a batch is equal to the sum of the processing times of the jobs contained in it. Jobs in the same batch are completed at the same time when the last job of the batch has finished its processing. A constant set-up time precedes the processing of each batch. The number of jobs in each batch is bounded by some value b. If b < n, then the problem is called bounded. Otherwise, it is unbounded. For both the bounded and unbounded problems, dynamic programming algorithms are presented for minimizing the maximum lateness, the number of late jobs, the total tardiness, the total weighted completion time, and the total weighted tardiness when all due dates are equal, which are polynomial if there is a fixed number of distinct due dates or processing times. More efficient algorithms are derived for some special cases of both the bounded and unbounded problems in which all due dates and/or processing times are equal. Several special cases of the bounded problem are shown to be NP-hard. Thus, a comprehensive classification of the computational complexities of the special cases is provided.     

Request queueing for magnetic bubble memories

The improvements in request throughput that result from the use of the shortest seek time first (SSTF) request, scheduling algorithm for major/minor loop organized magnetic bubble memories are considered. For the satisfaction of read requests the bubble memory can be considered as equivalent to a file drum with fixed block size. Bubble memories are considered with 64 kbits per chip running at a 5.6 μs stepping rate and serving 750 to 830 read requests pet second (as opposed to ≤ 419 requests per second without queueing) with both uniform and Poisson arrival rates. A priority interrupt algorithm is implemented that assures that all requests are served in ≤ 60ms, while average service times are 10 to 20 ms. Results of simulation runs, corresponding to the various cases of interest, are presented. It is concluded that request queueing with the appropriate scheduling algorithm is a practical way of improving bubble memory performance.     

Performance of an ant colony optimisation algorithm in dynamic job shop scheduling problems

The goal of the current study is to identify appropriate application domains of Ant Colony Optimisation (ACO) in the area of dynamic job shop scheduling problem. The algorithm is tested in a shop floor scenario with three levels of machine utilisations, three different processing time distributions, and three different performance measures for intermediate scheduling problems. The steady-state performances of ACO in terms of mean flow time, mean tardiness, total throughput on different experimental environments are compared with those from dispatching rules including first-in-first-out, shortest processing time, and minimum slack time. Two series of experiments are carried out to identify the best ACO strategy and the best performing dispatching rule. Those two approaches are thereafter compared with different variations of processing times. The experimental results show that ACO outperforms other approaches when the machine utilisation or the variation of processing times is not high.     

Integrating optimisation and simulation approaches for daily scheduling of assembly and test operations

The purpose of this paper is to show how the results of an optimisation model that can be integrated with the decisions made within a simulation model to schedule back-end operations in a semiconductor assembly and test facility. The problem is defined by a set of resources that includes machines and tooling, process plans for each product and the following four hierarchical objectives: minimise the weighted sum of key device shortages, maximise weighted throughput, minimise the number of machines used and minimise the makespan for a given set of lots in queue. A mixed integer programming model is purposed and first solved with a greedy randomised adaptive search procedure (GRASP). The results associated with the prescribed facility configuration are then fed to the simulation model written in AutoSched AP. However, due to the inadequacy of the options built into AutoSched, three new rules were created: the first two are designed to capture the machine set-up profiles provided by the GRASP and the third to prioritise the processing of hot lots containing key devices. The computational analysis showed that incorporating the set-up from the GRASP in dynamic operations of the simulation greatly improved its performance with respect to the four objectives.