Nous nous intéressons à la mise en oeuvre effective d'applications temps réel dans une approche d'ordonnancementhors-ligne de systèmes de tâches périodiques. L'ordonnancement hors-ligne consiste à rechercher avantl'exécution de l'application une séquence pire cas, c'est-à-dire une suite de blocs indiquant une date de débutet de fin d'exécution d'une instance de tâche. Mettre en oeuvre une séquence suppose de spécifier ce qui doit sepasser quand les durées d'exécution réelles sont inférieures aux durées pire cas prévues par la séquence. Notrepremière contribution consiste en la proposition de deux politiques de mise en oeuvre : une politique inflexiblequi respecte strictement les dates de début des blocs ; et une politique flexible qui permet de les avancer. Nousprouvons que ces politiques préservent la validité des séquences. Nous proposons ensuite un modèle de coûtspour l'évaluation et la comparaison de techniques respectant les politiques proposées. La seconde contributionconcerne la proposition de techniques de mise en oeuvre. Dans un premier temps, nous proposons sept techniquesde mise en oeuvre dans un contexte de tâches indépendantes et séquences sans préemption. Nous étendonsensuite l'utilisation de ces techniques aux séquences avec préemption, et aux tâches partageant des ressourcescritiques ou soumises à des contraintes de précédence. La troisième contribution concerne la mise en oeuvresous Posix. Nous présentons des outils de génération de code issus de l'ingénierie dirigée par les modèles. Nousproposons également un outil d'observation de séquences effectives. Enfin, une étude de cas présente l'utilisationpratique de notre approche. / We address the implementation of periodic task sets for off-line scheduling. Off-line scheduling approach consistsin computing a worst-case schedule before runtime. Implementing a schedule requires to specify what must happenwhen the actual execution times of tasks are lower than the planned execution times. The first contributionconsist of the formalization of implementation policies. These policies consider the date by which a task maystart execution, which may or not occur before the planned start time. The inflexible policy does not allowa task to run before its planned start time, the flexible policy does. Since many implementations can complywith these two policies, we also propose a cost model which enables to perform some comparisons betweenthese implementations. The second contribution is the proposition and the presentation of a set of algorithmswhich implement the pre-computed schedules. We first deal with independent task sets in a non preemptivecontext. These algorithms are then adapted to be used in the context of preemptive scheduling, with sharedcritical ressources and precedence constraints. Using the model driven engeneering, we next provide a Posixcode generation tool. We also present a schedule observation tool. Finally, our work has been tested through apratical case study.

El presente trabajo de título tuvo como objetivo el diseño, desarrollo y evaluación de una herramienta que permitiera apoyar la toma de decisiones respecto de la programación de operaciones en cada una de las dos plantas con que actualmente cuenta una compañía siderúrgica. Se buscó de esta forma encontrar la secuencia en que debieran ejecutarse los distintos trabajos mensuales, minimizando los tiempos de producción así como los tiempos de retrasos en las fechas de entrega. La investigación se centró, por razones de tiempo, únicamente en el proceso de laminación de la compañía, que es aquel en donde se le da la forma final a los productos siderúrgicos mediante deformación termomecánica. Esta elección no fue al azar y se tomó considerando el hecho de que dicho proceso es hasta el día de hoy el principal “cuello de botella” y por lo tanto representaba las mayores oportunidades de ganancia. Ahora bien, fue posible demostrar que el problema pertenece a la clase NP-Hard por lo que no se conocen algoritmos capaces de resolverlo en un tiempo polinomial. Como consecuencia, y dado que el tamaño de la instancia es relativamente grande, se hizo necesario incorporar enfoques heurísticos que permitieran obtener resultados suficientemente buenos en un tiempo de computación razonable. Es así como se optó por un algortimo de Búsqueda Tabú. La elección se basó principalmente en los buenos resultados reportados en la literatura para otros problemas de programación de operaciones (Lin y Ying, 2006; Gupta y Smith, 2007 y Valente y Alves, 2008). Gran parte del desempeño de este tipo de heurística depende de dos elementos: la solución inicial y la metodología de generación de vecindades. Es por ello que la estrategia seguida consistió en evaluar un amplio espectro de las técnicas más utilizadas para tales fines, escogiendo finalmente aquella combinación que presentó un mejor desempeño. Los resultados obtenidos muestran que la aplicación de la heurística propuesta a instancias reales permite obtener reducciones importantes en comparación a la situación actual: un 7% promedio en los tiempos de producción y disminuciones promedio del 35% en lo que se refiere a los tiempos de retraso. Por otra parte, se observa una dramática caída del 82% promedio en lo que al tiempo necesario para determinar la programación respecta. Finalmente, cabe destacar que la investigación realizada sugiere también que aún hay espacio para futuras mejoras, por lo que se recomienda dar continuidad al estudio y en lo posible ampliarlo a otros procesos de la cadena productiva.

