A novel genetic algorithm for solving production and transportation scheduling in a two-stage supply chain

This study considers the scheduling of products and vehicles in a two-stage supply chain environment. The first stage contains m suppliers with different production speeds, while the second stage is composed of l vehicles, each of which may have a different speed and different transport capacity. In addition, it is assumed that the various output products occupy different percentages of each vehicle’s capacity. We model the situation as a mixed integer programming problem, and, to solve it, we propose a gendered genetic algorithm (GGA) that considers two different chromosomes with non-equivalent structures. Our experimental results show that GGA offers better performance than standard genetic algorithms that feature a unique chromosomal structure. In addition, we compare the GGA performance with that of the most similar problem reported to date in the literature as proposed by Chang and Lee [Chang, Y., & Lee, C. (2004). Machine scheduling with job delivery coordination. European Journal of Operational Research, 158(2), 470–487]. The experimental results from our comparisons illustrate the promising potential of the new GGA approach.     

Computational analysis of machine repair problem with unreliable multi-repairmen

This paper considers a multi-repairmen problem comprising of M operating machines with W warm standbys (spares). Both operating and warm standby machines are subject to failures. With a coverage probability c, a failed unit is immediately detected and attended by one of R repairmen if available. If the failed unit is not detected with probability 1−c, the system enters an unsafe state and must be cleared by a reboot action. The repairmen are also subject to failures which result in service (repair) interruptions. The failed repairman resumes service after a random period of time. In addition, the repair rate depends on number of failed machines. The entire system is modeled as a finite-state Markov chain and its steady state distribution is obtained by a recursive matrix approach. The major performance measures are evaluated based on this distribution. Under a cost structure, we propose to use the Quasi-Newton method and probabilistic global search Lausanne method to search for the global optimal system parameters. Numerical examples are presented to demonstrate the effectiveness of our approach in solving a highly complex manufacturing system subject to multiple uncertainties.     

On path dependent loss and switch crosstalk reduction in optical networks

Although optical multistage interconnection networks (OMINs) promise to meet the ever growing demands of communication networks and multiprocessor systems in fast communication, they suffer from challenges such as path dependent loss and switch crosstalk. In this paper, we propose an innovative approach for reducing not only the path dependent loss but also the number of switch crosstalks in OMINs. Our approach is centered upon modelling OMINs with Petri nets and using the P-invariants method to determine the minimum number of stages m_min that is sufficient to establish requested communication patterns in variable-stage OMINs. Being composed of the smallest number of stages and consequently directional couplers (or photonic switches), m_min-stage OMIN employs minimal structure and, therefore, path dependent loss and also number of switch crosstalks reach the least possible values in the realization of requested communication patterns.We prove that the size of Petri nets created in this work is in polynomial dependence on the problem size which alleviates memory consumption significantly and ascertains the fact that memory capacity and performance of modern computers are indeed sufficient to run our task. We also show that the complexity results obtained in this research improve similar results reported in our previous paper. We carry out a series of computer experiments to confirm the effectiveness of the proposed approach.     

Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization

We show that the NP-complete Feedback Vertex Set problem, which asks for the smallest set of vertices to remove from a graph to destroy all cycles, is deterministically solvable in O(ck⋅m) time. Here, m denotes the number of graph edges, k denotes the size of the feedback vertex set searched for, and c is a constant. We extend this to an algorithm enumerating all solutions in O(dk⋅m) time for a (larger) constant d. As a further result, we present a fixed-parameter algorithm with runtime O(k²⋅m²) for the NP-complete Edge Bipartization problem, which asks for at most k edges to remove from a graph to make it bipartite.     

A naive Bayes probability estimation model based on self-adaptive differential evolution

