Dissimilarity Maximization Method for Real-time Routing of Parts in Random Flexible Manufacturing Systems

This paper presents a dissimilarity maximization method (DMM) for real-time routing selection and compares it via simulation with typical priority rules commonly used in scheduling and control of flexible manufacturing systems (FMSs). DMM aims to reduce the congestion in the system by selecting a routing for each part among its alternative routings such that the overall dissimilarity among the selected routings is maximized. In order to evaluate the performance of DMM, a random FMS, where the product mix is not known prior to production and off-line scheduling is not possible, is selected for the simulation study. A software environment that consists of a computer simulation model, which mimics a physical system, a C++ module, and a linear program solver is used to implement the DMM concept. In addition to DMM, the simulation study uses two priority rules for routing (i.e., machine) selection and seven priority rules for selecting parts awaiting service at machine buffers. The results show (1) DMM outperforms the other two routing selection rules on production rate regardless of the part selection rule used, and (2) its performance is highly dependent on the part selection rules it is combined with.     

A note on the selection of priority rules in software packages for project management

Various software packages for project management include a procedure for resource-constrained scheduling. In several packages, the user can influence this procedure by selecting a priority rule. However, the resource-allocation methods that are implemented in the procedures are proprietary information; therefore, the question of how the priority-rule selection impacts the performance of the procedures arises. We experimentally evaluate the resource-allocation methods of eight recent software packages using the 600 instances of the PSPLIB J120 test set. The results of our analysis indicate that applying the default rule tends to outperform a randomly selected rule, whereas applying two randomly selected rules tends to outperform the default rule. Applying a small set of more than two rules further improves the project durations considerably. However, a large number of rules must be applied to obtain the best possible project durations.     

Scheduling data analytics work with performance guarantees: queuing and machine learning models in synergy

In today’s scaled out systems, co-scheduling data analytics work with high priority user workloads is common as it utilizes better the vast hardware availability. User workloads are dominated by periodic patterns, with alternating periods of high and low utilization, creating promising conditions to schedule data analytics work during low activity periods. To this end, we show the effectiveness of machine learning models in accurately predicting user workload intensities, essentially by suggesting the most opportune time to co-schedule data analytics work. Yet, machine learning models cannot predict the effects of performance interference when co-scheduling is employed, as this constitutes a “new” observation. Specifically, in tiered storage systems, their hierarchical design makes performance interference even more complex, thus accurate performance prediction is more challenging. Here, we quantify the unknown performance effects of workload co-scheduling by enhancing machine learning models with queuing theory ones to develop a hybrid approach that can accurately predict performance and guide scheduling decisions in a tiered storage system. Using traces from commercial systems we illustrate that queuing theory and machine learning models can be used in synergy to surpass their respective weaknesses and deliver robust co-scheduling solutions that achieve high performance.     

A mixed dispatching rule approach in FMS scheduling

Short-term scheduling in flexible manufacturing systems (FMSs) is a difficult problem because of the complexities and dynamic behavior of FMSs. To solve this problem, a dispatching rule approach is widely used. In this approach, however, a single dispatching rule is usually assigned for all machines in a system during a given scheduling interval. In this paper, a mixed dispatching rule which can assign a different dispatching rule for each machine is proposed. A search algorithm which selects an appropriate mixed dispatching rule using predictions based on discrete event simulation is developed for this approach. The search algorithm for the mixed dispatching rule is described in detail. The effectiveness (in meeting performance criteria) of the mixed dispatching rule and the efficiency of the search algorithm relative to exhaustive search (complete enumeration) is demonstrated on an FMS model. The mixed dispatching rule approach performs up to 15.9% better than the conventional approach, and is 4% better on average. The statistical significance of the results is dicussed.     

A Genetic Algorithm Approach to the Scheduling of FMSs with Multiple Routes

