A Constructive Genetic Algorithm for permutation flowshop scheduling

The general flowshop scheduling problem is a production problem where a set of n jobs have to be processed with identical flow pattern on in machines. In permutation flowshops the sequence of jobs is the same on all machines. A significant research effort has been devoted for sequencing jobs in a flowshop minimizing the makespan. This paper describes the application of a Constructive Genetic Algorithm (CGA) to makespan minimization on flowshop scheduling. The CGA was proposed recently as an alternative to traditional GA approaches, particularly, for evaluating schemata directly. The population initially formed only by schemata, evolves controlled by recombination to a population of well-adapted structures (schemata instantiation). The CGA implemented is based on the NEH classic heuristic and a local search heuristic used to define the fitness functions. The parameters of the CGA are calibrated using a Design of Experiments (DOE) approach. The computational results are compared against some other successful algorithms from the literature on Taillard`s well-known standard benchmark. The computational experience shows that this innovative CGA approach provides competitive results for flowshop scheduling; problems. (C) 2007 Elsevier Ltd. All rights reserved.

Reducing mean flow time in permutation flow shop

This paper deals with the traditional permutation flow shop scheduling problem with the objective of minimizing mean flowtime, therefore reducing in-process inventory. A new heuristic method is proposed for the scheduling problem solution. The proposed heuristic is compared with the best one considered in the literature. Experimental results show that the new heuristic provides better solutions regarding both the solution quality and computational effort.

On the permutation behaviour of Dickson polynomials of the second kind

The known permutation behaviour of the Dickson polynomials of the second kind in characteristic 3 is expanded and simplified. (C) 2002 Elsevier Science (USA).

The compositional inverse of a class of permutation polynomials over a finite field

A new class of bilinear permutation polynomials was recently identified. In this note we determine the class of permutation polynomials which represents the functional inverse of the bilinear class.

ILS-ESP An efficient, simple, and parameter-free algorithm for solving the permutation flow-shop problem

From a managerial point of view, the more effcient, simple, and parameter-free (ESP) an algorithm is, the more likely it will be used in practice for solving real-life problems. Following this principle, an ESP algorithm for solving the Permutation Flowshop Sequencing Problem (PFSP) is proposed in this article. Using an Iterated Local Search (ILS) framework, the so-called ILS-ESP algorithm is able to compete in performance with other well-known ILS-based approaches, which are considered among the most effcient algorithms for the PFSP. However, while other similar approaches still employ several parameters that can affect their performance if not properly chosen, our algorithm does not require any particular fine-tuning process since it uses basic "common sense" rules for the local search, perturbation, and acceptance criterion stages of the ILS metaheuristic. Our approach defines a new operator for the ILS perturbation process, a new acceptance criterion based on extremely simple and transparent rules, and a biased randomization process of the initial solution to randomly generate different alternative initial solutions of similar quality -which is attained by applying a biased randomization to a classical PFSP heuristic. This diversification of the initial solution aims at avoiding poorly designed starting points and, thus, allows the methodology to take advantage of current trends in parallel and distributed computing. A set of extensive tests, based on literature benchmarks, has been carried out in order to validate our algorithm and compare it against other approaches. These tests show that our parameter-free algorithm is able to compete with state-of-the-art metaheuristics for the PFSP. Also, the experiments show that, when using parallel computing, it is possible to improve the top ILS-based metaheuristic by just incorporating to it our biased randomization process with a high-quality pseudo-random number generator.

A simple permutation test for clusteredness

Hierarchical clustering is a popular method for finding structure in multivariate data,resulting in a binary tree constructed on the particular objects of the study, usually samplingunits. The user faces the decision where to cut the binary tree in order to determine the numberof clusters to interpret and there are various ad hoc rules for arriving at a decision. A simplepermutation test is presented that diagnoses whether non-random levels of clustering are presentin the set of objects and, if so, indicates the specific level at which the tree can be cut. The test isvalidated against random matrices to verify the type I error probability and a power study isperformed on data sets with known clusteredness to study the type II error.

Testing Spatial Autocorrelation in Weighted Networks : the Modes Permutation Test

In a weighted spatial network, as specified by an exchange matrix, the variances of the spatial values are inversely proportional to the size of the regions. Spatial values are no more exchangeable under independence, thus weakening the rationale for ordinary permutation and bootstrap tests of spatial autocorrelation. We propose an alternative permutation test for spatial autocorrelation, based upon exchangeable spatial modes, constructed as linear orthogonal combinations of spatial values. The coefficients obtain as eigenvectors of the standardised exchange matrix appearing in spectral clustering, and generalise to the weighted case the concept of spatial filtering for connectivity matrices. Also, two proposals aimed at transforming an acessibility matrix into a exchange matrix with with a priori fixed margins are presented. Two examples (inter-regional migratory flows and binary adjacency networks) illustrate the formalism, rooted in the theory of spectral decomposition for reversible Markov chains.

Testing Spatial Autocorrelation in Weighted Networks : the Modes Permutation Test

In a weighted spatial network, as specified by an exchange matrix, the variances of the spatial values are inversely proportional to the size of the regions. Spatial values are no more exchangeable under independence, thus weakening the rationale for ordinary permutation and bootstrap tests of spatial autocorrelation. We propose an alternative permutation test for spatial autocorrelation, based upon exchangeable spatial modes, constructed as linear orthogonal combinations of spatial values. The coefficients obtain as eigenvectors of the standardised exchange matrix appearing in spectral clustering, and generalise to the weighted case the concept of spatial filtering for connectivity matrices. Also, two proposals aimed at transforming an acessibility matrix into a exchange matrix with with a priori fixed margins are presented. Two examples (inter-regional migratory flows and binary adjacency networks) illustrate the formalism, rooted in the theory of spectral decomposition for reversible Markov chains.

Genetic algorithm for sequencing in midex model non-permutation flowshops using constrained buffers

Este trabajo presenta un Algoritmo Genético (GA) del problema de secuenciar unidades en una línea de producción. Se tiene en cuenta la posibilidad de cambiar la secuencia de piezas mediante estaciones con acceso a un almacén intermedio o centralizado. El acceso al almacén además está restringido, debido al tamaño de las piezas.AbstractThis paper presents a Genetic Algorithm (GA) for the problem of sequencing in a mixed model non-permutation flowshop. Resequencingis permitted where stations have access to intermittent or centralized resequencing buffers. The access to a buffer is restricted by the number of available buffer places and the physical size of the products.

Modules d'endo-permutation

Dans la th´eorie des repr´esentations modulaires des groupes finis, les modules d?endo-permutation occupent une place importante. En e_et, c?est le r?ole jou´e par ces modules dans l?analyse de la structure de certains modules simples pour des groupes finis p-nilpotents, qui a amen´e E. Dade `a en introduire le concept, en 1978. Quelques ann´ees plus tard, L. Puig a d´emontr´e que la source de n?importe quel module simple pour un groupe fini p-r´esoluble quelconque est un module d?endo-permutation. Plus r´ecemment, on s?est rendu compte que ces modules interviennent aussi dans l?analyse locale des cat´egories d´eriv´ees et dans l?´etude des syst`emes de fusion. La situation que l?on consid`ere est la suivante. On se donne un nombre premier p, un p-groupe fini P, un corps alg´ebriquement clos k de caract´eristique p et on veut d´eterminer tous les kP-modules d?endo-permutation couverts ind´ecomposables de type fini, c?est-`a-dire tous les kP-modules ind´ecomposables de type fini, tels que leur alg`ebre d?endomorphismes est un kP-module de permutation ayant un facteur direct trivial. On d´efinit une relation d?´equivalence sur l?ensemble de ces kP-modules et le produit tensoriel des modules induit une structure de groupe ab´elien sur l?ensemble des classes d?´equivalence. On appelle ce groupe, le groupe de Dade de P. Ainsi, classifier les modules d?endo-permutation couverts revient `a d´eterminer le groupe de Dade de P. Le groupe de Dade d?un p-groupe fini arbitraire est encore inconnu, bien qu?E. Dade, en 1978, ´etait d´ej`a parvenu `a la classification dans le cas o`u P est ab´elien. La premi`ere partie de ce travail de th`ese est consacr´ee au probl`eme de la classification dans le cas g´en´eral et r´esoud la question dans le cas de deux familles de p-groupes finis, `a savoir celle des p-groupes m´etacycliques, pour un nombre premier p impair, et celle des 2-groupes extrasp´eciaux, de la forme D8 _ · · · _ D8. Ces deux choix ont ´et´e motiv´es par le fait que ces groupes sont "presque" ab´eliens. De plus, certains r´esultats sur la structure du groupe de Dade d?un p-groupe fini quelconque rendent le groupe de Dade des groupes de ces deux familles plus simple `a ´etudier. Dans un deuxi`eme temps, nous nous sommes int´eress´es `a deux occurrences de ces modules dans la th´eorie de la repr´esentation des groupes finis, c?est-`a-dire `a deux raisons qui motivent leur ´etude. Ainsi, nous avons r´ealis´e des modules d?endo-permutation comme sources de modules simples. En particulier, il s?av`ere que, dans le cas d?un nombre premier p impair, tout module d?endo-permutation ind´ecomposable dont la classe est un ´el´ement de torsion dans le groupe de Dade est la source d?un module simple. Finalement, nous avons d´etermin´e, parmi tous les modules d?endo-permutation connus actuellement, lesquels poss`edent une r´esolution de permutation endo-scind´ee. Nous sommes arriv´es `a la conclusion que les seuls modules d?endo-permutation qui n?ont pas de r´esolution de permutation endo-scind´ee sont les modules "exceptionnels" apparaissant pour un 2-groupe de quaternions g´en´eralis´es.<br/><br/>In modular representation theory, endo-permutation modules occupy an important position. Indeed, the role that these modules play, in the analysis of the structure of some particular simple modules for finite p-nilpotent groups, induced E. Dade, in 1978, to give them their current name. A few years later, L. Puig proved that the source of any simple module for any finite psolvable group is an endo-permutation module. More recently, the occurrence of endo-permutation modules has also been noticed in the local analysis of splendid equivalences between derived categories and in the study of fusion systems. We consider the following situation. Given a prime number p, a finite pgroup P and an algebraically closed field k of characteristic p, we are looking for all finitely generated indecomposable capped endo-permutation kP-modules. That is, all finitely generated indecomposable kP-modules such that their endomorphism algebra is a permutation kP-module having a trivial direct summand. Then, we define an equivalence relation on the set of all isomorphism classes of such modules, and it turns out that the tensor product (over k) induces a structure of abelian group on this set. We call this group the Dade group of P. Hence, classifying all indecomposable finitely generated capped endo-permutation kPmodules is equivalent to determining the Dade group of P. At present, the Dade group of an arbitrary finite p-group is still unknown. However, E. Dade computed the Dade group of all finite abelian p-groups, in 1978 already. The first part of this doctoral thesis is concerned with the problem of the classification in the general case and solve it in the case of two families of finite p-groups, namely the metacyclic p-groups, for an odd prime number p, and the extraspecial 2-groups of the shape D8 _· · ·_D8. These two choices have been motivated by the fact that these groups are not far from being abelian. Moreover, some general results concerning the Dade group of arbitrary finite p-groups suggest that the Dade group of the groups belonging to these two families is easier to study. In the second part of this thesis, we have been looking at two particular occurrences of these modules in representation theory of finite groups which motivate the interest of their classification. Thus, we realised endo-permutation modules as sources of simple modules. In particular, it turns out that, in case p is an odd prime, any indecomposable module whose class in the Dade group is a torsion element is the source of some simple module. Finally, we considered all the modules we know at present and determined which ones have an endo-split permutation resolution. We could then conclude that all but the "exceptionnal" modules occurring in the generalized quaternion case have an endo-split permutation resolution.<br/><br/>"Module d?endo-permutation" n?est pas le nom d?une maladie exotique contagieuse (du moins pas `a ma connaissance), comme vous pourriez peut-?etre l?imaginer si vous faites partie des personnes qui croient que le titre de docteur n?est destin´e qu?aux m´edecins. Dans ce cas, il se peut que le sujet dont il est question ici vous cause quelques naus´ees et r´eveille de douloureux souvenirs d?´ecole, car un module d?endo-permutation est un objet math´ematique, alg´ebrique, plus pr´ecis´ement. Ce concept a ´et´e introduit il y a un quart de si`ecle, de l?autre c?ot´e de l?Atlantique, et il s?est r´ev´el´e su_samment int´eressant pour qu?aujourd?hui il ait franchi bien des fronti`eres, celles de l?alg`ebre y compris. Mais de quoi s?agit-il ? Si vous entendez le terme "endo-permutation" probablement pour la premi`ere fois, ce n?est certainement pas le cas pour celui de "module". Cependant, sa d´efinition dans le pr´esent contexte ne co¨ýncide avec aucune de celles figurant dans les dictionnaires ordinaires. Les personnes qui ont d´ej`a entendu parler de Frobenius, Burnside, Schur, ou encore Brauer, pourront vous dire qu?un module est une repr´esentation. "De quoi ?" vous demanderezvous. "Un spectacle de marionnettes, peut-?etre ?" Bien s?ur que non ! Un module d?endo-permutation est une repr´esentation particuli`ere de certains groupes finis, o`u un groupe n?est pas un groupe de rock, comme vous pouvez vous en douter, mais d´esigne un objet math´ematique connu par tous les ´etudiants en sciences au terme de leur premi`ere ann´ee universitaire (en th´eorie, du moins). La "popularit´e" de la notion de groupe, fini ou non, est due au fait que les groupes sont fr´equemment utilis´es, aussi bien dans le domaine abstrait des math´ematiques, que dans le monde r´eel des physiciens, chimistes et autres biologistes (pour ne citer qu?eux). "Mais comment peut-on utiliser concr`etement ces objets invisibles ?" vous demanderez-vous alors. Et bien, justement, en les consid´erant par l?interm´ediaire de leurs repr´esentations, c?est-`a-dire en leur associant des matrices, de fa¸con plus ou moins naturelle. Or, comme il y a "beaucoup trop" de matrices pour un groupe donn´e, elles sont classifi´ees selon certaines de leurs propri´et´es, ce qui permet de les r´epertorier dans diverses familles (celle des modules d?endo-permutation, par exemple). Un groupe est ainsi rendu "concret", car les donn´ees matricielles sont manipulables par tous les scienti- fiques (et leurs ordinateurs), qui peuvent alors les utiliser dans leurs recherches, afin de contribuer au progr`es de la science. En toute franchise, c?est bien loin de ces soucis terre-`a-terre que ce travail de th`ese sur la classification des modules d?endo-permutation a ´et´e accompli. En fait, quitte `a choquer certaines ?ames sensibles, sa r´ealisation est surtout due au caract`ere ´epicure de son auteur, qui, avouons-le, en a ´et´e pleinement satisfait !

Arrêt du grand conseil qui juge que les brefs de pénitencerie de cour de Rome fulminés par les nonces de Sa Sainteté, quoique confirmés par les brefs de la daterie, n'ont point lieu en France pour le fore extérieur. En conséquence a déclaré la translation d'un hermite de Saint-Augustin dans l'ordre de Saint-Benoît nulle et abusive, et renvoyé ledit hermite dans le couvent de sa profession, à Paris, au faubourg Saint-Germain. Qui maintient un gradué régulier de l'ordre Cluny dans la possession du prieuré de Sainte-Gemme dont il était pourvu comme gradué. Et qui juge nulles tant la permutation faite en fraude des gradués que les collations faites au compermutant, contre les maximes du droit et les termes de l'indult du collateur

[Acte. 1694-09-20. Paris]

Permutation entropy based real-time chatter detection using audio signal in turning process

Machine tool chatter is an unfavorable phenomenon during metal cutting, which results in heavy vibration of cutting tool. With increase in depth of cut, the cutting regime changes from chatter-free cutting to one with chatter. In this paper, we propose the use of permutation entropy (PE), a conceptually simple and computationally fast measurement to detect the onset of chatter from the time series using sound signal recorded with a unidirectional microphone. PE can efficiently distinguish the regular and complex nature of any signal and extract information about the dynamics of the process by indicating sudden change in its value. Under situations where the data sets are huge and there is no time for preprocessing and fine-tuning, PE can effectively detect dynamical changes of the system. This makes PE an ideal choice for online detection of chatter, which is not possible with other conventional nonlinear methods. In the present study, the variation of PE under two cutting conditions is analyzed. Abrupt variation in the value of PE with increase in depth of cut indicates the onset of chatter vibrations. The results are verified using frequency spectra of the signals and the nonlinear measure, normalized coarse-grained information rate (NCIR).

Permutation Entropy Based Analysis of Complex Signals for Characterising Change in System Dynamics

Timely detection of sudden change in dynamics that adversely affect the performance of systems and quality of products has great scientific relevance. This work focuses on effective detection of dynamical changes of real time signals from mechanical as well as biological systems using a fast and robust technique of permutation entropy (PE). The results are used in detecting chatter onset in machine turning and identifying vocal disorders from speech signal.Permutation Entropy is a nonlinear complexity measure which can efficiently distinguish regular and complex nature of any signal and extract information about the change in dynamics of the process by indicating sudden change in its value. Here we propose the use of permutation entropy (PE), to detect the dynamical changes in two non linear processes, turning under mechanical system and speech under biological system.Effectiveness of PE in detecting the change in dynamics in turning process from the time series generated with samples of audio and current signals is studied. Experiments are carried out on a lathe machine for sudden increase in depth of cut and continuous increase in depth of cut on mild steel work pieces keeping the speed and feed rate constant. The results are applied to detect chatter onset in machining. These results are verified using frequency spectra of the signals and the non linear measure, normalized coarse-grained information rate (NCIR).PE analysis is carried out to investigate the variation in surface texture caused by chatter on the machined work piece. Statistical parameter from the optical grey level intensity histogram of laser speckle pattern recorded using a charge coupled device (CCD) camera is used to generate the time series required for PE analysis. Standard optical roughness parameter is used to confirm the results.Application of PE in identifying the vocal disorders is studied from speech signal recorded using microphone. Here analysis is carried out using speech signals of subjects with different pathological conditions and normal subjects, and the results are used for identifying vocal disorders. Standard linear technique of FFT is used to substantiate thc results.The results of PE analysis in all three cases clearly indicate that this complexity measure is sensitive to change in regularity of a signal and hence can suitably be used for detection of dynamical changes in real world systems. This work establishes the application of the simple, inexpensive and fast algorithm of PE for the benefit of advanced manufacturing process as well as clinical diagnosis in vocal disorders.

Notations and conventions in molecular spectroscopy: part 3. Permutation and permutation-inversion symmetry notation

The field of Molecular Spectroscopy was surveyed in order to determine a set of conventions and symbols which are in common use in the spectroscopic literature. This document, which is Part 3 in a series, deals with symmetry notation referring to groups that involve nuclear permutations and the inversion operation. Further parts will follow, dealing inter alia with vibration-rotation spectroscopy and electronic spectroscopy.