Добірка наукової літератури з теми "Dynamic Scheduling Technique"

Tracking and Data Relay Satellite System (TDRSS) is a space-based telemetry, tracking, and command system, which represents a research field of the international communication. The issue of the dynamic relay satellite scheduling, which focuses on assigning time resource to user tasks, has been an important concern in the TDRSS system. In this paper, the focus of study is on the dynamic relay satellite scheduling, whose detailed process consists of two steps: the initial relay satellite scheduling and the selection of dynamic scheduling schemes. To solve the dynamic scheduling problem, a new scheduling algorithm ABC-TOPSIS is proposed, which combines artificial bee colony (ABC) and technique for order preference by similarity to ideal solution (TOPSIS). The artificial bee colony algorithm is performed to solve the initial relay satellite scheduling. In addition, the technique for order preference by similarity to ideal solution is adopted for the selection of dynamic scheduling schemes. Plenty of simulation results are presented. The simulation results demonstrate that the proposed method provides better performance in solving the dynamic relay satellite scheduling problem in the TDRSS system.

Minimizing time cost in time-shared operating system is the main aim of the researchers interested in CPU scheduling. CPU scheduling is the basic job within any operating system. Scheduling criteria (e.g., waiting time, turnaround time and number of context switches (NCS)) are used to compare CPU scheduling algorithms. Round robin (RR) is the most common preemptive scheduling policy used in time-shared operating systems. In this paper, a modified version of the RR algorithm is introduced to combine the advantageous of favor short process and low scheduling overhead of RR for the sake of minimizing average waiting time, turnaround time and NCS. The proposed work starts by clustering the processes into clusters where each cluster contains processes that are similar in attributes (e.g., CPU service period, weights and number of allocations to CPU). Every process in a cluster is assigned the same time slice depending on the weight of its cluster and its CPU service period. The authors performed comparative study of the proposed approach and popular scheduling algorithms on nine groups of processes vary in their attributes. The evaluation was measured in terms of waiting time, turnaround time, and NCS. The experiments showed that the proposed approach gives better results.

In resource-constrained project scheduling (RCPS) problems, ongoing tasks are restricted to utilizing a fixed number of resources. This paper investigates a dynamic version of the RCPS problem where the number of tasks varies in time. Our previous work investigated a technique called mapping of task IDs for centroid-based approach with random immigrants (McBAR) that was used to solve the dynamic problem. However, the solution-searching ability of McBAR was investigated over only a few instances of the dynamic problem. As a consequence, only a small number of characteristics of McBAR, under the dynamics of the RCPS problem, were found. Further, only a few techniques were compared to McBAR with respect to its solution-searching ability for solving the dynamic problem. In this paper, (a) the significance of the subalgorithms of McBAR is investigated by comparing McBAR to several other techniques; and (b) the scope of investigation in the previous work is extended. In particular, McBAR is compared to a technique called, Estimation Distribution Algorithm (EDA). As with McBAR, EDA is applied to solve the dynamic problem, an application that is unique in the literature.

Scientific workflows have been employed to automate large scale scientific experiments by leveraging computational power provided on-demand by cloud computing platforms. Among these workflows, a parallel loop workflow is used for studying the effects of different input values of a scientific experiment. Because of its independent loop characteristic, a parallel loop workflow can be dynamically executed as parallel workflow instances to accelerate the execution. Such execution negates workflow traversal used in existing works to calculate execution time and cost during scheduling in order to maintain time and cost constraints. In this paper, we propose a novel scheduling technique that is able to handle dynamic parallel loop workflow execution through a new method for evaluating execution progress together with a workflow instance arrival control and a cloud resource adjustment mechanism. The proposed technique, which aims at maintaining a workflow deadline while reducing cost, is tested using 3 existing task scheduling heuristics as its task mapping strategies. The simulation results show that the proposed technique is practical and performs better when the time constraint is more relaxed. It also prefers task scheduling heuristics that allow for a more accurate progress evaluation.

