A multi-criteria approach for scheduling semiconductor wafer fabrication facilities

In this research, we model a semiconductor wafer fabrication process as a complex job shop, and adapt a Modified Shifting Bottleneck Heuristic (MSBH) to facilitate the multi-criteria optimization of makespan, cycle time, and total weighted tardiness using a desirability function. The desirability function is implemented at two different levels of the MSBH: the subproblem solution procedure level (SSP level) and the machine criticality measure level (MCM level). In addition, we suggest two different methods of choosing the critical toolgroup at the MCM level: (1) the Local MCM approach, which chooses the critical toolgroup based on local desirability values from the SSP level and (2) the Global MCM approach, which chooses the critical toolgroup based on its impact on the desirability of the entire disjunctive graph. Results demonstrate the desirability-based approaches’ ability to simultaneously minimize all three objectives.     

Mathematical models for preemptive shop scheduling problems

More than half a century has passed since Bowman and Dantzig (1959) [13] and [14] introduced their models for preemptive shop scheduling problems. A more efficient model seems to be needed to address all the aspects involved in the problem. We introduce a new Integer Linear Programming (ILP) formulation as a new method for solving the preemptive Job Shop Scheduling Problem (pJSSP). The dimension of the new model, unlike those of the existing ones, depends solely on the number of jobs and machines irrespective of processing times. The proposed model is used as an optimal, two-phase approach. In phase one, the model is solved to obtain the start and completion times of each operation on each machine. In phase two, a simple algorithm in O(mn log n) steps is used to turn these times into a complete and optimal schedule. Different preemptive flow shop problems are studied as special cases of the pJSSP while some related properties are also discussed. Finally, the higher efficiency of the proposed model is verified both theoretically and computationally through its comparison with conventional methods commonly in use.     

基于过滤束的转移瓶颈算法在JSSP中的应用

举例证明了传统转移瓶颈算法在求解瓶颈机时并不能得到局部最优解.提出一种新的确定瓶颈机的模型,在综合考虑时间和求解精度的情况下,采用分支定界方法的改进方法--过滤束搜索来求解此模型.在过滤束中引用了不同工件到达时间和处理时间的约束关系来解决成环问题.通过对OR-Library中的33个标准job shop问题的实验结果看,此算法得到了比较满意的效果.     

An effective asexual genetic algorithm for solving the job shop scheduling problem

By using the notion of elite pool, this paper presents an effective asexual genetic algorithm for solving the job shop scheduling problem. Based on mutation operations, the algorithm selectively picks the solution with the highest quality from the pool and after its modification, it can replace the solution with the lowest quality with such a modified solution. The elite pool is initially filled with a number of non-delay schedules, and then, in each iteration, the best solution of the elite pool is removed and mutated in a biased fashion through running a limited tabu search procedure. A decision strategy which balances exploitation versus exploration determines (i) whether any intermediate solution along the run of tabu search should join the elite pool, and (ii) whether upon joining a new solution to the pool, the worst solution should leave the pool. The genetic algorithm procedure is repeated until either a time limit is reached or the elite pool becomes empty. The results of extensive computational experiments on the benchmark instances indicate that the success of the procedure significantly depends on the employed mechanism of updating the elite pool. In these experiments, the optimal value of the well-known 10 × 10 instance, ft10, is obtained in 0.06 s. Moreover, for larger problems, solutions with the precision of less than one percent from the best known solutions are achieved within several seconds.     

A hybrid genetic algorithm for the job shop scheduling problems

The Job Shop Scheduling Problem (JSSP) is one of the most general and difficult of all traditional scheduling problems. The goal of this research is to develop an efficient scheduling method based on genetic algorithm to address JSSP. We design a scheduling method based on Single Genetic Algorithm (SGA) and Parallel Genetic Algorithm (PGA). In the scheduling method, the representation, which encodes the job number, is made to be always feasible, the initial population is generated through integrating representation and G&T algorithm, the new genetic operators and selection method are designed to better transmit the temporal relationships in the chromosome, and island model PGA are proposed. The scheduling methods based on genetic algorithm are tested on five standard benchmark JSSP. The results are compared with other proposed approaches. Compared to traditional genetic algorithm, the proposed approach yields significant improvement in solution quality. The superior results indicate the successful incorporation of a method to generate initial population into the genetic operators.     