Usually, most of the typical job shop scheduling approaches deal with the processing sequence of parts in a fixed routing condition. In this paper, we suggest a genetic algorithm (GA) to solve the job-sequencing problem for a production shop that is characterized by flexible routing and flexible machines. This means that all parts, of all part types, can be processed through alternative routings. Also, there can be several machines for each machine type. To solve these general scheduling problems, a genetic algorithm approach is proposed and the concepts of virtual and real operations are introduced. Chromosome coding and genetic operators of GAs are defined during the problem solving. A minimum weighted tardiness objective function is used to define code fitness, which is used for selecting species and producing a new generation of codes. Finally, several experimental results are given.     

Information-Based Dynamic Manufacturing System Scheduling

Information about the state of the system is of paramount importance in determining the dynamics underlying manufacturing systems. In this paper, we present an adaptive scheduling policy for dynamic manufacturing system scheduling using information obtained from snapshots of the system at various points in time. Specifically, the framework presented allows for information-based dynamic scheduling where information collected about the system is used to (1) adjust appropriate parameters in the system and (2) search or optimize using genetic algorithms. The main feature of this policy is that it tailors the dispatching rule to be used at a given point in time to the prevailing state of the system. Experimental studies indicate the superiority of the suggested approach over the alternative approach involving the repeated application of a single dispatching rule for randomly generated test problems as well as a real system. In pa ticular, its relative performance improves further when there are frequent disruptions and when disruptions are caused by the introduction of tight due date jobs and machine breakdown—two of the most common sources of disruption in most manufacturing systems. From an operational perspective, the most important characteristics of the pattern-directed scheduling approach are its ability to incorporate the idiosyncratic characteristics of the given system into the dispatching rule selection process and its ability to refine itself incrementally on a continual basis by taking new system parameters into account.     

Association pattern mining of intron retention events in human based on hybrid learning machine

Alternative splicing is a main component of protein diversity, and aberrant splicing is known to be one of the main causes of genetic disorders such as cancer. Many statistical and computational approaches have identified several major factors that determine the splicing event, such as exon/intron length, splice site strength, and density of splicing enhancers or silencers. These factors may be correlated with one another and thus result in a specific type of splicing, but there has not been a systematic approach to extracting comprehensible association patterns. Here, we attempted to understand the decision making process of the learning machine on intron retention event. We adopted a hybrid learning machine approach using a random forest and association rule mining algorithm to determine the governing factors of intron retention events and their combined effect on decision-making processes. By quantifying all candidate features into five category values, we enhanced the understandability of generated rules. The interesting features found by the random forest algorithm are that only the adenine- and thymine-based triplets such as ATA, TTA, and ATT, but not the known intronic splicing enhancer GGG triplet is shown the significant features. The rules generated by the association rule mining algorithm also show that constitutive introns are generally characterized by high adenine- and thymine-based triplet frequency (level 3 and above), 3' and 5' splice site scores, exonic splicing silencer scores, and intron length, whereas retained introns are characterized by low-level counterpart scores.     

Experimental investigation of an FMS due-date scheduling problem: Evaluation of machine and AGV scheduling rules

Although extensive research has been conducted to solve design and operational problems of automated manufacturing systems, many of the problems still remain unsolved. This article investigates the scheduling problems of flexible manufacturing systems (FMSs). Specifically, the relative performances of machine and automated guided vehicle (AGV) scheduling rules are analyzed against various due-date criteria. First, the relevant literature is briefly reviewed, and then the rules are tested under different experimental conditions by using a simulation model of an FMS. The sensitivity to AGV workload, buffer capacity, and processing-time distribution is also investigated to assess the robustness of the scheduling rules.     

Intelligent scheduling of FMSs with inductive learning capability using neural networks

With the growing uncertainty and complexity in the manufacturing environment, most scheduling problems have been proven to be NP-complete and this can degrade the performance of conventional operations research (OR) techniques. This article presents a system-attribute-oriented knowledge-based scheduling system (SAOSS) with inductive learning capability. With the rich heritage from artificial intelligence (AI), SAOSS takes a multialgorithm paradigm which makes it more intelligent, flexible, and suitable than others for tackling complicated, dynamic scheduling problems. SAOSS employs an efficient and effective inductive learning method, a continuous iterative dichotomister 3 (CID3) algorithm, to induce decision rules for scheduling by converting corresponding decision trees into hidden layers of a self-generated neural network. Connection weights between hidden units imply the scheduling heuristics, which are then formulated into scheduling rules. An FMS scheduling problem is also given for illustration. The scheduling results show that the system-attribute-oriented knowledge-based approach is capable of addressing dynamic scheduling problems.     