In massively parallel systems, the performance gains are often significantly diminished by the inherent communication overhead. This overhead is caused by the required message passing resulting from the task allocation scheme. In this paper, techniques to reduce this communication overhead by both scheduling the communication and determining the routing that the messages should take within a tightly-coupled processor network are presented. Using the recently developed Collision Graph model, static scheduling algorithms are derived which work at compile-time to determine the ordering and routing of the individual message transmissions. Since a priori knowledge about the network traffic required by static scheduling may not be available or accurate, this work also considers dynamic scheduling. A novel hybrid technique is presented which operates in a dynamic environment yet uses known information obtained by analyzing the communication patterns. Experiments performed show significant improvement over baseline techniques.

Recent years have witnessed a paradigm shift from centralized cloud computing to decentralized edge computing. As a key enabler technique in edge computing, computation offloading migrates computation-intensive tasks from resource-limited devices to nearby devices, optimizing service latency and energy consumption. In this paper, we investigate the problem of offloading task graphs in edge computing scenarios. Previous work based on list-scheduling heuristics is likely to suffer from severe processor time wastage due to intricate task dependencies and data transfer requirements. To this end, we propose a novel offloading algorithm, referred to as Iterative Dynamic Critical Path Scheduling (IDCP). IDCP minimizes the makespan by iteratively migrating tasks to keep shortening the dynamic critical path. Through IDCP, what is managed are essentially the sequences among tasks, including task dependencies and scheduled sequences on processors. Since we only schedule sequences here, the actual start time of each task is not fixed during the scheduling process, which effectively helps to avoid unfavorable schedules. Such flexibilities also offer us much space for continuous scheduling optimizations. Our experimental results show that our algorithm significantly outperforms existing list-scheduling heuristics in various scenarios, which demonstrates the effectiveness and competitiveness of our algorithm.

Computational Grid has been employed for solving complex and large computation-intensive problems with the help of geographically distributed, heterogeneous and dynamic resources. Job scheduling is a vital and challenging function of a computational Grid system. Job scheduler has to deal with many heterogeneous computational resources and to take decisions concerning the dynamic, efficient and effective execution of jobs. Optimization of the Grid performance is directly related with the efficiency of scheduling algorithm. To evaluate the efficiency of a scheduling algorithm, different parameters can be used, the most important of which are makespan and flowtime. In this paper, a very recent evolutionary heuristic algorithm known as Wind Driven Optimization (WDO) is used for efficiently allocating jobs to resources in a computational Grid system so that makespan and flowtime are minimized. In order to measure the efficacy of WDO, Genetic Algorithm (GA) and Particle Swarm Optimization (PSO) are considered for comparison. This study proves that WDO produces best results.

We study a dynamic scheduling problem that has the feature of due dates and time windows. This problem arises in chemotherapy scheduling where patients from different types have specific target dates along with time windows for appointment. We consider cancellation of appointments. The problem is modeled as a Markov Decision Process (MDP) and approximately solved using a direct-search based approximate dynamic programming (ADP) tehnique. We compare the performance of the ADP technique against the myopic policy under diverse scenarios. Our computational results reveal that the ADP technique outperforms the myopic policy on majority of problem sets we generated.

Parallel processing is a technique of executing the multiple tasksconcurrently on different processors. Parallel processing is usedto solve the complex problems that require vast amount ofprocessing time. Task scheduling is one of the major problemsof parallel processing. The objective of this study is to analyzethe performance of static (HLFET) and dynamic (DLS) BNPparallel scheduling algorithm for allocating the tasks ofdistributed database over number of processors. In the wholestudy the focus will be given on measuring the impact ofnumber of processors on different metrics of performance likemakespan, speed up and processor utilization by using HLFETand DLS BNP task scheduling algorithms.

Thesis (M.S.)--West Virginia University, 1999.
Title from document title page. Document formatted into pages; contains viii, 82 p. : ill. (some col.) Vita. Includes abstract. Includes bibliographical references (p. 77-79).

The topic of smart grids has become one of the most important research arenas recently. Spurred by the urges to reduce our dependence on fossil fuels for several environmental and economic reasons, researchers have written many treatises on this topic. M. He, S. Murugesan and J. Zhang suggested in their article, "Multiple Timescale Dispatch and Scheduling for Stochastic Reliability in Smart Grids with Wind Generation Integration", a new pricing and scheduling model to exploit the wind (or any other stochastic) energy to the fullest extent. I studied this model, and from my experiments, I found a defect. In this thesis, I try to evaluate this model. Firstly, I present it with detailed proofs of the main results. Secondly, I explain the experiments and simulations I did. Then, I analyze the results to show the defect I discovered. Finally, I suggest a solution for that defect, and I point out the advantages of that model.

