Sadi F.,CNRS Laboratory Informatics |
Soukhal A.,CNRS Laboratory Informatics
Discrete Optimization | Year: 2017
We study the scheduling of independent jobs where several agents compete to perform their jobs on common identical parallel machines: resource manager GA (global agent) wants to minimize a cost function associated with all jobs, while each agent k wants to have another cost function associated with its jobs not exceeding a given value Qk, k=1,...,K. The jobs have equal processing requirements. Monotonic regular objective functions depending on the completion times of jobs are considered. The global cost function of agent GA may correspond to the global performance of the workshop independently on the agents objective functions. With various combinations of the objective functions, new complexity results are proposed and polynomial algorithms are derived to find an optimal solution that minimizes the global objective function, subject to the constraints that the objective functions of the other agents do not exceed a given threshold. © 2017 Elsevier B.V.
Pessan C.,CNRS Laboratory Informatics |
Neron E.,CNRS Laboratory Informatics |
Haouari M.,Combinatorial Optimization Research Group ROI |
Haouari M.,Ozyegin University
European Journal of Industrial Engineering | Year: 2013
Efficient production resettings are necessary to achieve production flexibility. For this reason, it is of primary importance to reduce the setup time required to switch the production from one product type to another, and more generally to minimise the loss of production during these resetting phases. In this paper, we investigate the problem of scheduling operations within a production resetting that arises at the ball bearing factories of the SKF group. In the case of full serial production lines, improving the setup times amount to minimising the time spent prior to restarting production. We show that the problem of scheduling operations within a production resetting can be modelled as an unrelated parallel machine scheduling problem, and we propose several lower bounds. The first one is an extension of the improved energetic reasoning to the unrelated parallel machine problem. The second one is based on a preemptive relaxation that includes valid inequalities. We report the results of computational experiments that were carried out on both industrial and generated instances and that provide evidence of the efficacy of the proposed lower bounds. Copyright © 2013 Inderscience Enterprises Ltd.
Cordeau D.,CNRS Laboratory Informatics |
Paillot J.-M.,CNRS Laboratory Informatics
AEU - International Journal of Electronics and Communications | Year: 2010
In this paper, we describe an original method for determining the optimal operating point of the active part (transistor) of an LC oscillator leading to the minimum phase noise for given specifications in terms of power consumption, oscillation frequency and for given devices (i.e., transistor and resonator). The key point of the proposed method is based on the use of a proper LC oscillator architecture providing a fixed loaded quality factor for different operating points of the active part within the oscillator. The feedback network of this architecture is made of an LC resonator with coupling transformers. In these conditions, we show that it is possible to easily change the operating point of the amplifier, through the determination of the turns ratio of those transformers, and observe its effect on phase noise without modifying the loaded quality factor of the resonator. The optimal operating point for minimum phase noise is then extracted from nonlinear simulations. Once this optimal behavior of the active part is known and by associating the previous LC resonator, a design of an LC oscillator or VCO with an optimal phase noise becomes possible. The conclusions of the presented simulation results have been widely used to design and implement a fully integrated LC differential VCO on a 0.35 μ m BiCMOS SiGe process. © 2009 Elsevier GmbH. All rights reserved.
Bonhomme P.,CNRS Laboratory Informatics
Discrete Event Dynamic Systems: Theory and Applications | Year: 2013
Petri nets are a powerful formalism for the specification and verification of concurrent systems, such as sequential systems and manufacturing systems. To deal with real-time systems whose time issues become essential, different extensions of Petri nets with time have been proposed in the literature. In this paper, a new scheduling and control technique for real-time systems modeled by ordinary P-time Petri nets is proposed. Its goal is to provide a scheduling for a particular firing sequence, without any violation of timing constraints ensuring that no deadline is missed. It is based on the firing instant notion and it consists in determining an inequality system generated for a possible evolution (in terms of a feasible firing sequence for the untimed underlying Petri net) of the model. This system can be used to check reachability problems as well as evaluating the performances of the model considered and determining the associated control for a definite functioning mode and it introduces partial order on the execution of particular events. © 2012 Springer Science+Business Media, LLC.
Giacometti A.,CNRS Laboratory Informatics |
Soulet A.,CNRS Laboratory Informatics
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2016
Outlier detection consists in detecting anomalous observations from data. During the past decade, pattern-based outlier detection methods have proposed to mine all frequent patterns in order to compute the outlier factor of each transaction. This approach remains too expensive despite recent progress in pattern mining field. In this paper, we provide exact and approximate methods for calculating the frequent pattern outlier factor (FPOF) without extracting any pattern or by extracting a small sample. We propose an algorithm that returns the exact FPOF without mining any pattern. Surprisingly, it works in polynomial time on the size of the dataset. We also present an approximate method where the end-user controls the maximum error on the estimated FPOF. Experiments show the interest of both methods for very large datasets where exhaustive mining fails to provide the exact solution. The accuracy of our approximate method outperforms the baseline approach for a same budget in time or number of patterns. © Springer International Publishing Switzerland 2016.
Bonhomme P.,CNRS Laboratory Informatics
IEEE International Conference on Emerging Technologies and Factory Automation, ETFA | Year: 2013
This paper deals with a novel state observer synthesis method of real-time systems under partial observation. Indeed, the developed approach aims at estimating the marking of a P-time Petri net system based on the observation of the occurrence of particular transitions called observable transitions. As opposed to many existing approaches the application of the method does not require strong assumptions on the structure of the model considered. In addition, although the time factor is taken into consideration, the proposed technique is not hampered by the state space explosion problem as it relies on the underlying untimed structure of the P-time model studied - the building of the state class graph is not necessary. © 2013 IEEE.
Jlassi A.,CNRS Laboratory Informatics |
Martineau P.,CNRS Laboratory Informatics
CLOSER 2016 - Proceedings of the 6th International Conference on Cloud Computing and Services Science | Year: 2016
Virtual technologies have proven their capabilities to ensure good performance in the context of high performance computing (HPC). During the last decade, the big data tools have been emerging, they have their own needs in performance and infrastructure. Having a wide breadth of experience in the HPC domain, the experts can evaluate the infrastructures used to run big data tools easily. The outcome of this paper is the evaluation of two technologies of virtualization in the context of big data tools. We compare the performance and the energy consumption of two technologies of virtualization (Docker containers and VMware) and benchmark the software Hadoop (JoshBaer, 2015) using these environments. Firstly, the aim is the reduction of the Hadoop deployment cost using the cloud. Secondly, we discuss and analyze the assumptions learned from the HPC experiments and their applicability in the big data context. Thirdly, the Hadoop community finds an in-depth study of the resource consumption depending on the deployment environment. We come to the point that the use of the Docker container gives better performance in most experiments. Besides, the energy consumption varies according to the executed workload. Copyright © 2016 by SCITEPRESS - Science and Technology Publications, Lda. All rights reserved.
Ramel J.-Y.,CNRS Laboratory Informatics |
Sidere N.,CNRS Laboratory Informatics |
Rayar F.,CNRS Laboratory Informatics
Literary and Linguistic Computing | Year: 2013
This article describes the work performed in the Pattern Redundancy Analysis for Document Image Indexing and Transcription research project. The project focused on layout analysis, text/graphics separation, optical character recognition (OCR), and text transcription processes dedicated to old and precious books. The originality of this work relies on the analysis and exploitation of pattern redundancy in documents to enable the efficient indexing and quick transcription of books and the identification of typographic materials. For these purposes, we have developed two software packages. The first, AGORA, performs page layout analysis, text/graphics separation, and pattern (letterform) extraction simultaneously. These patterns are then processed to group similar patterns together in single clusters so that different letterforms of a book can be extracted and analysed to compute redundancy rates. This process allows a significant reduction of the number of letterforms to be recognized. Once the clustering of letterforms is done, a user may assign a label to each cluster using the second software, RETRO. Labels are then automatically assigned to each corresponding character to perform the text transcription of the whole book. Thus, if 90% of the letterforms are detected as redundant, only one character out of ten must be labelled by the user to transcribe the book. Moreover, this transcription method allows us to deal easily with the special characters that appear frequently in old books. It is also possible to use our clustering approach to extract and create new font packages from specific printing material (e.g. from rare books printed with particular types or woodblocks). These new font packages could be incorporated into the training step of optical fonts recognition methods to improve the recognition results of OCRs on rare or specific books. The identification of typographic materials could also be useful for the study of both the aesthetic (such as how the thickness and shape of printing types evolved from the 15th to the mid-16th century) and economic aspects of printing historically. Until the second half of the 16th century, for instance, printing types circulated among workshops, and printers frequently sold or lent types to their fellows. © The Author 2013. Published by Oxford University Press on behalf of ALLC. All rights reserved.
Bonhomme P.,CNRS Laboratory Informatics
CEUR Workshop Proceedings | Year: 2015
This paper focuses on the fault diagnosis problem of systems modeled with P-time labeled Petri nets with partial information. Indeed, the set of transitions is partitioned into those labeled with the empty string o called silent (as their firin cannot be detected) including the faulty transitions and the observable ones. The proposed approach is based on the synthesis of a function called diagnoser allowing to determine the diagnosis state of the system based on the current observation. The novelty of the developed approach resides in the fact that, although the time factor is considered as intervals, the diagnoser is computed thanks to the underlying untimed Petri net structure of the P-time labeled model considered. Furthermore, the method relies on the schedulability analysis of particular firin sequences exhibited by the analysis of the obtained diagnoser and does not require the building of the state class graph.
Bonhomme P.,CNRS Laboratory Informatics
International Journal of Advanced Manufacturing Technology | Year: 2013
In this paper, a novel schedulability analysis technique of real-time systems is presented. The developed approach is based on the consideration of the reachability graph of the (untimed) underlying Petri net of the studied model. The schedulability analysis is then conducted in two steps. Once a feasible firing sequence (called occurrence sequence) is highlighted, this sequence is then described under an algebraic form of type Ax ≤ b. The particular features of matrix A lead to a bimonotone linear inequality system. A bimonotone linear inequality is a linear inequality with at most two nonzero coefficients that are of opposite signs (if both different from zero). Thus, deciding whether a firing sequence is schedulable or not takes the form of the solution of a single-source shortest path problem which can be polynomially solved via the Bellman-Ford algorithm. © 2012 Springer-Verlag London.