A new branch and bound algorithm for loading problems in flexible manufacturing systems

Loading problems in flexible manufacturing systems involve assigning operations for selected part types and their associated tools to machines or machine groups. One of the objectives might be to maximize the expected production rate (throughput) of the system. Because of the difficulty in dealing with this objective directly, a commonly used surrogate objective is the closeness of the actual workload allocation to the continuous workload allocation that maximizes throughput. We test several measures of closeness and discuss correlations between these measures and throughput. Using the best measure, we show how to modify an existing branch and bound algorithm which was developed for the case of equal target workloads for all machine groups to accommodate unequal target workloads. We also develop a new branch and bound algorithm which can be used for both types of problems. The efficiency of the algorithm in finding optimal solutions is achieved through the application of better branching rules and improved dominance results. Computational results on randomly generated test problems indicate that the new algorithm performs well.     

Rule Extraction Based on Extreme Learning Machine and an Improved Ant-Miner Algorithm for Transient Stability Assessment

In order to overcome the problems of poor understandability of the pattern recognition-based transient stability assessment (PRTSA) methods, a new rule extraction method based on extreme learning machine (ELM) and an improved Ant-miner (IAM) algorithm is presented in this paper. First, the basic principles of ELM and Ant-miner algorithm are respectively introduced. Then, based on the selected optimal feature subset, an example sample set is generated by the trained ELM-based PRTSA model. And finally, a set of classification rules are obtained by IAM algorithm to replace the original ELM network. The novelty of this proposal is that transient stability rules are extracted from an example sample set generated by the trained ELM-based transient stability assessment model by using IAM algorithm. The effectiveness of the proposed method is shown by the application results on the New England 39-bus power system and a practical power system — the southern power system of Hebei province.     

Automating parallel implementation of neural learning algorithms

Neural learning algorithms generally involve a number of identical processing units, which are fully or partially connected, and involve an update function, such as a ramp, a sigmoid or a Gaussian function for instance. Some variations also exist, where units can be heterogeneous, or where an alternative update technique is employed, such as a pulse stream generator. Associated with connections are numerical values that must be adjusted using a learning rule, and and dictated by parameters that are learning rule specific, such as momentum, a learning rate, a temperature, amongst others. Usually, neural learning algorithms involve local updates, and a global interaction between units is often discouraged, except in instances where units are fully connected, or involve synchronous updates. In all of these instances, concurrency within a neural algorithm cannot be fully exploited without a suitable implementation strategy. A design scheme is described for translating a neural learning algorithm from inception to implementation on a parallel machine using PVM or MPI libraries, or onto programmable logic such as FPGAs. A designer must first describe the algorithm using a specialised Neural Language, from which a Petri net (PN) model is constructed automatically for verification, and building a performance model. The PN model can be used to study issues such as synchronisation points, resource sharing and concurrency within a learning rule. Specialised constructs are provided to enable a designer to express various aspects of a learning rule, such as the number and connectivity of neural nodes, the interconnection strategies, and information flows required by the learning algorithm. A scheduling and mapping strategy is then used to translate this PN model onto a multiprocessor template. We demonstrate our technique using a Kohonen and backpropagation learning rules, implemented on a loosely coupled workstation cluster, and a dedicated parallel machine, with PVM libraries.     

Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics

We investigate a difficult scheduling problem in a semiconductor manufacturing process that seeks to minimize the number of tardy jobs and makespan with sequence-dependent setup time, release time, due dates and tool constraints. We propose a mixed integer programming (MIP) formulation which treats tardy jobs as soft constraints so that our objective seeks the minimum weighted sum of makespan and heavily penalized tardy jobs. Although our polynomial-sized MIP formulation can correctly model this scheduling problem, it is so difficult that even a feasible solution can not be calculated efficiently for small-scale problems. We then propose a technique to estimate the upper bound for the number of jobs processed by a machine, and use it to effectively reduce the size of the MIP formulation. In order to handle real-world large-scale scheduling problems, we propose an efficient dispatching rule that assigns a job of the earliest due date to a machine with least recipe changeover (EDDLC) and try to re-optimize the solution by local search heuristics which involves interchange, translocation and transposition between assigned jobs. Our computational experiments indicate that EDDLC and our proposed reoptimization techniques are very efficient and effective. In particular, our method usually gives solutions very close to the exact optimum for smaller scheduling problems, and calculates good solutions for scheduling up to 200 jobs on 40 machines within 10 min.     

