A beam search-based algorithm and evaluation of scheduling approaches for flexible manufacturing systems

This paper presents a new algorithm for the flexible manufacturing system (FMS) scheduling problem. The proposed algorithm is a heuristic based on filtered beam search. It considers finite buffer capacity, routing and sequence flexibilities and generates machine and automated guided vehicle (AGV) schedules for a given scheduling period. A new deadlock resolution mechanism is also developed as an integral part of the proposed algorithm. The performance of the algorithm is compared with several machine and AGV dispatching rules using mean flow time, mean tardiness and makespan criteria. It is also used to examine the effects of scheduling factors (i.e., machine and AGV load levels, routing and sequence flexibilities, etc.) on the system performance. The results indicate that the proposed scheduling algorithm yields considerable improvements in system performance over dispatching rules under a wide variety of experimental conditions.     

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.     

基于聚类状态隶属度的动态调度Q-学习

提出了一种利用Q-学习解决动态单机调度环境下的自适应调度规则选择的方法.该方法针对动态调度环境中系统状态空间大,Q-学习不易收敛的特点,首先提取系统状态特征,对系统状态进行合理聚类,有效地降低系统状态空间维数,然后在学习过程中令设备Agent根据瞬时状态向量对各聚类状态的隶属度做出综合判断,选择合适规则,并在每次迭代后根据隶属度将动作奖惩分配给各聚类状态的动作值函数.仿真结果表明,所提Q-学习算法较之传统Q-学习具有更快的收敛速度,提高了设备Agent的动态调度规则选择能力.     

Fuzzy-logic-based network for complex systems risk assessment: Application to ship performance analysis

In this paper, a new interpretation of intuitionistic fuzzy sets in the advanced framework of the Dempster–Shafer theory of evidence is extended to monitor safety-critical systems’ performance. Not only is the proposed approach more effective, but it also takes into account the fuzzy rules that deal with imperfect knowledge/information and, therefore, is different from the classical Takagi–Sugeno fuzzy system, which assumes that the rule (the knowledge) is perfect. We provide an analytical solution to the practical and important problem of the conceptual probabilistic approach for formal ship safety assessment using the fuzzy set theory that involves uncertainties associated with the reliability input data. Thus, the overall safety of the ship engine is investigated as an object of risk analysis using the fuzzy mapping structure, which considers uncertainty and partial truth in the input–output mapping. The proposed method integrates direct evidence of the frame of discernment and is demonstrated through references to examples where fuzzy set models are informative. These simple applications illustrate how to assess the conflict of sensor information fusion for a sufficient cooling power system of vessels under extreme operation conditions. It was found that propulsion engine safety systems are not only a function of many environmental and operation profiles but are also dynamic and complex.     

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.     

Dispatching rules in scheduling Dispatching rules in scheduling: a fuzzy approach

Job-shop scheduling through simulation uses various kinds of dispatching rules such as SPT or the slack time rule. Each of these rules aims at satisfying a single criterion although workshop management is a multi-criteria problem. This paper proposes a way to use fuzzy logic in order to build aggregated rules allowing to obtain a compromise between the satisfaction of several criteria. When the criteria of performance change with the evolution of the production environment, these aggregated rules can be parametrized in order to modify the respective influence of the elementary rules they are composed of.     

An interactive scheduler for a wafer probe centre in semiconductor manufacturing

This paper analyses production operations and scheduling constraints on a wafer probe centre in semiconductor manufacturing. Such actions as lot split and hot lot preemption are discussed. Due to the combinatorial difficulties of scheduling problems with sequence-dependent setup costs and multiple criteria, a humancomputer interactive scheduler named the 'interactive computer aided scheduling system' (ICASS) is proposed. This ICASS can search for schedules to achieve a specific performance level set by a human. An experiment was conducted on a wafer probe centre to compare the performance of ICASS with that of a manual approach and six priority rules. The results indicate that ICASS spent less scheduling time and provided better schedules than the manual approach. All the six priority rules yielded only poor schedules with unbalanced performance in three kinds of criteria, although they were beneficial in computation time.     

Modelling and simulation of automated manufacturing systems for evaluation of complex schedules

