Dissertations / Theses on the topic 'Production scheduling Multimedia systems. Algorithms'

The primary purpose of this work is to propose a new scheduling approach of multimedia data streams in real-time communication and also to study and analyze the various existing scheduling approaches.

Process planning and scheduling are two important manufacturing planning functions which are traditionally performed separately and sequentially. Usually, the process plan has to be prepared first before scheduling can be performed. However, due to the complexity of manufacturing systems and the uncertainties and dynamical changes encountered in practical production, process plans and schedules may easily become inefficient or even infeasible. The concept of integrated process planning and scheduling (IPPS) has been proposed to improve the efficiency, effectiveness as well as flexibility of the respective process plan and schedule. By combining both functions together, the process plan for producing a part could be dynamically arranged in accordance with the availability of manufacturing resources and current status of the system, and its operations’ schedule could be determined concurrently. Therefore, IPPS could provide an essential solution to the dynamic process planning and scheduling problem in the practical manufacturing environment. Nevertheless, process planning and scheduling are both complex functions that depend on many factors and flexibilities in the manufacturing system, IPPS is therefore a highly complex NP-hard problem. Ant colony optimization (ACO) is a widely applied meta-heuristics, which has been proved capable of generating feasible solutions for IPPS problem in previous research. However, due to the nature of the ACO algorithm, the performance is not that favourable compared with other heuristics. This thesis presents an enhanced ACO approach for IPPS. The weaknesses and limitations of standard ACO algorithm are identified and corresponding modifications are proposed to deal with the drawbacks and improve the performance of the algorithm. The mechanism is implemented on a specifically designed multi-agent system (MAS) framework in which ants are assigned as software agents to generate solutions. First of all, the manufacturing processes of the parts are graphically formulated as a disjunctive AND/OR graph. In applying the ACO algorithm, ants are deployed to find a path on the disjunctive graph. Such an ant route indicates a corresponding solution with associated operations scheduled by the sequence of ant visit. The ACO in this thesis is enhanced with the novel node selection heuristic and pheromone update strategy. With the node selection heuristic, pheromone is deposited on the nodes as well as edges on the ant path. This is contrast to the conventional ACO algorithm that pheromone is only deposited on edges. In addition, a more reasonable strategy based on “earliest completion time” of operations are used to determine the heuristic desirability of ants, instead of the “greedy” strategy used in standard ACO, which is based on the “shortest processing time”. The approach is evaluated by a comprehensive set of problems with a full set of flexibilities, while multiple performance measurements are considered, including makespan, mean flow time, average machine utilization and CPU time, among which makespan is the major criterion. The results are compared with other approaches and encouraging improvements on solution quality could be observed.
published_or_final_version
Industrial and Manufacturing Systems Engineering
Master
Master of Philosophy

Les travaux de cette thèse sont articulés autour du problème d’ordonnancement de tâches dans un type d’atelier de structure complexe peu étudié dans la littérature. Cet atelier est de composition hybride : chaque étage de l’atelier a une ou plusieurs machines. Les principales contraintes considérées sont le traitement par lots et la minimisation du retard total. Les méthodes de résolution de ce problème sont intégrées dans les systèmes d’aide à la décision du programme de recherche du Groupe SouffletEtant donné la structure complexe du type d’atelier considéré, nous avons décomposé ce dernier afin d’étudier plus particulièrement le problème d’ordonnancement sur machines parallèles identiques. Différentes méthodes de résolution sont testées. Les résultats sont analysés afin de proposer une classification d’instances et de méthodes de résolution. Les problèmes étudiés sont résolus de manière exacte et approchée. Différentes méthodes ont été testées : des recherches itératives, des algorithmes tabous, des méthodes évolutionnaires. Les conclusions de la résolution du problème d’ordonnancement des machines parallèles sont utilisées pour construire des méthodes à deux niveaux pour le problème complexe d’ordonnancement. Les résultats montrent que les algorithmes trouvent des solutions de bonne qualité pour le problème traité. De la même manière, de problématiques industrielles similaires sont traitées, dans l’objectif d’optimiser le fonctionnement du centre de recherche
This thesis considers a complex workshop scheduling problem, which is rarely studied to our knowledge. This workshop has a hybrid composition : one or several machines are available at each stage. Main considered constraints are batch processing and total tardiness minimization. Solution methods are embedded on the information system of research program of Soufflet Group. Given the complex structure of the workshop, it has been split in order to study the parallel machines scheduling problem individually. Different solution methods are developed. Obtained results are used to build a classification of instances and solution methods. To solve described problems, exact and approach solution methods are proposed. We have adapted iterated search, tabu search, genetic algorithms, … Findings from solving parallel machines scheduling problem are employed to develop a two levels solution method for the described flow shop problem. Results show the performance of developed algorithms to find good quality solutions for described scheduling problem. Similarly, industrial problems are considered, in order to optimize operational behavior of research center