The application of rule-based methods to class prediction problems in genomics.

We propose a method for constructing classifiers using logical combinations of elementary rules. The method is a form of rule-based classification, which has been widely discussed in the literature. In this work we focus specifically on issues that arise in the context of classifying cell samples based on RNA or protein expression measurements. The basic idea is to specify elementary rules that exhibit a locally strong pattern in favor of a single class. Strict admissibility criteria are imposed to produce a manageable universe of elementary rules. Then the elementary rules are combined using a set covering algorithm to form a composite rule that achieves a perfect fit to the training data. The user has explicit control over a parameter that determines the composite rule's level of redundancy and parsimony. This built-in control, along with the simplicity of interpreting the rules, makes the method particularly useful for classification problems in genomics. We demonstrate the new method using several microarray datasets and examine its generalization performance. We also draw comparisons to other machine-learning strategies such as CART, ID3, and C4.5.     

Hybrid FMS control architectures based on holonic principles

The escalation in processor technologies and the corresponding reduction in costs have enabled alternative FMS control architectures to be developed without the restrictions of “fixed machine controller boundaries”. These new architectures can be based upon the use of intelligent servo axes, which are desccribed in this article, as flexible numerical control (FNC). In current parlance, the FNC is a “part movement holon” within a manufacturing cell. The control architectures that can be derived from the FNC concept are referred to as hybrid architectures and share the emerging attributes of holonics. This article details the problems that arise in the scheduling and control of FMSs in the light of hybrid control architectures. A number of traditional scheduling approaches have been devised to cope with the scheduling of parts to discrete machines, but the problem here is to ascribe the processing (machining) of part features to axis groups. This article documents how two research programs, undertaken at the CIM Centre at Swinburne University of Technology in Hawthorn, Victoria, Australia, have endeavored to address the problem of hybrid architectures and their associated scheduling.     

XCSc: a novel approach to clustering with extended classifier system

In this paper, we propose a novel approach to clustering noisy and complex data sets based on the eXtend Classifier Systems (XCS). The proposed approach, termed XCSc, has three main processes: (a) a learning process to evolve the rule population, (b) a rule compacting process to remove redundant rules after the learning process, and (c) a rule merging process to deal with the overlapping rules that commonly occur between the clusters. In the first process, we have modified the clustering mechanisms of the current available XCS and developed a new accelerate learning method to improve the quality of the evolved rule population. In the second process, an effective rule compacting algorithm is utilized. The rule merging process is based on our newly proposed agglomerative hierarchical rule merging algorithm, which comprises the following steps: (i) all the generated rules are modeled by a graph, with each rule representing a node; (ii) the vertices in the graph are merged to form a number of sub-graphs (i.e. rule clusters) under some pre-defined criteria, which generates the final rule set to represent the clusters; (iii) each data is re-checked and assigned to a cluster that it belongs to, guided by the final rule set. In our experiments, we compared the proposed XCSc with CHAMELEON, a benchmark algorithm well known for its excellent performance, on a number of challenging data sets. The results show that the proposed approach outperforms CHAMELEON in the successful rate, and also demonstrates good stability.     

Multi-objective workflow scheduling in Amazon EC2