Automated manufacturing systems have been studied widely in terms of scheduling. As technology evolves, the behaviour of tools in automated manufacturing systems has become complicated. Therefore, mathematical approaches to the analysis of complex schedules no longer reflect reality. In this paper, we propose a systematic way of conducting simulation experiments to evaluate the complex operating schedules of automated manufacturing systems. A simulation model is based on a timed Petri net to take advantage of its mathematical strength. Since a Petri net cannot itself have token firing rules, we introduce additional states called operational states. Operational states are not directly related to a Petri net, and are only used for decision making. In addition, a decision function that is responsible for the conflict resolution of a Petri net model and an operational state transition function are introduced. The parallel simulation concept is also suggested by dividing a Petri net into several independent decision sub-nets. A multi-cluster tool system for semiconductor manufacturing is analysed as an application.     

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 comparison of tool management strategies and part selection rules for a flexible manufacturing system

An important element in the successful operation of flexible manufacturing systems (FMS) is the management of the tooling component. This paper reports on one aspect of tool management for FMS operations. Four tool allocation and scheduling strategies are compared in the presence of three part selection rules through a simulation study of a five-machine FMS with an automated tool handling system. The tool allocation strategies are similar to those used in industry while the part selection rules are synthesized from the literature on FMS scheduling under tooling constraints. The use of different tooling strategies produces significantly different outcomes in FMS performance.     

An effective heuristic for adaptive control of job sequences subject to variation in processing times

Variation in sequential task processing times is common in manufacturing systems. This type of disturbance challenges most scheduling methods since they cannot fundamentally change job sequences to adaptively control production performance as jobs enter the system because actual processing times, are not known in advance. Some research literature indicates that simple rules are more suitable than algorithmic scheduling methods for adaptive control. In this work, a ‘state space – average processing time’ (SS-APT) heuristic is proposed and compared to four most commonly used scheduling rules and two well-established heuristics based on Taillard’s benchmarks. It is shown that the adaptive control is made possible under variation in processing times given the flexibility and strong performance of the SS-APT heuristic, especially for work-in-process inventory control.     

Evaluation of the Shortest Processing Time Scheduling Rule with Truncation Process

This paper discusses the development of a scheduling rule and summarizes the results of the evaluation of its performance with respect to some tardiness related criteria. Studies done on job shop scheduling indicated that the simple dispatching rules which mostly perform well with respect to a criterion of performance may have undesirable results with respect to other criteria. In this paper, a scheduling rule with truncation process called SPT-T is introduced and studied. Simulation results showed that the shortcomings of simple dispatching rules are remedied by using the SPT-T scheduling rule.     

Critical Ratio Scheduling with Queue Waiting Time Information: An Experimental Analysis

The Critical Ratio and Slack Time priority scheduling rules have been applied by a number of firms in computer-based scheduling systems for manufacturing operations. One question in using these rules is whether queue waiting time estimates for individual machines should be used in making scheduling decisions. Simulation experiments are reported in this paper that measure the effect of including historical queue time data in the Critical Ratio and Slack Time rules. The results suggest that such data can adversely affect shop performance, measured using criteria such as job flow times, job lateness, and inventory system costs.     

Fuzzy rule-based image processing

A novel image-processing technique based on fuzzy rules is proposed. This technique uses human knowledge about how an image should be processed depending on the local characteristics of image. The knowledge is represented by fuzzy rules and is also represented by a multidimensional nonlinear function which can be optimized by training. Efficient noise reduction and edge detection are realized by this fuzzy rule-based method. © 1997 John Wiley & Sons, Inc. Int J Imaging Syst Technol, 8, 457–461, 1997     

Production scheduling using adaptable fuzzy logic with genetic algorithms