In the process of learning the naive Bayes, estimating probabilities from a given set of training samples is crucial. However, when the training samples are not adequate, probability estimation method will inevitably suffer from the zero-frequency problem. To avoid this problem, Laplace-estimate and M-estimate are the two main methods used to estimate probabilities. The estimation of two important parameters m (integer variable) and p (probability variable) in these methods has a direct impact on the underlying experimental results. In this paper, we study the existing probability estimation methods and carry out a parameter Cross-test by experimentally analyzing the performance of M-estimate with different settings for the two parameters m and p. This part of experimental result shows that the optimal parameter values vary corresponding to different data sets. Motivated by these analysis results, we propose an estimation model based on self-adaptive differential evolution. Then we propose an approach to calculate the optimal m and p value for each conditional probability to avoid the zero-frequency problem. We experimentally test our approach in terms of classification accuracy using the 36 benchmark machine learning repository data sets, and compare it to a naive Bayes with Laplace-estimate and M-estimate with a variety of setting of parameters from literature and those possible optimal settings via our experimental analysis. The experimental results show that the estimation model is efficient and our proposed approach significantly outperforms the traditional probability estimation approaches especially for large data sets (large number of instances and attributes).     

Efficient visual secret sharing scheme for color images

A k-out-of-n visual secret sharing scheme (VSSS) resolves the visual variant of the k-out-of-n secret sharing problem where only k or more out of n participants can reveal the secret by human visual system without any cryptographic computation. The best pixel expansion of the general k-out-of-n VSSS for c-colored images was c×m by Yang and Laih [New colored visual secret sharing schemes, Des Codes Cryptogr. 24 (2000) 325-335] where m is the pixel expansion of an existing binary k-out-of-n VSSS. Regarding the c-colored n-out-of-n scheme, the best pixel expansion is (c-1)2^n-1-c+2 and c(c-1)2^n-2-c when n is odd and even, respectively, by Blundo et al. [Improved schemes for visual cryptography, Des Codes Cryptogr. 24 (2001) 255-278]. In this paper, we propose a new c-colored k-out-of-n VSSS by using a pixel expansion of that is more efficient than ever.     

Improving vector space embedding of graphs through feature selection algorithms

Graph based pattern representation offers a versatile alternative to vectorial data structures. Therefore, a growing interest in graphs can be observed in various fields. However, a serious limitation in the use of graphs is the lack of elementary mathematical operations in the graph domain, actually required in many pattern recognition algorithms. In order to overcome this limitation, the present paper proposes an embedding of a given graph population in a vector space Rⁿ. The key idea of this embedding approach is to interpret the distances of a graph g to a number of prototype graphs as numerical features of g. In previous works, the prototypes were selected beforehand with heuristic selection algorithms. In the present paper we take a more fundamental approach and regard the problem of prototype selection as a feature selection or dimensionality reduction problem, for which many methods are available. With several experiments we show the feasibility of graph embedding based on prototypes obtained from such feature selection algorithms and demonstrate their potential to outperform previous approaches.     

Efficient allocation and composition of distributed storage

In this paper, we investigate the composition of cheap network storage resources to meet specific availability and capacity requirements. We show that the problem of finding the optimal composition for availability and price requirements can be reduced to the knapsack problem, and propose three techniques for efficiently finding approximate solutions. The first algorithm uses a dynamic programming approach to find mirrored storage resources for high availability requirements, and runs in the pseudo-polynomial O(n ² c) time where n is the number of sellers’ resources to choose from and c is a capacity function of the requested and minimum availability. The second technique is a heuristic which finds resources to be agglomerated into a larger coherent resource, with complexity of O(nlog?n). The third technique finds a compromise between capacity and availability (which in our phrasing is a complex integer programming problem) using a genetic algorithm. The algorithms can be implemented on a broker that intermediates between buyers and sellers of storage resources. Finally, we show that a broker in an open storage market, using the combination of the three algorithms can more frequently meet user requests and lower the cost of requests that are met compared to a broker that simply matches single resources to requests.     

Redundant modeling in permutation weighted constraint satisfaction problems

