A fuzzy-based approach to the liquid crystal injection scheduling problem in a TFT-LCD fab

In a thin film transistor-liquid crystal display (TFT-LCD) fab, the liquid crystal injection (LCI) process is to inject liquid crystal into the cell gaps on panels. Since its processing time is enormous (typically 12?h) compared to other processes, the LCI process is a bottleneck in the entire cell process. This study focuses on the LCI scheduling problem, which is divided into two sub-problems: automated guided vehicle (AGV) dispatching and LCI machine scheduling. A self-adjusted fuzzy (SAF) method is developed to solve the AGV dispatching problem. The SAF method is fuzzy based, and it is capable of adjusting the inference rules according to the status of the system to determine which cassette is to be transported first. A modified least slack time (MLST) method is proposed for the LCI machine scheduling problem. The MLST method assigns available LCI machines to first work on processing batches which will be finished beyond their due dates. If there are no such batches, the system releases a new batch, which is waiting in the input buffer with the least slack time, to the available LCI machine. Results indicate that the proposed SAF and MLST methods are able to finish a certain number of batches in a shorter time and reduce the tardiness of cassettes.     

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 hybrid computer simulation-artificial neural network algorithm for optimisation of dispatching rule selection in stochastic job shop scheduling problems

Industrial systems are constantly subject to random events with inevitable uncertainties in production factors, especially in processing times. Due to this stochastic nature, selecting appropriate dispatching rules has become a major issue in practical problems. However, previous research implies that using one dispatching rule does not necessarily yield an optimal schedule. Therefore, a new algorithm is proposed based on computer simulation and artificial neural networks (ANNs) to select the optimal dispatching rule for each machine from a set of rules in order to minimise the makespan in stochastic job shop scheduling problems (SJSSPs). The algorithm contributes to the previous work on job shop scheduling in three significant ways: (1) to the best of our knowledge it is the first time that an approach based on computer simulation and ANNs is proposed to select dispatching rules; (2) non-identical dispatching rules are considered for machines under stochastic environment; and (3) the algorithm is capable of finding the optimal solution of SJSSPs since it evaluates all possible solutions. The performance of the proposed algorithm is compared with computer simulation methods by replicating comprehensive simulation experiments. Extensive computational results for job shops with five and six machines indicate the superiority of the new algorithm compared to previous studies in the literature.     

A filtered-beam-search-based heuristic algorithm for flexible job-shop scheduling problem

Scheduling for the flexible job-shop is a very important issue in both fields of combinatorial optimization and production operations. However, due to combination of the routing and sequencing problems, flexible job-shop scheduling problem (FJSP) presents additional difficulty than the classical job-shop scheduling problem and requires more effective algorithms. This paper developed a filtered-beam-search-based heuristic algorithm (named as HFBS) to find sub-optimal schedules within a reasonable computational time for the FJSP with multiple objectives of minimising makespan, the total workload of machines and the workload of the most loaded machine. The proposed algorithm incorporates dispatching rules based heuristics and explores intelligently the search space to avoid useless paths, which makes it possible to improve the search speed. Through computational experiments, the performance of the presented algorithm is evaluated and compared with those of existing literature and those of commonly used dispatching rules, and the results demonstrate that the proposed algorithm is an effective and practical approach for the FJSP.     

Linguistic-based meta-heuristic optimization model for flexible job shop scheduling

In this paper, a linguistic based meta-heuristic modelling and solution approach for solving the Flexible Job Shop Scheduling Problem (FJSSP) is presented. FJSSP is an extension of the classical job-shop scheduling problem. The present problem definition is to assign each operation to a machine out of a set of capable machines ( the routing problem ) and to order the operations on the machines ( the sequencing problem ), such that a predefined performance measure is optimized. The scope of the problem is widened by taking into account the alternative process plans for each part ( process plan selection problem ) in the present study. Moreover, instead of using operations to represent product processing requirements and machine processing capabilities, machine independent capability units, which are known as Resource Elements (RE), are used. Representation of unique and shared capability boundaries of machine tools and part processing requirements is possible via RE. Using REs in scheduling can also reduce the problem size. The FJSSP is presented as a grammar and the productions in the grammar are defined as controls. Using these controls and the Giffler and Thompson (1960) priority rule-based heuristic, a simulated annealing algorithm is developed to solve FJSSP. This novel approach simplifies the modelling process of the FJSSP and enables usage of existing job shop scheduling algorithms for its solution. The results obtained from the computational study have shown that the proposed algorithm can solve this complex problem effectively within reasonable time. The results have also given some insights on the effect of the selection of dispatching rules and the flexibility level on the job shop performance. It is observed that the effect of dispatching rule selection on the job shop performance diminishes by increasing the job shop flexibility.     

Scheduling of Automated Guided Vehicles in a Decision Making Hierarchy

Scheduling efforts made without considering the special limitations of the material handling system might lead to infeasible results. An analytical model is proposed, first, to incorporate the automated guided vehicle (AGV) system into the overall decision making hierarchy. A mathematical formulation is developed to include interaction between the AGV module and other modules in the system by considering the restrictions of the material handling system. A micro-opportunistic approach is then proposed to solve the AGV scheduling problem. Finally, the proposed method is compared with a number of dispatching rules.     

