Academic literature on the topic 'Dynamic Scheduling Technique'

Thesis (M.S.)--West Virginia University, 1999.<br>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<br>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<br>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<br>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)<br>إن الطلب العالمي على الموارد المعدنية بشكل عام، والفوسفاط على وجه الخصوص، يزداد بسرعة منذ عدة سنوات. وفي هذا السياق الذي يعنى بمنافسة قوية بين الأطر الفعالة، يسعى كل مصنع الى أن يكون الرائد في مجاله، وأن يقلل من تكاليف الإنتاج من أجل ضمان متانته في إطار خضوعه لقيود قانونية تحت منظور التنمية المسؤولة. في إطار مواجهة قضايا مماثلة، انتقلت العديد من الصناعات التحويلية، بنجاح لعدة عقود، إلى تطبيق النهج الياباني 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<br>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<br>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