An efficient memetic algorithm for solving the job shop scheduling problem

The job shop scheduling problem (JSP) is well known as one of the most complicated combinatorial optimization problems, and it is a NP-hard problem. Memetic algorithm (MA) which combines the global search and local search is a hybrid evolutionary algorithm. In this paper, an efficient MA with a novel local search is proposed to solve the JSP. Within the local search, a systematic change of the neighborhood is carried out to avoid trapping into local optimal. And two neighborhood structures are designed by exchanging and inserting based on the critical path. The objective of minimizing makespan is considered while satisfying a number of hard constraints. The computational results obtained in experiments demonstrate that the efficiency of the proposed MA is significantly superior to the other reported approaches in the literature.     

An integrated security-aware job scheduling strategy for large-scale computational grids

All existing fault-tolerance job scheduling algorithms for computational grids were proposed under the assumption that all sites apply the same fault-tolerance strategy. They all ignored that each grid site may have its own fault-tolerance strategy because each site is itself an autonomous domain. In fact, it is very common that there are multiple fault-tolerance strategies adopted at the same time in a large-scale computational grid. Various fault-tolerance strategies may have different hardware and software requirements. For instance, if a grid site employs the job checkpointing mechanism, each computation node must have the following ability. Periodically, the computational node transmits the transient state of the job execution to the server. If a job fails, it will migrate to another computational node and resume from the last stored checkpoint. Therefore, in this paper we propose a genetic algorithm for job scheduling to address the heterogeneity of fault-tolerance mechanisms problem in a computational grid. We assume that the system supports four kinds fault-tolerance mechanisms, including the job retry, the job migration without checkpointing, the job migration with checkpointing, and the job replication mechanisms. Because each fault-tolerance mechanism has different requirements for gene encoding, we also propose a new chromosome encoding approach to integrate the four kinds of mechanisms in a chromosome. The risk nature of the grid environment is also taken into account in the algorithm. The risk relationship between jobs and nodes are defined by the security demand and the trust level. Simulation results show that our algorithm has shorter makespan and more excellent efficiencies on improving the job failure rate than the Min–Min and sufferage algorithms.     

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

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

Modeling and heuristics for scheduling of distributed job shops

This paper deals with the problem of distributed job shop scheduling in which the classical single-facility job shop is extended to the multi-facility one. The mathematical formulation of the problem is comprehensively discussed. Two different mixed integer linear programming models in form of sequence and position based variables are proposed. Using commercial software of CPLEX, the small sized problems are optimally solved. To solve large sized problems, besides adapting three well-known heuristics, three greedy heuristics are developed. The basic idea behind the developed heuristics is to iteratively insert operations (one at each iteration) into a sequence to build up a complete permutation of operations. The permutation scheme, although having several advantages, suffers from redundancy which is having many different permutations representing the same schedule. The issue is analyzed to recognize the redundant permutation. That improves efficiency of heuristics. Comprehensive experiments are conducted to evaluate the performance of the two models and the six heuristics. The results show sequence based model and greedy heuristics equipped with redundancy exclusion are effective for the problem.     

A computer simulation model for job shop scheduling problems minimizing makespan

One of the basic and significant problems, that a shop or a factory manager is encountered, is a suitable scheduling and sequencing of jobs on machines. One type of scheduling problem is job shop scheduling. There are different machines in a shop of which a job may require some or all these machines in some specific sequence. For solving this problem, the objective may be to minimize the makespan. After optimizing the makespan, the jobs sequencing must be carried out for each machine. The above problem can be solved by a number of different methods such as branch and bound, cutting plane, heuristic methods, etc. In recent years, researches have used genetic algorithms, simulated annealing, and machine learning methods for solving such problems. In this paper, a simulation model is presented to work out job shop scheduling problems with the objective of minimizing makespan. The model has been coded by Visual SLAM which is a special simulation language. The structure of this language is based on the network modeling. After modeling the scheduling problem, the model is verified and validated. Then the computational results are presented and compared with other results reported in the literature. Finally, the model output is analyzed.     

混合交叉熵算法求解复杂零等待流水线调度问题