In classical constraint satisfaction, redundant modeling has been shown effective in increasing constraint propagation and reducing search space for many problem instances. In this paper, we investigate, for the first time, how to benefit the same from redundant modeling in weighted constraint satisfaction problems (WCSPs), a common soft constraint framework for modeling optimization and over-constrained problems. Our work focuses on a popular and special class of problems, namely, permutation problems. First, we show how to automatically generate a redundant permutation WCSP model from an existing permutation WCSP using generalized model induction. We then uncover why naively combining mutually redundant permutation WCSPs by posting channeling constraints as hard constraints and relying on the standard node consistency (NC*) and arc consistency (AC*) algorithms would miss pruning opportunities, which are available even in a single model. Based on these observations, we suggest two approaches to handle the combined WCSP models. In our first approach, we propose m\text -NC_{\text c}^*m\text {-NC}_{\text c}^* and m\text -AC_{\text c}^*m\text {-AC}_{\text c}^* and their associated algorithms for effectively enforcing node and arc consistencies in a combined model with m sub-models. The two notions are strictly stronger than NC* and AC* respectively. While the first approach specifically refines NC* and AC* so as to apply to combined models, in our second approach, we propose a parameterized local consistency LB(m,Φ). The consistency can be instantiated with any local consistency Φ for single models and applied to a combined model with m sub-models. We also provide a simple algorithm to enforce LB(m,Φ). With the two suggested approaches, we demonstrate their applicabilities on several permutation problems in the experiments. Prototype implementations of our proposed algorithms confirm that applying 2\text -NC_{\text c}^*,  2\text -AC_{\text c}^*2\text {-NC}_{\text c}^*,\;2\text {-AC}_{\text c}^*, and LB(2,Φ) on combined models allow far more constraint propagation than applying the state-of-the-art AC*, FDAC*, and EDAC* algorithms on single models of hard benchmark problems.     

A memetic algorithm for the capacitated m-ring-star problem

The Capacitated m-Ring-Star Problem (CmRSP) models a network topology design problem in the telecommunications industry. In this paper, we propose to solve this problem using a memetic algorithm that includes a crossover operation, a mutation operation, a local search involving three neighborhood operators, and a population selection strategy that maintains population diversity. Our approach generates the best known solutions for 131 out of 138 benchmark instances, improving on the previous best solutions for 24 of them, and exhibits more advantages on large benchmark instances when compared with the best existing approach. Additionally, all existing algorithms for this problem in literature assume that the underlying graph of the problem instance satisfies the triangle inequality rule; our approach does not require this assumption. We also generated a new set of 36 larger test instances based on a digital data service network price structure to serve as a new benchmark data set for future researchers.     

Petri net based decision system modeling in real-time scheduling and control of flexible automotive manufacturing systems

This paper presents the design and the implementation of a Petri net (PN) model for the control of a flexible manufacturing system (FMS). A flexible automotive manufacturing system used in this environment enables quick cell configuration, and the efficient operation of cells. In this paper, we attempt to propose a flexible automotive manufacturing approach for modeling and analysis of shop floor scheduling problem of FMSs using high-level PNs. Since PNs have emerged as the principal performance modeling tools for FMS, this paper provides an object-oriented Petri nets (OOPNs) approach to performance modeling and to implement efficient production control. In this study, we modeled the system as a timed marked graph (TMG), a well-known subclass of PNs, and we showed that the problem of performance evaluation can be reduced to a simple linear programming (LP) problem with m − n + 1 variables and n constraints, where m and n represent the number of places and transitions in the marked graph, respectively. The presented PN based method is illustrated by modeling a real-time scheduling and control for flexible automotive manufacturing system (FAMS) in Valeo Turkey.     

An algorithm for Exact Satisfiability analysed with the number of clauses as parameter

We give an algorithm for Exact Satisfiability with polynomial space usage and a time bound of poly(L)⋅m!, where m is the number of clauses and L is the length of the formula. Skjernaa has given an algorithm for Exact Satisfiability with time bound poly(L)⋅m² but using exponential space. We leave the following problem open: Is there an algorithm for Exact Satisfiability using only polynomial space with a time bound of cm, where c is a constant and m is the number of clauses?     