The continuous shrink of transistor sizes has allowed more complex and powerful devices to be implemented in the same area, which provides new capabilities and functionalities. However, this complexity increase comes with a considerable rise in power consumption. This situation is critical in portable devices where the energy budget is limited and, hence, battery lifetime defines the usefulness of the system. Therefore, power consumption has become a major concern in the design of real-time multicore embedded systems. This dissertation proposes several techniques aimed to save energy without sacrifying real-time schedulability in this type of systems. The proposed techniques deal with different main components of the system. In particular, the techniques affect the task partitioner and the scheduler, as well as the memory controller. Some of the techniques are especially tailored for multicores with shared Dynamic Voltage and Frequency Scaling (DVFS) domains. Workload balancing among cores in a given domain has a strong impact on power consumption, since all the cores sharing a DVFS domain must run at the speed required by the most loaded core. In this thesis, a novel workload partitioning algorithm is proposed, namely Loadbounded Resource Balancing (LRB). The proposal allocates tasks to cores to balance a given resource (processor or memory) consumption among cores, improving real-time schedulability by increasing overlapping between processor and memory. However, distributing tasks in this way regardless the individual core utilizations could lead to unfair load distributions. That is, one of the cores could become much loaded than the others. To avoid this scenario, when a given utilization threshold is exceeded, tasks are assigned to the least loaded core. Unfortunately, workload partitioning alone is sometimes not able to achieve a good workload balance among cores. Therefore, this work also explores novel task migration approaches. Two task migration heuristics are proposed. The first heuristic, referred to as Single Option Migration (SOM ), attempts to perform only one migration when the workload changes to improve utilization balance. Three variants of the SOM algorithm have been devised, depending on the point of time the migration attempt is performed: when a task arrives to the system (SOMin), when a task leaves the system (SOMout), and in both cases (SOMin−out). The second heuristic, referred to as Multiple Option Migration (MOM ) explores an additional alternative workload partitioning before performing the migration attempt. Regarding the memory controller, memory controller scheduling policies are devised. Conventional policies used in Non Real-Time (NRT) systems are not appropriate for systems providing support for both Hard Real-Time (HRT) and Soft Real-Time (SRT) tasks. Those policies can introduce variability in the latencies of the memory requests and, hence, cause an HRT deadline miss that could lead to a critical failure of the real-time system. To deal with this drawback, a simple policy, referred to as HR- first, which prioritizes requests of HRT tasks, is proposed. In addition, a more advanced approach, namely ATR-first, is presented. ATR-first prioritizes only those requests of HRT tasks that are necessary to ensure real-time schedulability, improving the Quality of Service (QoS) of SRT tasks. Finally, this thesis also tackles dynamic execution time estimation. The accuracy of this estimation is important to avoid deadline misses of HRT tasks but also to increase QoS in SRT systems. Besides, it can also help to improve the schedulability of the systems and reduce power consumption. The Processor-Memory (Proc-Mem) model, that dynamically predicts the execution time of real-time application for each frequency level, is proposed. This model measures at the first hyperperiod, making use of Performance Monitoring Counters (PMCs) at run-time, the portion of time that each core is performing computation (CPU ), waiting for memory (MEM ), or both (OVERLAP). This information will be used to estimate the execution time at any other working frequency
March Cabrelles, JL. (2014). Dynamic Power-Aware Techniques for Real-Time Multicore Embedded Systems [Tesis doctoral]. Editorial Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/48464
TESIS