针对制造行业中广泛存在的一类复杂零等待流水线调度问题,即带序相关设置时间和释放时间的零等待流水线调度问题(NFSSP SDSTs RTs),建立问题的排序模型并提出一种混合交叉熵算法(HCEA)进行求解,优化目标为最小化总提前和延迟时间.首先,设计了一种基于问题性质的快速评价方法,有效降低评价解的计算复杂度.其次,采用...     

作业车间调度转换瓶颈算法可行性研究

讨论了转换瓶颈( SB) 算法在解作业车间调度问题时需要解决的子问题。转换瓶颈算法是解决作业车间调度最小makespan( 完工时间) 问题的有效启发式算法。它是基于反复地解决某些单机调度问题这样的子问题。然而所解决的单机调度问题的解可能会导致算法最终得不到可行解, 即使是单机调度最优解也可能得到不可行解。为此, 给出了一个简单的反例证明了产生不可行解的情况, 并对产生不可行解的原因作了详细分析。该研究有利于对转换瓶颈技术进行更好的理解和应用。     

A hybrid Electromagnetism-like Mechanism/tabu search procedure for the single machine scheduling problem with a maximum lateness objective

This paper presents a hybrid meta-heuristic search procedure to solve the well-known single machine scheduling problem to minimize the maximum lateness over all jobs, where precedence relations may exist between some of the jobs. The hybridization consists of a well-designed balance between the principles borrowed from an Electromagnetism-like Mechanism algorithm and the characteristics used in a tabu search procedure. The Electromagnetism-like Mechanism (EM) algorithm follows a search pattern based on the theory of physics to simulate attraction and repulsion of solutions in order to move towards more promising solutions. The well-known tabu search enhances the performance of a local search method by using memory structures by prohibiting visited solutions during a certain time of the search process. The hybridization of both algorithms results in an important trade-off between intensification and diversification strategies. These strategies will be discussed in detail. To that purpose, a new set of data instances is used to compare different elements of the hybrid search procedure and to validate the performance of the algorithm.     

Simple heuristics for scheduling with limited intermediate storage

Limited storage capacities impose important restrictions in production planning and scheduling that can be used to control the work-in-process and must be taken into account when feasible schedules are to be generated. In this paper we consider a deterministic scheduling problem with limited intermediate storage. Contrary to other approaches known from the scheduling literature the intermediate storage is measured in material quantities that are associated with the jobs. Thus, a different consumption of space by the jobs inside the storage can be considered. Three heuristics are presented that are capable of taking into account limited intermediate storage. The procedures offer the opportunity to control the work-in-process formed by the jobs that wait for processing or are being processed in the production system.     

Decision support tool for multi-objective job shop scheduling problems with linguistically quantified decision functions

This paper presents a new tool for multi-objective job shop scheduling problems. The tool encompasses an interactive fuzzy multi-objective genetic algorithm (GA) which considers aspiration levels set by the decision maker (DM) for all the objectives. The GA's decision (fitness) function is defined as a measure of truth of a linguistically quantified statement, imprecisely specified by the DM using linguistic quantifiers such as most, few, etc., that refer to acceptable distances between the achieved objective values and the aspiration levels. The linguistic quantifiers are modelled using fuzzy sets. The developed tool is used to analyse and solve a real-world problem defined in collaboration with a pottery company. The tool provides a valuable support in performing various what-if analyses, for example, how changes of batch sizes, aspiration levels, linguistic quantifiers and the measure of acceptable distances affect the final schedule.     

带负载均衡的混合算法求解分布式异构作业车间调度问题

针对以最小化最大完工时间为目标的分布式异构作业车间调度问题(DHJSP), 本文提出了一种新的混合遗传禁忌搜索算法. 首先, 综合考虑工厂的工件总负载与最大机器负载, 提出了一种新的工厂负载表达方式. 其次, 针对DHJSP总工序数不定的特性, 提出以最小化最大工厂负载为目标快速确定初始工件分配方案, 并验证了方法的高效性. 然后, 新设计了两种考虑负载均衡的单工件转移邻域结构, 根据工序调度的结果对工件分配方案进行局部搜索. 最后, 因DHJSP缺少标准算例和相关算法, 在分布式同构作业车间调度问题(DJSP)上与现有算法进行对比, 所提算法在TA算例的480个问题上更新了420个问题的最优解, 其余60个问题取得了同等最优解. 在随机生成的3个不同规模的异构算例中, 所提算法也均取得了较好解, 验证了所提方法的优越性.     