A priority scheduling approach for flexible job shops with multiple process plans

This paper considers the job shop scheduling problem with alternative operations and machines, called the flexible job shop scheduling problem. As an extension of previous studies, operation and routing flexibilities are considered at the same time in the form of multiple process plans, i.e. each job can be processed through alternative operations, each of which can be processed on alternative machines. The main decisions are: (a) selecting operation/machine pair; and (b) sequencing the jobs assigned to each machine. Since the problem is highly complicated, we suggest a practical priority scheduling approach in which the two decisions are done at the same time using a combination of operation/machine selection and job sequencing rules. The performance measures used are minimising makespan, total flow time, mean tardiness, the number of tardy jobs, and the maximum tardiness. To compare the performances of various rule combinations, simulation experiments were done on the data for hybrid systems with an advanced reconfigurable manufacturing system and a conventional legacy system, and the results are reported.     

A rework-based dispatching algorithm for module process in TFT-LCD manufacture

This paper presents development of a scheduling methodology for module processing in thin film transistor liquid crystal display (TFT-LCD) manufacturing. The problem is a parallel machine scheduling problem with rework probabilities, sequence-dependent setup times and due dates. It is assumed that rework probability for each job on a machine can be given through historical data acquisition. The dispatching algorithm named GRPD (greedy rework probability with due-dates) is proposed in this paper focusing on the rework processes. The performance of GRPD is measured by the six diagnostic indicators. A large number of test problems are randomly generated to evaluate the performance of the proposed algorithm. Computational results show that the proposed algorithm is significantly superior to existing dispatching algorithms for the test problems.     

Effects of flexibility and scheduling decisions on the performance of an FMS: simulation modelling and analysis

This paper focuses on a simulation-based experimental study of the effects of routing flexibility, sequencing flexibility, and part sequencing rules on the performance of a typical FMS. Three routing flexibility levels, five sequencing flexibility levels, and four scheduling rules for part sequencing decision are considered for detailed investigation. The system work load characterised by the mean interarrival time of parts has been set at different levels. The performance of the FMS is evaluated using various measures related to flow time and tardiness of parts. The simulation results are subjected to statistical analysis. Multiple regression-based metamodels have been developed using the simulation results. The analyses of results reveal that deterioration in system performance can be minimised substantially by incorporating either routing flexibility or sequencing flexibility or both. However, the benefits of either of these flexibilities diminish at higher flexibility levels. When flexibility exists, part sequencing rules such as the earliest due date and earliest operation due date provide a better performance for all the measures.     

Co-evolutionary genetic algorithm for multi-machine scheduling: Coping with high performance variability

Optimizing dispatching policy in a networked, multi-machine system is a formidable task for both field experts and operations researchers due to the problem's stochastic and combinatorial nature. This paper proposes an innovative variation of co-evolutionary genetic algorithm (CGA) for acquiring the adaptive scheduling strategies in a complex multi-machine system. The task is to assign each machine an appropriate dispatching rule that is harmonious with the rules used in neighbouring machines. An ordinary co-evolutionary algorithm would not be successful due to the high variability (i.e. noisy causality) of system performance and the ripple effects among neighbouring populations. The computing time for large enough populations to avoid premature convergence would be prohibitive. We introduced the notion of derivative contribution feedback (DCF), in which an individual rule for a machine takes responsibility for the first-order change of the overall system performance according to its participation in decisions. The DCFCGA effectively suppressed premature convergence and produced dispatching rules for spatial adaptation that outperformed other heuristics. The required time for knowledge acquisition was also favourably compared with an efficient statistical method. The DCF-CGA method can be utilized in a wide variety of genetic algorithm application problems that have similar characteristics and difficulties.     

The study of real time scheduling by an intelligent multi-controller approach

Earlier studies indicated that using multiple dispatching rules (MDRs) for the various zones in the system can enhance the production performance to a greater extent than using a single dispatching rule (SDR) over a given scheduling interval for all the machines in the system, since MDRs employ the multi-pass simulation approach for real-time scheduling (RTS). However, if a classical machine learning approach is used, an RTS knowledge base (KB) can be developed by using the appropriate MDRs strategy (this method is called an intelligent multi-controller in this paper) as obtained from training examples. The main disadvantage of using MDRs is that the classes (scheduling decision variables) to which training examples are assigned must be provided. Hence, developing an RTS KB using the intelligent multi-controller approach becomes an intolerably time-consuming task because MDRs for the next scheduling period must be determined. To address this issue, we proposed an intelligent multi-controller incorporating three main mechanisms: (1) simulation-based training example generation mechanism, (2) data pre-processing mechanism and (3) SOM-based real time MDRs selection mechanism. Under various performance criteria over a long period, the proposed approach yields better system performance than the machine learning-based RTS using the SDR approach and heuristic individual dispatching rules.     

A constraint-based perspective in resource constrained project scheduling