Nowadays, scientists and companies are confronted with multiple competing goals such as makespan in high-performance computing and economic cost in Clouds that have to be simultaneously optimised. Multi-objective scheduling of scientific applications in these systems is therefore receiving increasing research attention. Most existing approaches typically aggregate all objectives in a single function, defined a-priori without any knowledge about the problem being solved, which negatively impacts the quality of the solutions. In contrast, Pareto-based approaches having as outcome a set of (nearly) optimal solutions that represent a tradeoff among the different objectives, have been scarcely studied. In this paper, we analyse MOHEFT, a Pareto-based list scheduling heuristic that provides the user with a set of tradeoff optimal solutions from which the one that better suits the user requirements can be manually selected. We demonstrate the potential of our method for multi-objective workflow scheduling on the commercial Amazon EC2 Cloud. We compare the quality of the MOHEFT tradeoff solutions with two state-of-the-art approaches using different synthetic and real-world workflows: the classical HEFT algorithm for single-objective scheduling and the SPEA2* genetic algorithm used in multi-objective optimisation problems. The results demonstrate that our approach is able to compute solutions of higher quality than SPEA2*. In addition, we show that MOHEFT is more suitable than SPEA2* for workflow scheduling in the context of commercial Clouds, since the genetic-based approach is unable of dealing with some of the constraints imposed by these systems.     

Controlling flexible manufacturing systems based on a dynamic selection of the appropriate operational criteria and scheduling policy

This study presents the development of a multi-criteria control methodology for flexible manufacturing systems (FMSs). The control methodology is based on a two-tier decision making mechanism. The first tier is designed to select a dominant decision criterion and a relevant scheduling rule set using a rule-based algorithm. In the second tier, using a look-ahead multi-pass simulation, a scheduling rule that best advances the selected criterion is determined. The decision making mechanism was integrated with the shop floor control module that comprises a real-time simulation model at the top control level and RapidCIM methodology at the low equipment control level. A factorial experiment was designed to analyze and evaluate the two-tier decision making mechanism and the effects that the main design parameters have on the system’s performance. Next, the proposed control methodology was compared to a selected group of scheduling rules/policies using DEA. The results demonstrated the superiority of the suggested control methodology as well as its capacity to cope with a fast changing environment.     

Mirrored STDP Implements Autoencoder Learning in a Network of Spiking Neurons

The autoencoder algorithm is a simple but powerful unsupervised method for training neural networks. Autoencoder networks can learn sparse distributed codes similar to those seen in cortical sensory areas such as visual area V1, but they can also be stacked to learn increasingly abstract representations. Several computational neuroscience models of sensory areas, including Olshausen & Field’s Sparse Coding algorithm, can be seen as autoencoder variants, and autoencoders have seen extensive use in the machine learning community. Despite their power and versatility, autoencoders have been difficult to implement in a biologically realistic fashion. The challenges include their need to calculate differences between two neuronal activities and their requirement for learning rules which lead to identical changes at feedforward and feedback connections. Here, we study a biologically realistic network of integrate-and-fire neurons with anatomical connectivity and synaptic plasticity that closely matches that observed in cortical sensory areas. Our choice of synaptic plasticity rules is inspired by recent experimental and theoretical results suggesting that learning at feedback connections may have a different form from learning at feedforward connections, and our results depend critically on this novel choice of plasticity rules. Specifically, we propose that plasticity rules at feedforward versus feedback connections are temporally opposed versions of spike-timing dependent plasticity (STDP), leading to a symmetric combined rule we call Mirrored STDP (mSTDP). We show that with mSTDP, our network follows a learning rule that approximately minimizes an autoencoder loss function. When trained with whitened natural image patches, the learned synaptic weights resemble the receptive fields seen in V1. Our results use realistic synaptic plasticity rules to show that the powerful autoencoder learning algorithm could be within the reach of real biological networks.     

流域管理决策支持系统研究进展

流域管理决策支持系统是为帮助流域管理者实现水资源优化配置而研发的智能系统,其模拟结果直接影响流域管理的科学性和实用性.本文从水量模拟和调配系统、水质监测和评价系统、流域综合管理系统三方面总结了国内外的相关研究,并分析了现存系统的特点和存在的问题,同时简要介绍AQUA-Tool、Elbe-DSS、HD等代表性系统的模型结构和发展现状.模拟结果精确稳定、工作流程简洁、用户可视化程度高是流域管理决策支持系统的研发重点,优化方案选择模型和三维可视化工具、研发跨流域综合管理系统、提高利益相关者的参与度是未来该领域的发展方向.