La demande mondiale en ressource minérale en général et celle du phosphate en particulier connait une forte croissance depuis plusieurs années. C’est dans ce contexte tendu que chaque industriel cherche à être pionnier et à réduire ses coûts afin d’assurer sa pérennité tout en étant soumis aux contraintes légales dans une perspective de développement responsable. Face à des enjeux comparables, plusieurs industries manufacturières se sont orientées avec succès depuis plusieurs décennies vers l’approche japonaise du Lean Management. C’est pour cette raison que nous avons réfléchi à proposer à travers ce projet de recherche une méthodologie pour le Lean Mining Responsable visant à améliorer l’efficacité et l’efficience de l’industrie minière. L’ensemble des méthodes, briques logicielles et concepts proposés dans cette thèse ont été construit à partir d’un retour d’expérience réalisé sur le système minier d’extraction du phosphate de l’axe centre de l’OCP SA. Nos travaux, réalisés sous la forme d’une recherche action, se caractérisent par des apports à 3 niveaux :Apports méthodologiques ; nous proposons la Méthodologie ASCI-LM pour évaluer l’impact sur l’organisation industrielle liés à la mise en place d’outils et de méthodes en contexte minier. Cette approche constitue un guide méthodologique permettant une recherche action dans le contexte de l’industrie minière. Ce guide méthodologique explique comment formaliser les modèles de connaissance (cartographie des flux) et comment imbriquer les modèles informatiques permettant d’évaluer informatiquement des scenarios organisationnels liés à des problèmes de coordination des activités en contexte minier.Briques logicielles pour l’aide à la décision ; l’interdépendance spatio-temporelle qui caractérise la chaîne minière, rend difficile la prédiction de l’impact de la décision prise. Ce point est un facteur-clé qui explique la démotivation de l’industrie minière à l’égard de la mise en œuvre du Lean Mining. Un système d’aide à la prise de décision pour l’industrie minière aura comme objectif de pouvoir reproduire la réalité et par la suite de tester l’impact de différentes décisions en prenant compte de : l’état du gisement, le programme de maintenance, la disponibilité des machines, les demandes à satisfaire… Les décisions prises dans le processus extractif auront comme impact sur : l’évolution des stocks de minerai, l’occupation des machines mobilisées, la satisfaction de la demande… Nous proposons deux briques logicielles dont la première porte sur la planification minière pour assurer un pilotage intégré de la mine et aider à la prise de décision dans un délai court. La deuxième brique logicielle que nous avons imaginée évalue / optimise les méthodes d’organisations industrielles de la mine lors de la constitution des « mélanges » de minerai ; le mélange de minerai constitue l’output commercialisable du système minier et qui est envoyé aux clients internes ou externes de la supply chain minière. Nouvelles méthodes d’organisation industrielle ; Nous avons proposé une méthode de constitution des mélanges de minerai qui change complètement celle utilisée actuellement. Cette dernière est basée sur une logique de nomenclature figée alors que nous proposons des nomenclatures dynamiques que nous avons appelés « blending dynamique ». Ces nomenclatures dynamiques visent à définir les mélanges optimaux qui varient au fil du temps en fonction des minerais extrait du chantier et de leur composition chimique. Malgré les réticences qui pouvaient y avoir pour adopter cette approche (ce qui est logique dans une organisation « historique »), les mineurs ont montré un grand intérêt vis-à-vis de l’approche qui a été validée sur le terrain et qui est même généralisable sur d’autres contextes
Global demand for mineral resources in general, and phosphate in particular, has been growing strongly for several years. In this increased competitive environment, every industry seeks to be pioneering and to reduce its costs to ensure its sustainability while complying with new responsible development regulations. Faced with this kind of challenges, a number of manufacturing industries have turned to the Japanese Lean Management approach. With this in mind, we designed our research project to develop a Lean Sustainable Mining methodology aimed at improving the mining industry’s efficiency and effectiveness at the OCP-SA center axis phosphate mine. We first conducted a detailed review of the Lean Mining (LM) literature to assess how well such an approach had already been implemented, which points are directly relevant to the mine and which are not. We also reviewed the implementation methodologies and assessed how effectively they were used. This analysis highlighted multiple shortcomings including in relation to the methodological approaches, the software bricks for decision support systems, the industrial organization methods and adequate factoring in of all energy-related aspects.We first recommend applying the ASCI (Analyze, Specification, Conception, Implementation) methodology to LM in order first to identify all the steps upstream of development of the relevant knowledge model and then the associated action model. This phase was developed based on a thorough analysis of mine soil characteristics in order to build a robust knowledge base. This methodology was then applied to the Ben Guerir mine. We believe that this methodological approach will be found useful by other industries in their effort to switch to LM.Our next step was to construct a model based on discrete event simulation for short-term decision support of mine extraction planning. This model closely matches current extractive process operations (drilling, blasting, etc.) and takes into account all the constraints whether they be in relation to the field (geology, blocks, state of the initial system, distances, ...) or to the equipment (capacity differences, technical downtime, ...). Other considerations that we factored in include the decisions taken upstream of the chain (priority source layers, maintenance program, orders, among others). The model yields the following output: deposits blocks to be extracted in order to meet the demand defined over the planning horizon, the equipment Gantt to define the route to be taken by each piece of equipment and the cumulative feed curves for extracted source layers. The purpose is to extract material required by the downstream blending process, while avoiding any non-value added activities, and to improve overall chain performance.The phosphate industry needs to define the blends used to produce the ore qualities to be shipped to domestic and international customers. We have proposed a new method for optimal definition of these blends designed to replace fixed bills of materials by dynamic ones that change over time. Our "dynamic blending" model serves to define, based on available source layer stocks i) the feedings to be conveyed from the deposit to the stock and ii) the optimal quantities to be extracted from each layer while meeting the customer’s quality specifications charter. The purpose of this approach is to produce the right quality, preserve the phosphate-rich layers for the future, streamline stocks and ensure a connection between the pushed upstream flow (deposit) and the pulled downstream flow (definition of blends)
إن الطلب العالمي على الموارد المعدنية بشكل عام، والفوسفاط على وجه الخصوص، يزداد بسرعة منذ عدة سنوات. وفي هذا السياق الذي يعنى بمنافسة قوية بين الأطر الفعالة، يسعى كل مصنع الى أن يكون الرائد في مجاله، وأن يقلل من تكاليف الإنتاج من أجل ضمان متانته في إطار خضوعه لقيود قانونية تحت منظور التنمية المسؤولة. في إطار مواجهة قضايا مماثلة، انتقلت العديد من الصناعات التحويلية، بنجاح لعدة عقود، إلى تطبيق النهج الياباني Lean Management. ولهذا السبب، فكرنا من خلال مشروع البحث هذا في اقتراح منهجية من أجل Lean Mining مسؤول، هدفه تحسين كفاءة وفعالية صناعة المعادن. جميع الطرق والمنهجيات ومفاهيم البرمجيات المقترحة في هذه الأطروحة يتم بناؤها على أساس تجارب منجزة على نظام الصناعة المعدنية لاستخراج الفوسفاط للمحور المركزي لـ OCP-SA. يتميز عملنا، الذي تم تنفيذه على شكل بحث-عملي، بمساهمات على 3 مستويات:مساهمات منهجية: نقترح منهجية ASCI-LM لتقييم تأثير تنفيذ أساليب على المنظمة الصناعية المتعلقة بالصناعة المعدنية. هذا النهج هو عبارة عن دليل منهجي للبحث-العملي في هذا المجال، الذي يشرح كيفية إضفاء الطابع الرسمي على نماذج المعرفة (رسم خرائط التدفقات) وكيفية تضمين النماذج المعلوماتية التي تجعل من الممكن تقييم سيناريوهات تنظيمية تتعلق بمشاكل التنسيق بين الأنشطة في سياق الصناعة المعدنية.أسس البرمجيات لدعم اتخاذ القرار: إن الترابط الزمكاني الذي يميز سلسلة التعدين اللوجستيكية يجعل من الصعب التنبؤ بأثر القرار المتخذ. هذا الترابط يعتبر العامل الرئيسي الذي يفسر إبطاء صناعة التعدين فيما يتعلق بتطبيق ونهج سياسة Lean Mining. يهدف نظام دعم القرار الخاص بصناعة التعدين إلى إعادة إنتاج الواقع ومن ثم اختبار أثر القرارات المتخذة، مع الأخذ بعين الاعتبار: هيئة المنجم، برنامج الصيانة، توفر الآلات، المطالب الواجب تلبيتها ... القرارات التي اتخذت في سلسلة عملية الاستخراج سيكون لها تأثير على: تطور مخزونات المادة الخام، مدى استعمال الآلات المخصصة لذلك، و تلبية المطالب ... نقترح اسسين اثنين من البرمجيات: يتناول الأول تخطيط التعدين لضمان الإدارة المتكاملة للمنجم والمساعدة في اتخاذ القرار في وقت قصير. أما الثاني فيهتم بتقييم / تحسين أساليب التنظيم في المنجم أثناء تكوين "خليط" انطلاقا من المواد الخام؛ ويعتبر هذا الأخير الناتج النهائي القابل للتسويق في إطار النظام اللوجستيكي للتعدين، ويتم إرساله إلى الزبناء الداخليين أو الخارجيين لسلسلة التوريد.أساليب جديدة للتنظيم الصناعي: لقد اقترحنا طريقة لتكوين خليط من المواد الخام والتي تختلف تماما عن الطريقة المستخدمة حاليًا. وتستند هذه الأخيرة على منطق التركيبة الثابتة في حين أننا نقترح تركيبات ديناميكية أطلقنا عليها إسم "المزج الديناميكي". تهدف هذه التسميات الديناميكية إلى تحديد الخلطات المثالية التي تتغير بتغير الوقت، اعتمادًا على المواد الخام المستخرجة وتركيبتها الكيميائية. وبالرغم من الإحجام عن تبني هذا النهج (وهو أمر طبيعي في إطار تنظيم ذو أسس "تاريخية عريقة")، فقد أظهر عمال المناجم اهتماما كبيرا بالنهج المقترح والذي تم التحقق من مصداقيته في هذا المجال والذي من الممكن تعميمه في مجال صناعي آخر