In this study, a new heuristic approach to the resource constrained project scheduling problem is introduced. This approach, which is called local constraint based analysis (LCBA), is more robust than the dispatching rules found in the literature, since it does not depend on an a priori insight as do the dispatching rules. LCBA consists of the application of local essential conditions which respect the current temporal and resource constraints to generate a necessary sequence of activities at a scheduling decision time point in a single-pass parallel scheduling algorithm. LCBA is a time efficient procedure due to the localized aspect with which the activities are handled. Only the activities which are schedulable at the current scheduling time are considered for the application of the essential conditions. LCBA is tested against well-known rules from the literature and some recently developed rules. This testing is done using a set of problems of a special design and also a set of optimally solved problems from a recent benchmark in the literature. It is observed that near optimal time efficient solutions are obtained by LCBA and the procedure's performance is considerably better than that of the dispatching rules.     

Experimental investigation of FMS machine and AGV scheduling rules against the mean flow-time criterion

Although a significant amount of research has been carried out in the scheduling of flexible manufacturing systems (FMSs), it has generally been focused on developing intelligent scheduling systems. Most of these systems use simple scheduling rules as a part of their decision process. While these scheduling rules have been investigated extensively for a job shop environment, there is little guidance in the literature as to their performance in an FMS environment. This paper attempts to investigate the performances of machine and AGV scheduling rules against the mean flow-time criterion. The scheduling rules are tested under a variety of experimental conditions by using an FMS simulation model.     

An ant colony optimisation algorithm for scheduling in agile manufacturing

Producing customised products in a short time at low cost is one of the goals of agile manufacturing. To achieve this goal an assembly-driven differentiation strategy has been proposed in the agile manufacturing literature. In this paper, we address a manufacturing system that applies the assembly-driven differentiation strategy. The system consists of machining and assembly stages, where there is a single machine at the machining stage and multiple identical assembly stations at the assembly stage. An ant colony optimisation (ACO) algorithm is developed for solving the scheduling problem of determining the sequence of parts to be produced in the system so as to minimise the maximum completion time (or makespan). The ACO algorithm uses a new dispatching rule as the heuristic desirability and variable neighbourhood search as the local search to make it more efficient and effective. To evaluate the performance of heuristic algorithms, a branch-and-bound procedure is proposed for deriving the optimal solution to the problem. Computational results show that the proposed ACO algorithm is superior to the existing algorithm, not only improving the performance but also decreasing the computation time.     

蚁群系统结合指派规则求解HFS调度问题

以NP-难的最小化时间表长为目标的混合流水车间调度问题为研究对象。把工件在第1阶段开始加工的排序问题转化为旅行商问题,采用蚁群系统求得初始排序;在第1阶段后各阶段采用工件先到先服务规则选择工件、最先空闲机器优先规则选择机器以构建初始工件的机器指派与排序;充分利用已知的机器布局和工件加工时间特点,确定工件加工瓶颈阶段,并以此为基础对工件的机器指派与排序进行改进。用Carlier和Neron设计的Benchmark算例仿真后与著名的NEH算法比较,表明这种算法是有效的。     

Dynamic job shop scheduling for missed due date performance

In this research, missed due date in terms of mean absolute lateness (MAL) and mean square lateness (MSL) has been considered as a performance criterion and a scheduling study has been performed to improve the missed due date performance in dynamic, stochastic, multi machine job shop environments. In the study, a new due date assignment model was proposed and a new dynamic dispatching rule was developed. The results indicate that the proposed due date assignment model is very successful for improving the missed due date performance and the developed dispatching rule is also very successful for meeting the assigned due dates.     

Learning effective dispatching rules for batch processor scheduling

Batch processor scheduling, where machines can process multiple jobs simultaneously, is frequently harder than its unit-capacity counterpart because an effective scheduling procedure must not only decide how to group the individual jobs into batches, but also determine the sequence in which the batches are to be processed. We extend a previously developed genetic learning approach to automatically discover effective dispatching policies for several batch scheduling environments, and show that these rules yield good system performance. Computational results show the competitiveness of the learned rules with existing rules for different performance measures. The autonomous learning approach addresses a growing practical need for rapidly developing effective dispatching rules for these environments by automating the discovery of effective job dispatching procedures.     

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.     

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.     

A new paradigm for rule-based scheduling in the wafer probe centre

This paper addresses the scheduling problem in the wafer probe centre. The proposed approach is based on the dispatching rule, which is popularly used in the semiconductor manufacturing industry. Instead of designing new rules, this paper proposes a new paradigm to utilize these rules. The proposed paradigm formulates the dispatching process as a 2-D assignment problem with the consideration of information from multiple lots and multiple pieces of equipment in an integrated manner. Then, the dispatching decisions are made by maximizing the gains of multiple possible decisions simultaneously. Besides, we develop a genetic algorithm (GA) for generating good dispatching rules through combining multiple rules with linear weighted summation. The benefits of the proposed paradigm and GA are verified with a comprehensive simulation study on three due-date-based performance measures. The experimental results show that under the proposed paradigm, the dispatching rules and GA can perform much better than under the traditional paradigm.