Production scheduling for a flexible manufacturing environment must satisfy multiple conflicting criteria. Whilst estimation and modelling of capacity is facilitated by commercially available tools, the actual release strategy of orders into the system is still subject to considerable research as improved solutions over conventional dispatching heuristics are sought. An order release mechanism incorporating an adaptable fuzzy logic system enhanced by genetic algorithms is proposed. Through the use of fuzzy logic, the system can consider multiple criteria and rapidly determine solutions of consistently high quality. Adaptability ensures that the solution quality is maintained throughout the life of the system. The subsequent application of a genetic algorithm follows an efficient optimization path, since the initial solution derived through fuzzy logic is known to be good. The system developed, using the combined methodology, was tested on a discrete event simulation model and showed measurable benefits in schedule performance against commonly implemented dispatching heuristics.     

OPSYN: A CAD BASED EXPERT SYSTEM FOR OPTIMUM STRUCTURAL SYNTHESIS

This paper presents an overview of an expert system, OPSYN, for optimum structural synthesis, with particular emphasis on the significance of the development environment for such systems. The knowledge base for this system includes rules for facilitating finite element modeling, optimum design modeling, and selection of optimization strategies and parameters. The environment for this development is an inference engine with both forward and backward reasoning capabilities, a detailed explanation facility, and an automated knowledge acquisition system with a knowledge base editor facility. The use of a computer aided design (CAD) interface with its significant data structure and graphics capabilities in the knowledge acquisition and knowledge representation process is demonstrated with this expert system.     

A multiple-criteria real-time scheduling approach for multiple-load carriers subject to LIFO loading constraints

This paper studies the problem of scheduling a multiple-load carrier subject to last-in-first-out loading constraints in an automobile assembly line. Two scheduling criteria, the throughput of the assembly line and the material handling distance, are considered in order to maximise the profit of the assembly line. Different from other studies, the product mix and weights of the scheduling criteria are considered to be variable. A scheduling approach is proposed for the problem. At moments when the product mix or weights of the scheduling criteria change, the scheduling approach can select an appropriate rule from a set of given rules. In this study, the proposed approach is compared with other approaches by simulation in order to verify the performance of the proposed approach. The results indicate that, when the product mix and weights of the scheduling criteria are variable, the proposed scheduling approach outperforms other approaches.     

Multilevel intelligent scheduling and control system for an automated flow shop manufacturing environment

Current manufacturing scheduling and control systems are incapable of coping with complex system dynamics inherent in real-world situations and, hence, human intervention is required to maintain real-time adaptation and optimization. A unique feature of biological intelligent systems is that they build and improve over their communication, decision-making and control structures in real time autonomously. A challenge is now emerging in the design of manufacturing systems where on-line adaptation and optimization become increasingly important. This paper reports on the development of a new integrated intelligent scheduling and control system for an automated manufacturing environment using a multilevel approach. At the first level, a conventional scheduling and control system is considered, then at the second level, a new fuzzy logic mechanism is developed to enable the conventional system to improve and perceive the changes of system parameters adaptively. A new perturbation mechanism is embedded in the third level to implement on-line optimization for coping with the more complex structural changes of system dynamics. The final level is composed of artificial neural networks that can learn from experiences provided by the perturbation mechanism. The approach is designed to improve system intelligence gradually to cope with various forms of systems dynamics. A fully automated flow shop manufacturing system is taken to demonstrate this approach.     

基于模糊逻辑的两步卡尔曼滤波器设计

在对惯性运动跟踪系统的建模分析中,常采用基于计算机的集中式卡尔曼滤波算法进行数据处理。由于该方法存在算法复杂,处理数据速度慢等问题,难以在嵌入式系统中实现高速运动跟踪,提出一种基于模糊逻辑的自适应两步卡尔曼滤波算法。该方法根据人体不同的运动状态调整卡尔曼滤波器,实验结果证明所提的方法能够更好地估计各个传感器的测量精度,减少了运算量,并在一定程度上提高了滤波器的容错性能。     

Fuzzy inference-based multiple criteria FMS scheduling

This paper proposes a fuzzy inference-based scheduling decision for flexible manufacturing systems (FMS) with multiple objectives. The objectives have different and dynamic preference levels. It is inferred that the changes in the production environment may be sensed by environmental variables. The detected changes are input in a fuzzy inference mechanism, which outputs the current preference levels of all objectives. A multiple criteria scheduling decision is then made, using the partitioned combination of the preference levels. An example of application is presented. Simulation results show very good performance for the proposed system.