Avec l’avènement de la prochaine génération de télescope de plus de 30m de diamètre, il devient primordial de réduire le coût des observations et d’améliorer leur rendement scientifique. De plus il est essentiel de construire ces instruments sur des sites disposant d’une qualité optique maximale. J’ai donc essayé, au cours de ma thèse, de développer un outil fiable, facile d’utilisation et économique permettant de satisfaire ces exigences. J’ai donc utilisé le modèle de prévision météorologique Weather Research and Forecasting et le modèle de calcul de la turbulence optique Trinquet-Vernin pour prédire, plusieurs heures à l’avance, les conditions optiques du ciel tout au long de la nuit. Cette information permettrait d’améliorer la gestion du programme d’observation, appelée "flexible scheduling", et ainsi de réduire les pertes dues à la variation des conditions atmosphériques. Les résultats obtenus et les améliorations apportées au modèle WRF-TV lui permettent de présenter un bon accord entre les mesures et les prévisions ce qui est prometteur pour une utilisation réelle. Au delà de cette gestion, nous avons voulu créer un moyen d’améliorer la recherche et le test de sites astronomiquement intéressants. Nous avons donc définit un paramètre de qualité qui prend en compte les conditions météorologiques et optiques. Ce paramètre a été testé au-dessus de l’île de La Palma aux Canaries et a montré que l’Observatorio del Roque de los Muchachos est situé au meilleur emplacement de l’île. Enfin nous avons créé une routine d’automatisation du modèle WRF-TV afin d’avoir un outil opérationnel fonctionnant de manière autonome
With the next generation of extremely large telescope having mirror with a diameter larger than 30m, it becomes essential to reduce the cost of observations and to improve their scientific efficiency. Moreover it is fundamental to build these huge infrastructures in location having the best possible optical quality. The purpose of my thesis is to bring a solution easier and more economical than before. I used the Weather Research and Forecasting (WRF) model and the Trinquet-Vernin parametrization, which computes the values of the optical turbulence, to forecast a couple of hours in advance the evolution of the sky optical quality along the coming night. This information would improve the management of observation program, called "flexible scheduling", and thereby reduce losses due to the atmospheric variations. Our results and improvements allow the model us WRF-TV to have a good agreement between previsions and in-situ measurements in different sites, which is promising for a real use in an observatory. Beyond the flexible scheduling, we wanted to create a tool to improve the search for new sites or site testing for already existing sites. Therefore we defined a quality parameter which takes into account meteorological conditions (wind, humidity, precipitable water vapor) and optical conditions (seeing, coherence time, isoplanatic angle). This parameter has been tested above La Palma in Canary island showing that the Observatorio del Roque de los Muchachos is located close to the best possible location of the island. Finally we created an automated program to use WRF-TV model in order to have an operational tool working routinely

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