Scheduling of multiple in-line steppers for semiconductor wafer fabs

A few prior studies noticed that an in-line stepper (a bottleneck machine in a semiconductor fab) may have a capacity loss while operated in a low-yield scenario. To alleviate such a capacity loss, some meta-heuristic algorithms for scheduling a single in-line stepper were proposed. Yet, in practice, there are multiple in-line steppers to be scheduled in a fab. This article aims to enhance prior algorithms so as to deal with the scheduling for multiple in-line steppers. Compared to prior studies, this research has to additionally consider how to appropriately allocate jobs to various machines. We enhance prior algorithms by developing a chromosome-decoding scheme which can yield a job-allocation decision for any given chromosome (or job sequence). Seven enhanced versions of meta-heuristic algorithms (genetic algorithm, Tabu, GA–Tabu, simulated annealing, M-MMAX, PACO and particle swarm optimisation) were then proposed and tested. Numerical experiments indicate that the GA–Tabu method outperforms the others. In addition, the lower the process yield, the better is the performance of the GA–Tabu algorithm.     

改进果蝇算法求解混合流水车间调度问题

针对混合流水车间调度问题(HFSP),本文提出了一种新的基于果蝇算法和变邻域搜索的混合优化方法.首先,将关键块内的工序与同阶段其他机器上的工序进行交换,提出了一种基于关键路径的HFSP新邻域结构.其次,针对HFSP的阶段式解码特性,提出了一种邻域解的快速评估方法,并验证了快速评估方法的高效性.然后,基于提出的新邻域结构,并将N7和K-insertion邻域结构引入HFSP,设计了基于上述3种邻域结构的变邻域搜索方法,以此为基础提出了一种针对HFSP的混合优化方法.最后,通过对Carlier和Liao等经典测试集进行测试,验证了所提新邻域结构的可行性和有效性,并将该方法与其他文献的方法进行了对比,验证了所提方法的优越性.     

A heuristic for job shop scheduling to minimize total weighted tardiness

This paper considers the job shop scheduling problem to minimize the total weighted tardiness with job-specific due dates and delay penalties, and a heuristic algorithm based on the tree search procedure is developed for solving the problem. A certain job shop scheduling to minimize the maximum tardiness subject to fixed sub-schedules is solved at each node of the search tree, and the successor nodes are generated, where the sub-schedules of the operations are fixed. Thus, a schedule is obtained at each node, and the sub-optimum solution is determined among the obtained schedules. Computational results on some 10 jobs and 10 machines problems and 15 jobs and 15 machines problems show that the proposed algorithm can find the sub-optimum solutions with a little computation time.     

A hybrid algorithm based on a new neighborhood structure evaluation method for job shop scheduling problem

Job shop scheduling problem (JSP) which is widespread in the real-world production system is one of the most general and important problems in various scheduling problems. Nowadays, the effective method for JSP is a hot topic in research area of manufacturing system. JSP is a typical NP-hard combinatorial optimization problem and has a broad engineering application background. Due to the large and complicated solution space and process constraints, JSP is very difficult to find an optimal solution within a reasonable time even for small instances. In this paper, a hybrid particle swarm optimization algorithm (PSO) based on variable neighborhood search (VNS) has been proposed to solve this problem. In order to overcome the blind selection of neighborhood structures during the hybrid algorithm design, a new neighborhood structure evaluation method based on logistic model has been developed to guide the neighborhood structures selection. This method is utilized to evaluate the performance of different neighborhood structures. Then the neighborhood structures which have good performance are selected as the main neighborhood structures in VNS. Finally, a set of benchmark instances have been conducted to evaluate the performance of proposed hybrid algorithm and the comparisons among some other state-of-art reported algorithms are also presented. The experimental results show that the proposed hybrid algorithm has achieved good improvement on the optimization of JSP, which also verifies the effectiveness and efficiency of the proposed neighborhood structure evaluation method.