Scheduling imprecise computation tasks on uniform processors

We consider the problem of preemptively scheduling n imprecise computation tasks on m?1 uniform processors, with each task Ti having two weights wi and . Three objectives are considered: (1) minimizing the maximum w^′-weighted error; (2) minimizing the total w-weighted error subject to the constraint that the maximum w^′-weighted error is minimized; (3) minimizing the maximum w^′-weighted error subject to the constraint that the total w-weighted error is minimized. For these objectives, we give polynomial time algorithms with time complexity O(mn⁴), O(mn⁴) and O(kmn⁴), respectively, where k is the number of distinct w-weights. We also present alternative algorithms for the three objectives, with time complexity O(cmn³), O(cmn³+mn⁴) and O(kcmn³), respectively, where c is a parameter-dependent number.     

Row and column generation technique for a multistage cutting stock problem

The multistage cutting stock problem (CSP) generalizes the one-dimensional CSP when a lengthwise cutting process is distributed over two or more successive stages. At every stage of the cutting process incoming rolls are slit into smaller rolls by width. The problem is to minimize total trim loss occurring at all stages of technological process meeting customer demands for finished rolls. We propose a row and column generation technique for solving the multistage one-dimensional CSP. The technique is a generalization of the column generation method suggested by Gilmore and Gomory for solving a classic CSP. The procedure generates only those intermediate rolls (rows) and cutting patterns (columns) that are needed. An auxiliary problem embedded into the frame of the revised simplex algorithm is a non-linear knapsack problem that can be solved efficiently. Computational results prove the overall method is a valuable addition to the tool set for modeling and solving the multistage CSP.Scope and purposeWe investigate a broad class of large-scale linear programming models and suggest a new and efficient way to solve them. The proposed method belongs to a category of decomposition techniques generalizing the famous column generation method. An iteration of the revised simplex algorithm may “enrich” the LP matrix either by generating a new column, as a purely column generation method does, or by generating a combination of a new row and a pair of new columns. The method is a row and column generation technique that we propose and investigate. Applications modeled by a multistage CSP occur in the industries that use a multistage cutting process: paper, leather, film, steel, etc., or a nested packing/loading process: transportation. The unknown variables in the multistage cutting stock problem are intermediate sizes (rows) and cutting patterns (columns). According to the algorithm both are to be generated dynamically. The proposed algorithm brings tremendous benefits in terms of the quality of solutions and computational performance.     

Efficient algorithms for finding interleaving relationship between sequences

The longest common subsequence and sequence alignment problems have been studied extensively and they can be regarded as the relationship measurement between sequences. However, most of them treat sequences evenly or consider only two sequences. Recently, with the rise of whole-genome duplication research, the doubly conserved synteny relationship among three sequences should be considered. It is a brand new model to find a merging way for understanding the interleaving relationship of sequences. Here, we define the merged LCS problem for measuring the interleaving relationship among three sequences. An O(n³) algorithm is first proposed for solving the problem, where n is the sequence length. We further discuss the variant version of this problem with the block information. For the blocked merged LCS problem, we propose an algorithm with time complexity O(n²m), where m is the number of blocks. An improved O(n²+nm²) algorithm is further proposed for the same blocked problem.     

An exact schema theorem for adaptive genetic algorithm and its application to machine cell formation

This paper proposes an exact schema theorem that is able to predict the expected number of copies of schemas in the next GA generation. It focuses on two-point crossover, which is widely used in many GA applications. As two important GA control parameters, crossover probability (p_c) and mutation probability (p_m) affect the performance of GAs drastically. A set of good GA parameters help in improving the ability of a GA to search for near global optimal solutions. This work shows that optimal p_c and p_m do not exist in most cases. As a result, a compromised pair of p_c and p_m may help improve the performance of GA. A multiple population search strategy enabled fuzzy c-means based evolutionary approach, which embeds the proposed exact schema theorem, to machine cell formation is then proposed. The approach enables the crossover and mutation probabilities of GAs to be made adaptive to suit different stages of the search for near optimal solutions. Three case studies were conducted. The proposed approach was able to provide better solutions consistently.     

