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.     

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.     

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

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

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.     

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.     

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.     

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.     

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.     

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.     

Modified genetic algorithms for solving fuzzy flow shop scheduling problems and their implementation with CUDA

In this paper we propose an improved algorithm to search optimal solutions to the flow shop scheduling problems with fuzzy processing times and fuzzy due dates. A longest common substring method is proposed to combine with the random key method. Numerical simulation shows that longest common substring method combined with rearranging mating method improves the search efficiency of genetic algorithm in this problem. For application in large-sized problems, we also enhance this modified algorithm by CUDA based parallel computation. Numerical experiments show that the performances of the CUDA program on GPU compare favorably to the traditional programs on CPU. Based on the modified algorithm invoking with CUDA scheme, we can search satisfied solutions to the fuzzy flow shop scheduling problems with high performance.     

A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem

In this paper, we study the job shop scheduling problem with the objective of minimizing the total weighted tardiness. We propose a hybrid shifting bottleneck-tabu search (SB-TS) algorithm by replacing the re-optimization step in the shifting bottleneck (SB) algorithm by a tabu search (TS). In terms of the shifting bottleneck heuristic, the proposed tabu search optimizes the total weighted tardiness for partial schedules in which some machines are currently assumed to have infinite capacity. In the context of tabu search, the shifting bottleneck heuristic features a long-term memory which helps to diversify the local search. We exploit this synergy to develop a state-of-the-art algorithm for the job shop total weighted tardiness problem (JS-TWT). The computational effectiveness of the algorithm is demonstrated on standard benchmark instances from the literature.     

作业车间调度问题的一种混合式算法

描述了一种解决作业车间调度最短完工时间问题的混合式算法．该算法基于禁忌搜索和转换瓶颈技术．算法中利用了多种禁忌搜索方法．为了得到更好的结果，算法中还引入了倒转技术．从对一组问题基准实例的实验计算结果看，该算法在合理的计算时间内，对多个实例得到比当前解决该问题的最高效的启发式算法之一的TSSB算法更好的结果．     

瓶颈指向的启发式算法求解混合流水车间调度问题

针对以最小化时间表长为目标的复杂混合流水车间调度问题,提出了一种将机器布局和工件加工时间特征紧密结合的启发式算法.首先,充分利用各阶段平均机器负荷一般不相等的特点确定瓶颈阶段,构建初始工件排序.其次,针对在瓶颈阶段前加工时间较短而瓶颈阶段后加工时间相对较长的工件,在第1阶段优先开始加工.同时,在瓶颈阶段前的每一个阶段,每当有工件等待加工或同时完工时,优先选择瓶颈阶段前剩余加工时间最短的工件加工;在瓶颈阶段以及瓶颈阶段之后,则优先选择这台机器后剩余加工时间最长的工件加工.最后,采用工件交换和插入操作改进初始调度.用Carlier和Neron的Benchmark算例测试提出的启发式算法.将计算结果与NEH启发式算法进行了比较,平均偏差降低了0.0555%,表明这个启发式算法是有效的.     

A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem

Tabu search (TS) algorithms are among the most effective approaches for solving the job shop scheduling problem (JSP) which is one of the most difficult NP-complete problems. However, neighborhood structures and move evaluation strategies play the central role in the effectiveness and efficiency of the tabu search for the JSP. In this paper, a new enhanced neighborhood structure is proposed and applied to solving the job shop scheduling problem by TS approach. Using this new neighborhood structure combined with the appropriate move evaluation strategy and parameters, we tested the TS approach on a set of standard benchmark instances and found a large number of better upper bounds among the unsolved instances. The computational results show that for the rectangular problem our approach dominates all others in terms of both solution quality and performance.     

Improving the delivery efficiency of the customer order scheduling problem in a job shop

The focus of this paper is customer order scheduling (COS) problem, where each order consists of a set of jobs that must be shipped as one batch at the same time. In COS each job is part of a customer order and the make-up of the jobs in the order are pre-specified. Most of the existing research deals with COS in a single machine or in a parallel machine shop for developing an optimal solution. COS is common in a normal job shop, and the more complex the shop, the more complex the scheduling. Most existing research has focused on trying to reduce the completion time of the batch. That is, the focus is only on the point in time the last job is finished, while ignoring the actual duration of the jobs within the same order. The longer it takes to complete all the jobs within an order the more it increases the stock of finished goods and the more it deteriorates the efficiency of the logistics and the supply chain management.A new dispatching rule, referred to as Minimum Flow Time Variation (MFV), has been proposed for COS in a normal job shop, in order to reduce the total time it takes to complete all jobs within the same order. That is, the individual completion times of all jobs for the same customer order will be controlled in order to improve the shipping performance. In the simulation test and statistical analysis, the level of work in process (WIP) under the MFV rule in the finished goods warehouse is reduced by more than 70% compared to any other method. The MFV method will efficiently reduce the stock level of finished goods, and controls the waiting time required before they can be shipped. Depending on the environmental factors, the performance of our proposed method will become increasingly significant the more complex the system.     

Ant colony optimization combined with taboo search for the job shop scheduling problem

In this paper, we present a hybrid algorithm combining ant colony optimization algorithm with the taboo search algorithm for the classical job shop scheduling problem. Instead of using the conventional construction approach to construct feasible schedules, the proposed ant colony optimization algorithm employs a novel decomposition method inspired by the shifting bottleneck procedure, and a mechanism of occasional reoptimizations of partial schedules. Besides, a taboo search algorithm is embedded to improve the solution quality. We run the proposed algorithm on 101 benchmark instances and obtain competitive results and a new best upper bound for one open benchmark instance is found.     

A very fast TS/SA algorithm for the job shop scheduling problem

The job shop scheduling problem (JSP) is one of the most notoriously intractable NP-complete optimization problems. Over the last 10–15 years, tabu search (TS) has emerged as an effective algorithmic approach for the JSP. However, the quality of solutions found by tabu search approach depends on the initial solution. To overcome this problem and provide a robust and efficient methodology for the JSP, the heuristics search approach combining simulated annealing (SA) and TS strategy is developed. The main principle of this approach is that SA is used to find the elite solutions inside big valley (BV) so that TS can re-intensify search from the promising solutions. This hybrid algorithm is tested on the standard benchmark sets and compared with the other approaches. The computational results show that the proposed algorithm could obtain the high-quality solutions within reasonable computing times. For example, 17 new upper bounds among the unsolved problems are found in a short time.