[pt] As doenças vasculares são enfermidades graves e seus tratamentos são complexos e necessitam de procedimentos cirúrgicos. Para a realização desses procedimentos, são necessários equipamentos, equipes qualificadas e unidade de terapia intensiva (UTI) equipada para o pós-operatório. Hospitais de ensino devem atender à legislação vigente que preconiza um número mínimo de cirurgias para aprovação do residente no programa de formação. Assim, propõe-se, via otimização, encontrar soluções eficientes para o planejamento e programação de cirurgias eletivas que atendam à legislação. Este problema é tratado em 2 níveis. O primeiro é relativo ao planejamento e é chamado de Master Surgical Schedule (MSS) que consiste em definir os recursos necessários para a realização de um conjunto de procedimentos. O segundo se refere à programação e é chamado de Surgical Case Assigment Problem (SCAP) e tem por objetivo alocar o médico a cada cirurgia. Assim, foram propostos dois modelos de programação matemática, um para o MSS e outro para o SCAP. Estes modelos foram aplicados no caso real da alocação de residentes para cirurgias vasculares no Hospital Universitário Pedro Ernesto. Como resultado do modelo MSS, identificou-se a necessidade de mais anestesistas e maior disponibilidade de equipamentos para atender à legislação de formação de residentes. Por fim, como resultado do SCAP, o quantitativo de cirurgias foi distribuído entre os cirurgiões de forma balanceada. / [en] Vascular diseases are serious diseases and their treatments are complex and require surgical procedures. In order to perform these procedures, is required equipment, qualified teams and an intensive care unit (ICU) equipped for the postoperative period. Teaching hospitals must comply with current legislation that recommend a minimum number of surgeries for the resident s approval in the training program. Thus, it is proposed, through optimization, to find efficient solutions for the planning and programming of elective surgeries that comply with the legislation. This problem is dealt with on two levels. The first is relative to planning and is called the Master Surgical Schedule (MSS), which consists of defining the necessary resources to perform a set of procedures. The second one refers to programming and is called Surgical Case Assigment Problem (SCAP) and aims to allocate the doctor to each surgery. Thus, two models of mathematical programming were proposed, one for MSS and another for SCAP. These models were applied in the real case of residents allocation for vascular surgeries at Pedro Ernesto University Hospital. As a result of MSS model were identified the need for more anesthesiologists and greater availability of equipment ensure the cover of resident training legislation. Finally, as a result of SCAP, the quantity of surgeries was distributed equitably distributed among surgeons.