Cette thèse porte sur la résolution multi-objectif du problème d’ordonnancement de projet avec contraintes de ressources. Après avoir dressé un état de l’art sur le problème, nous le résolvons dans un premier temps avec les approches exactes : la méthode à deux phases et la méthode de partitionnement parallèle. Face à un problème NP-difficile, les méthodes exactes ne permettent de résoudre que des instances de petites tailles. Par conséquent, les méthodes approchées sont mises en œuvre pour traiter les problèmes de plus grandes tailles. Les algorithmes génétiques sont d’abord adoptés pour résoudre notre problème. Au-delà des schémas de base, nous proposons d’améliorer les solutions par plusieurs hybridations. Une recherche locale avec la méthode de Mapping est appliquée pour une meilleure exploration de l’espace de recherche. Nous considérons ensuite un cas spécial où les décideurs souhaitent réduire le nombre de solutions afin de faciliter leur travail. Nous avons donc réalisé les pré-sélections vis-à-vis d’un ensemble de solutions de grande taille. Pour ce faire, plusieurs alternatives de dominance de Pareto sont intégrées. Ces règles de dominances sont implémentées dans les schémas des algorithmes génétiques classiques et hybridés avec des recherches locales. Les résultats montrent que les hybridations considérées permettent d’améliorer significativement les méthodes de base. Nos recherches dans le futur proche s’appuient sur la résolution des problèmes plus complexes et en relation avec les cas industriels au plus proches de la réalité
This thesis deals with the multi-objective Resource Constraint Project Scheduling Problem (RCPSP). After a specific literature review, we solve the problem with exact approaches in the first place: the Two Phases Method and the Parallel Partitioning Method. Due to the NP-hardness of the problem, the exact methods are only able to solve small instances. For this reason, we apply the approximated methods to deal with larger problems. The genetic algorithms are firstly adopted to solve large-scaled instances. Moreover, we propose to improve the basic scheme with several hybridizations. A local search with Mapping Method is applied for a better exploration of the solution space. Next, we consider a special case where the decision-makers wish to reduce the number of solutions. Thus, in this part of the thesis, we try to select the most interesting solutions among the whole non-dominated front. For this purpose, several dominance relationships are considered as alternatives of the Pareto dominance. These dominance rules are implemented in the basic genetic algorithm schemes, as well as those with local search. The results show that the considered hybridizations enhance highly the basic method results. Our future research will highlight more complex multi-objective RCPSP problems and the industrial application

Les travaux présentés dans ce document portent sur des problèmes d'optimisation dans le domaine de la logistique interne des entrepôts. Le domaine est soumis à une forte concurrence et est en plein essor, poussé par les besoins croissants du marché et favorisé par l'automatisation. L'entreprise SAVOYE construit des équipements et propose sa propre solution GTP (Goods-To-Person) pour la préparation de commandes. La solution utilise un système de stockage automatisé appelé X-Picking Tray System (X-PTS) et achemine les charges automatiquement à des postes de travail via des carrousels pour effectuer des opérations séquencées. C'est un système de systèmes particulièrement complexe qui offre de nombreuses applications aux techniques de la recherche opérationnelle. Tout cela définit le périmètre applicatif et théorique des travaux menés dans cette thèse. Nous avons d'abord traité un problème d'ordonnancement de type Job Shop avec des contraintes de précédences. Le contexte particulier du problème a permis de le résoudre en un temps polynomial avec un algorithme exact. Celui-ci a permis de calculer les dates d'injection des charges provenant des différents flux de sortie du stockage pour s'agréger sur un carrousel, dans un ordre donné. Ainsi, la gestion inter-allées du stockage PTS a été améliorée et le débit du flux de charges maximisé, depuis le stockage jusqu'à un poste. Nous avons ensuite étudié des algorithmes de tri tels que le tri par base et développé un algorithme de tri en ligne, utilisé pour piloter des systèmes autonomes de tri appelés Buffers Séquenceurs (BS). Placés en amont de chaque poste de travail dans la solution GTP, les BS permettent de délocaliser la fonction de tri en aval du stockage, augmentant de facto le débit des flux de sortie. Enfin, nous avons considéré un problème de séquencement consistant à trouver une extension linéaire d'un ordre partiel minimisant une distance avec un ordre donné. Nous proposons de le résoudre par une approche de programmation linéaire en nombres entiers, par la construction de programmes dynamiques et par des heuristiques de type glouton. Une heuristique efficace a été développée en se basant sur des appels itératifs d'un des programmes dynamiques, permettant d'atteindre une solution proche ou égale à l'optimum en un temps très court. L'application de ce problème aux flux de sortie non ordonnés du stockage X-PTS permet de réaliser un pré-tri au niveau des carrousels. Les diverses solutions développées ont été validées par simulation et certaines ont été brevetées et/ou déjà été mises en application dans des entrepôts
The work presented in this PhD thesis deals with optimization problems in the context of internal warehouse logistics. The field is subject to strong competition and extensive growth, driven by the growing needs of the market and favored by automation. SAVOYE builds warehouse storage handling equipment and offers its own GTP (Goods-To-Person) solution for order picking. The solution uses an Automated Storage and Retrieval System (ASRS) called X-Picking Tray System (X-PTS) and automatically routes loads to workstations via carousels to perform sequenced operations. It is a highly complex system of systems with many applications for operational research techniques. All this defines the applicative and theoretical scope of the work carried out in this thesis. In this thesis, we have first dealt with a specific scheduling Job Shop problem with precedence constraints. The particular context of this problem allowed us to solve it in polynomial time with exact algorithms. These algorithms made it possible to calculate the injection schedule of the loads coming from the different storage output streams to aggregate on a carousel in a given order. Thus, the inter-aisle management of the X-PTS storage was improved and the throughput of the load flow was maximized, from the storage to a station. In the sequel of this work, the radix sort LSD (Least Significant Digit) algorithm was studied and a dedicated online sorting algorithm was developed. The second one is used to drive autonomous sorting systems called Buffers Sequencers (BS), which are placed upstream of each workstation in the GTP solution. Finally, a sequencing problem was considered, consisting of finding a linear extension of a partial order minimizing a distance with a given order. An integer linear programming approach, different variants of dynamic programming and greedy algorithms were proposed to solve it. An efficient heuristic was developed based on iterative calls of dynamic programming routines, allowing to reach a solution close or equal to the optimum in a very short time. The application of this problem to the unordered output streams of X-PTS storage allows pre-sorting at the carousel level. The various solutions developed have been validated by simulation and some have been patented and/or already implemented in warehouses