AbstractWe review algorithmic techniques for energy conservation in processing environments handling big data sets. Firstly, we address dynamic speed scaling, where processors can run at variable speed/frequency. The goal is to use the speed spectrum of the processors so as to minimize energy consumption while providing a desired service. Here we focus on multi-processor platforms with heterogeneous CPUs. Secondly, we examine power-down mechanisms where idle devices can be transitioned into low-power standby and sleep states. We consider power-down mechanisms in massively parallel systems, where the components have to coordinate their active and idle periods. In particular we focus on data centers with homogeneous as well as heterogeneous servers.

Abstract Using Autonomous Mobile Robots (AMRs) to collaboratively complete tasks has received a lot of attention in recent years from both industry and acedemia, especially in applications related to manufacturing automation. However, in spite of the technological progress, there are many challenges yet to be addressed in prioritized task allocation and scheduling of a school of AMRs in real time. This paper focuses on the real-time task allocation problem for a school of AMRs, i.e., given a prioritized task list and multiple AMRs, determining the set of tasks to be completed by each AMR. This paper proposes a probabilistic task allocation method which formulates the problem as a log-likelihood maximization problem, and uses a cyclic optimization scheme. This algorithm is shown to perform better when compared to commonly-used algorithms for asymmetric clustering. This proposed algorithm can be combined with scheduling methods to generate a ‘cluster-first, order-second’ solution to the multi-AMR task planning problem.