In this article, we study the school bus routing and scheduling problem with transfers arising in the field of nonperiodic public transportation systems. It deals with the transportation of pupils from home to their school in the morning taking the possibility that pupils may change buses into account. Allowing transfers has several consequences. On the one hand, it allows more flexibility in the bus network structure and can, therefore, help to reduce operating costs. On the other hand, transfers have an impact on the service level: the perceived service quality is lower due to the existence of transfers; however, at the same time, user ride times may be reduced and, thus, transfers may also have a positive impact on service quality. The main objective is the minimization of the total operating costs. We develop a heuristic solution framework to solve this problem and compare it with two solution concepts that do not consider transfers. The impact of transfers on the service level in terms of time loss (or user ride time) and the number of transfers is analyzed. Our results show that allowing transfers reduces total operating costs significantly while average and maximum user ride times are comparable to solutions without transfers. (authors' abstract)

M.Sc. / The manufacturing sector has produced a wide variety of techniques in its attempts to find the ultimate solution for the manufacturing process, with these techniques ranging from material requirements planning, just-in-time production, total-quality management, flexible manufacturing systems and computer integrated manufacturing to advanced planning and scheduling. Given the fact that the technique entitled "advanced planning and scheduling" in the manufacturing environment is primarily aimed at resource planning and scheduling during the production process, however, a clamant need was created for manufacturing companies to broaden their focus in order to include all the processes involved in the production environment, as well as the external processes impacting on productivity. A large area that came into focus owing to the latter paradigm shift is known as "supply chain management". Supply chain management is concerned with the integration of and communication between the various elements in the entire supply chain, including elements such as demand planning and forecasting, scheduling, customer sales, supplier purchases, production planning and forecasting, resource planning and warehouse management. This research study will be devoted to an investigation into the issues surrounding supply chain management and all its manifestations, including its basic components and their integration and interaction. This investigation will also cover research into scheduling systems up to current reactive constraintbased scheduling systems, since scheduling is deemed to be the core of the supply chain in terms of the influence it exerts on most other components, be it directly or indirectly. The investigation will also take us into the realm of an exciting new technology whose exponents are known as "intelligent software agents", which agents are aimed at providing autonomy to the objects within a system and which agents are characterised by their behaviour and decision processes. The said agents can be used to perform highly specialised tasks during the manufacturing process, such as scheduling and forecasting. A prototype system will be developed in the course of the research in a bid to illustrate the integration, evaluation and monitoring of the supply chain elements through the use of intelligent agents. By endowing the system with intelligence, the researchers hope to identify many future uses for intelligent agents in the various segments of the supply chain.

Irrigation scheduling is accepted as the process to decide when to irrigate crops and how much to apply and is assumed to play an important role in the general improvement of water efficiency on the farm. However, the idea that there is a single key to the adoption of irrigation scheduling on the farm is simplistic. It implies that science has all the answers, and “we need just to convince the farmers”. The objectives of this study were to investigate the adoption process in South Africa with the further purpose to identify the possible human and socio-economic factors that may influence it. In order to appreciate the spectrum of soil-plant-atmosphere irrigation scheduling models and techniques that are available to potential users, it was necessary to quantitatively describe and classify the scheduling methods. The adoption of irrigation scheduling methods among commercial and small-scale farmers was investigated on a scheme (macro) level as well as on-farm (micro) level through a quantitative assessment of scheduling methods on a national basis, semi-structured interviews with irrigation professionals, survey among a stratified sample of commercial farmers and case studies of small scale irrigation farmers. It was hypothesized that the adoption behaviour of irrigation farmers is determine by socio-economic (independent) and intervening factors. It was also hypothesized that ground level support and effective dialogue between scientist and farmers are conducive for the implementation of irrigation scheduling. The study indicates that only 18% of irrigation farmers in South Africa make use of objective irrigation scheduling method, while the rest make use of subjective scheduling methods based on intuition, observation, local knowledge and experience. Differential perceptions occur between farmers as well as between farmers and scientists with regard to the concept of “irrigation scheduling” commonly being used. These differences contributed to the communication gap between science and the practice of irrigation scheduling resulting in the unsuccessful communication between farmers and scientists and the ultimate low adoption rate. The implementation of irrigation scheduling models are predominantly advisor-driven and not farmer-driven, as they are perceived by farmers to be complex and not easy to implement on the farm. Younger farmers are more willing to use irrigation models because of their higher computer literacy levels and positive attitude towards the use of computers in general. The technology level of a farm, size of farming operation and the value of the crop being produced determine the selection of irrigation scheduling methods. The general problems experienced by some farmers with regard to bulk water delivery hampers the implementation of more precise irrigation scheduling. Farmers’ awareness, flexibility and willingness to change, innovate and step outside of accustomed ways of implementing irrigation, are strongly influenced by their social, economic, cultural and institutional settings, and not merely by irrigation scheduling technology. Perceived indicators of efficient use of irrigation on the farm include increased production levels, decreasing electricity costs, improvement of crop quality and efficiency of fertiliser use. Farmers identified accuracy, reliability, ease of implementing and affordability as important technological characteristics of scheduling methods and devices. The case studies of small-scale irrigation farming revealed that weak institutional arrangements and handling of farmers’ affairs on the level of several small-scale irrigation schemes hampers sustainable agricultural development. Small-scale irrigators have reported that the lack of competent extension support prevents them from implementing irrigation scheduling. Also, the scientific framework used by scientists and advisors to convey information to irrigators often follows the linear transfer of technology approach instead of following the “learning based approach”. A significant relationship exists between the number of information sources used and the implementation of the type of scheduling methods The majority of irrigation farmers are more interested in the use of irrigation scheduling to identify “troubles or problems” experienced with irrigation, and inevitably farmers will differ in their selection of the most appropriate scheduling method and technique. / Thesis (PhD (Agricultural Economics, Extension and Rural Development))--University of Pretoria, 2007. / Agricultural Economics, Extension and Rural Development / unrestricted

No description available.

Cloud computing environments mainly focus on the delivery of resources, platforms, and infrastructure as services to users over the Internet. More specifically, Cloud promises user access to a scalable amount of resources, making use of the elasticity on the provisioning of recourses by scaling them up and down depending on the demand. The cloud technology has gained popularity in recent years as the next big step in the IT industry. The number of users of Cloud services has been increasing steadily, so the need for efficient task scheduling is crucial for improving and maintaining performance. Moreover, those users have different SLAs that imposes different demands on the cloud system. In this particular case, a scheduler is responsible for assigning tasks to virtual machines in an effective and efficient matter to meet with the QoS promised to users. The scheduler needs to adapt to changes in the cloud environment along with defined demand requirements. Hence, an Adjustable and Configurable bio-inspired scheduling heuristic for cloud based systems (ACBH) is suggested. We also present an extensively comparative performance study on bio-inspired scheduling algorithms namely Ant Colony Optimization (ACO) and Honey Bee Optimization (HBO). Furthermore, a networking scheduling algorithm is also evaluated, which comprises Random Biased Sampling (RBS). The study of bio-inspired techniques concluded that all the bio-inspired algorithms follow the same flow that was later used in the development of (ACBH). The experimental results have shown that ACBH has a 90% better execution time that it closest rival which is ACO. ACBH has a better performance in terms of the fairness between execution time differences between tasks. HBO shows better scheduling when the objective consists mainly of costs. However, when there is multiple optimization objectives ACBH performs the best due to its configurability and adaptability.

A scheduler, as a central components of a computing site, aggregates computing resources and is responsible to distribute the incoming load (jobs) between the resources. Under such an environment, the optimum performance of the system against the service level agreement (SLA) based workloads, can be achieved by calculating the priority of SLA bound jobs using integrated heuristic. The SLA defines the service obligations and expectations to use the computational resources. The integrated heuristic is the combination of different SLA terms. It combines the SLA terms with a specific weight for each term. Theweights are computed by applying parameter sweep technique in order to obtain the best schedule for the optimum performance of the system under the workload. The sweepingof parameters on the integrated heuristic observed to be computationally expensive. The integrated heuristic becomes more expensive if no value of the computed weights result in improvement in performance with the resulting schedule. Hence, instead of obtaining optimum performance it incurs computation cost in such situations. Therefore, there is a need of detection of situations where the integrated heuristic can be exploited beneficially. For that reason, in this thesis we propose a metric based on the concept of utilization, to evaluate the SLA based parallel workloads of independent jobs to detect any impact of integrated heuristic on the workload.

This research aims at a study of the hybrid flow shop problem which has parallel batch-processing machines in one stage and discrete-processing machines in other stages to process jobs of arbitrary sizes. The objective is to minimize the makespan for a set of jobs. The problem is denoted as: FF|batch1, sj|Cmax. The problem is formulated as a mixed-integer linear program. The commercial solver, AMPL/CPLEX, is used to solve problem instances to their optimality. Experimental results show that AMPL/CPLEX requires considerable time to find the optimal solution for even a small size problem, i.e., a 6-job instance requires 2 hours in average. A bottleneck-first-decomposition heuristic (BFD) is proposed in this study to overcome the computational (time) problem encountered while using the commercial solver. The proposed BFD heuristic is inspired by the shifting bottleneck heuristic. It decomposes the entire problem into three sub-problems, and schedules the sub-problems one by one. The proposed BFD heuristic consists of four major steps: formulating sub-problems, prioritizing sub-problems, solving sub-problems and re-scheduling. For solving the sub-problems, two heuristic algorithms are proposed; one for scheduling a hybrid flow shop with discrete processing machines, and the other for scheduling parallel batching machines (single stage). Both consider job arrival and delivery times. An experiment design is conducted to evaluate the effectiveness of the proposed BFD, which is further evaluated against a set of common heuristics including a randomized greedy heuristic and five dispatching rules. The results show that the proposed BFD heuristic outperforms all these algorithms. To evaluate the quality of the heuristic solution, a procedure is developed to calculate a lower bound of makespan for the problem under study. The lower bound obtained is tighter than other bounds developed for related problems in literature. A meta-search approach based on the Genetic Algorithm concept is developed to evaluate the significance of further improving the solution obtained from the proposed BFD heuristic. The experiment indicates that it reduces the makespan by 1.93% in average within a negligible time when problem size is less than 50 jobs.