Combined pattern search optimization of feature extraction and classification parameters in facial recognition

Constantly, the assumption is made that there is an independent contribution of the individual feature extraction and classifier parameters to the recognition performance. In our approach, the problems of feature extraction and classifier design are viewed together as a single matter of estimating the optimal parameters from limited data. We propose, for the problem of facial recognition, a combination between an Interest Operator based feature extraction technique and a k-NN statistical classifier having the parameters determined using a pattern search based optimization technique. This approach enables us to achieve both higher classification accuracy and faster processing time.     

Cluster-based dynamic variance adaptation for interconnecting speech enhancement pre-processor and speech recognizer

A conventional approach to noise robust speech recognition consists of employing a speech enhancement pre-processor prior to recognition. However, such a pre-processor usually introduces artifacts that limit recognition performance improvement. In this paper we discuss a framework for improving the interconnection between speech enhancement pre-processors and a recognizer. The framework relies on recent proposals for increasing robustness by replacing the point estimate of the enhanced features with a distribution with a dynamic (i.e. time varying) feature variance. We have recently proposed a model for the dynamic feature variance consisting of a dynamic feature variance root obtained from the pre-processor, which is multiplied by a weight representing the pre-processor uncertainty, and that uses adaptation data to optimize the pre-processor uncertainty weight. The formulation of the method is general and could be used with any speech enhancement pre-processor. However, we observed that in case of noise reduction based on spectral subtraction or related approaches, adaptation could fail because the proposed model is weak at representing well the actual dynamic feature variance. The dynamic feature variance changes according to the level of speech sound, which varies with the HMM states. Therefore, we propose improving the model by introducing HMM state dependency. We achieve this by using a cluster-based representation, i.e. the Gaussians of the acoustic model are grouped into clusters and a different pre-processor uncertainty weight is associated with each cluster. Experiments with various pre-processors and recognition tasks prove the generality of the proposed integration scheme and show that the proposed extension improves the performance with various speech enhancement pre-processors.     

An anchor-based spectral clustering method

Spectral clustering is one of the most popular and important clustering methods in pattern recognition, machine learning, and data mining. However, its high computational complexity limits it in applications involving truly large-scale datasets. For a clustering problem with n samples, it needs to compute the eigenvectors of the graph Laplacian with O(n³) time complexity. To address this problem, we propose a novel method called anchor-based spectral clustering (ASC) by employing anchor points of data. Specifically, m (m ? n) anchor points are selected from the dataset, which can basically maintain the intrinsic (manifold) structure of the original data. Then a mapping matrix between the original data and the anchors is constructed. More importantly, it is proved that this data-anchor mapping matrix essentially preserves the clustering structure of the data. Based on this mapping matrix, it is easy to approximate the spectral embedding of the original data. The proposed method scales linearly relative to the size of the data but with low degradation of the clustering performance. The proposed method, ASC, is compared to the classical spectral clustering and two state-of-the-art accelerating methods, i.e., power iteration clustering and landmark-based spectral clustering, on 10 real-world applications under three evaluation metrics. Experimental results show that ASC is consistently faster than the classical spectral clustering with comparable clustering performance, and at least comparable with or better than the state-of-the-art methods on both effectiveness and efficiency.     

Quorum-based mutual exclusion in asynchronous distributed systems with unreliable failure detectors

This paper considers the fault-tolerant quorum-based mutual exclusion problem in a message-passing asynchronous system and determines a failure detector to solve the problem. This failure detector, which we call the modal failure detector star, and which we denote by M ^?, is strictly weaker than the perfect failure detector P but strictly stronger than the eventually perfect failure detector ?P. The paper shows that at any environment, the problem is solvable with M ^?. In addition, we make an analysis of our algorithm performance in terms of the number of messages and synchronization delay.