Objective: Determine the state-of-the-art in dynamic scheduling techniques for cloud manufacturing.Significance: This paper firmly establishes the underexplored technique of Deep Reinforcement Learning as the state-of-the-art for dynamic scheduling in cloud manufacturing, exposes a significant gap in the literature, and sets out critical future research objectives.Abstract:For many years, metaheuristic algorithms have represented the state of the art in manufacturing scheduling techniques, proving to be exceptionally reliable for optimising schedules. However, metaheuristics suffer from inherent weaknesses that inhibit their ability to be applied to dynamic cloud manufacturing (CMfg) scheduling problems in practice. Thanks to the very recent and rapidly accelerating development in deep reinforcement learning (DRL), a small sample of studies have described how those approaches have thoroughly outperformed metaheuristic algorithms in dynamic manufacturing scheduling problems, establishing a new state of the art. However, a significant lag in maturity exists between the algorithms used in CMfg and state-of-the-art DRL. This paper systematically reviews the CMfg scheduling literature published between 2010 and 2020, summarises the development of deep reinforcement learning in this context and offers valuable directions for future research.

In this paper, an event-based sampled discrete-time linear system representing a port-fuel-injection process based on wall-wetting dynamics is obtained and formulated as a linear parameter varying (LPV) system. The system parameters used in the engine fuel system model are engine speed, temperature, and load. These system parameters can be measured in real-time through physical or virtual sensors. A gain-scheduling controller for the obtained LPV system is then designed based on the numerically efficient convex optimization or linear matrix inequality (LMI) technique. To demonstrate the feasibility of implementing the gain-scheduling controller, a hardware-in-the-loop (HIL) simulation is performed using a mixed mean-value and crank-based engine model. The HIL results show the effectiveness and implementability of the proposed scheme.

Abstract The Job Shop Scheduling Problem (JSSP) is a method which assigns multiple jobs to various machines. The large dimension of JSSP and the dynamic manufacturing environment have always been a difficult problem to optimize due to its size and complexity. In this study, three objective functions are selected namely, minimizing makespan, minimizing total cost and maximizing machine utilization. Genetic Algorithm (GA) is used to solve this scheduling problem. Lot size optimization technique is investigated for the potential of optimizing the makespan, total cost, and machine utilization objectives. Global Criterion (GC) Technique is implemented which can optimize multiple objectives all at once and obtain the best schedule. Finally, a case study is presented.