Scheduling is concerned with the process of deciding how to commit resources between a variety of possible tasks with the aim of optimizing some performance criterion. Efficient scheduling is a vital tool in successful decision-making. To date, an enormous amount of research has been done on scheduling problems arising from various disciplines. Major attention has so far been dedicated to off-line (usually deterministic) scheduling problems. Off-line deterministic scheduling deals with perfect information. That is, all information with regard to a problem is known prior to any decision. However, this perfect information assumption violates the nature of many realistic issues with uncertainties, for example, a situation where the knowledge of problem instances is revealed over time, or a scenario in which processing tasks are temporarily disrupted or cancelled. To better formulate this sort of problem with high uncertainties, a new concept of on-line scheduling was introduced. On-line approaches have become increasingly important and are frequently encountered when only partial knowledge is available but instant or very fast solution methods are required and should nevertheless result in good outcomes. In on-line scheduling, a decision maker allocates resources between tasks as the information is gradually released. Obviously, given the same scheduling environment and problem instance, the result produced by an on-line scheduler cannot be better than that by the optimal off-line scheduler; but the on-line scheduling technique immunizes schedules from future disruptions and uncertainties. / This thesis extends the study of some scheduling problems derived from various industrial and computing situations to on-line scheduling environments, specifically the on-line-list and the on-line-time paradigms. The six topics studied are classified in two parts in this thesis. Part I consists of three machine scheduling problems taking into account various types of setup considerations. Part II includes the other three scheduling problems which are closely related to issues arising in the management of shipping containers and wind energy. / The effort is focused on constructing effective and efficient (on-line) decision-making strategies with the purpose of optimizing certain objective measures in those uncertain scheduling environments. The performance of the proposed heuristics as well as some existing on-line algorithms is evaluated and compared via competitive analysis. For some cases, empirical studies are also carried out to assess their average performance.

Scheduling is concerned with the process of deciding how to commit resources between a variety of possible tasks with the aim of optimizing some performance criterion. Efficient scheduling is a vital tool in successful decision-making. To date, an enormous amount of research has been done on scheduling problems arising from various disciplines. Major attention has so far been dedicated to off-line (usually deterministic) scheduling problems. Off-line deterministic scheduling deals with perfect information. That is, all information with regard to a problem is known prior to any decision. However, this perfect information assumption violates the nature of many realistic issues with uncertainties, for example, a situation where the knowledge of problem instances is revealed over time, or a scenario in which processing tasks are temporarily disrupted or cancelled. To better formulate this sort of problem with high uncertainties, a new concept of on-line scheduling was introduced. On-line approaches have become increasingly important and are frequently encountered when only partial knowledge is available but instant or very fast solution methods are required and should nevertheless result in good outcomes. In on-line scheduling, a decision maker allocates resources between tasks as the information is gradually released. Obviously, given the same scheduling environment and problem instance, the result produced by an on-line scheduler cannot be better than that by the optimal off-line scheduler; but the on-line scheduling technique immunizes schedules from future disruptions and uncertainties. / This thesis extends the study of some scheduling problems derived from various industrial and computing situations to on-line scheduling environments, specifically the on-line-list and the on-line-time paradigms. The six topics studied are classified in two parts in this thesis. Part I consists of three machine scheduling problems taking into account various types of setup considerations. Part II includes the other three scheduling problems which are closely related to issues arising in the management of shipping containers and wind energy. / The effort is focused on constructing effective and efficient (on-line) decision-making strategies with the purpose of optimizing certain objective measures in those uncertain scheduling environments. The performance of the proposed heuristics as well as some existing on-line algorithms is evaluated and compared via competitive analysis. For some cases, empirical studies are also carried out to assess their average performance.

We consider the scheduling problem of minimizing the average weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith's ratio rule yield smaller competitive ratios compared to the previously best-known deterministic on-line algorithms, which are (4+epsilon)-competitive in either case. Our preemptive algorithm is 2-competitive, which actually meets the competitive ratio of the currently best randomized on-line algorithm for this scenario. Our nonpreemptive algorithm has a competitive ratio of 3.28. Both results are characterized by a surprisingly simple analysis; moreover, the preemptive algorithm also works in the less clairvoyant environment in which only the ratio of weight to processing time of a job becomes known at its release date, but neither its actual weight nor its processing time. In the corresponding nonpreemptive situation, every on-line algorithm has an unbounded competitive ratio

The open bin packing problem (OBPP) is a new variant of the well-known bin packing problem. In the OBPP, items are packed into bins so that the total content before the last item in each bin is strictly less than the bin capacity. The objective is to minimize the number of bins used. The applications of the OBPP can be found in the subway station systems in Hong Kong and Taipei and the scheduling in manufacturing industries. We show that the OBPP is NP-hard and propose two heuristic algorithms instead of solving the problem to optimality. We propose two offline algorithms in which the information of the items is known in advance. First, we consider the First Fit Decreasing (FFD) which is a good approximation algorithm for the bin packing problem. We prove that its asymptotic worst-case performance ratio is no more than 3/2. We observe that its performance for the OBPP is worse than that of the BPP. Consequently, we modify it by adding the algorithm that the set of largest items is the set of last items in each bin. Then, we propose the Modified First Fit Decreasing (MFFD) as an alternative and prove that its asymptotic worst-case performance ratio is no more than 91/80. We conduct empirical tests to show their average-case performance. The results show that in general, the FFD and MFFD algorithms use no more than 33% and 1% of the number of bins than that of optimal packing, respectively. In addition, the MFFD is asymptotically optimal when the sizes of items are (0,1) uniformly distributed. / Ph. D.

L'apparition de CUDA en 2007 a rendu les GPU hautement programmables permettant ainsi aux applications scientifiques et techniques de profiter de leur capacité de calcul élevée. Des solutions ultra-rapides pour la résolution des transferts de chaleur par rayonnement et par conduction sur GPU sont présentées dans ce travail. Tout d'abord, la méthode MACZM pour le calcul des facteurs de transferts radiatifs directs en 3D et en milieu semi-transparent est représentée et validée. Ensuite, une implémentation efficace de la méthode à la base d'algorithmes de géométrie discrète et d'une parallélisation optimisée sur GPU dans CUDA atteignant 300 à 600 fois d'accélération, est présentée. Ceci est suivi par la formulation du NRPA, une version non-récursive de l'algorithme des revêtements pour le calcul des facteurs d'échange radiatifs totaux. La complexité du NRPA est inférieure à celle du PA et sont exécution sur GPU est jusqu'à 750 fois plus rapide que l'exécution du PA sur CPU. D'autre part, une implémentation efficace de la LOD sur GPU est présentée, consistant d'une alternance optimisée des solveurs et schémas de parallélisation et achevant une accélération GPU de 75 à 250 fois. Finalement, toutes les méthodes sont appliquées ensemble pour la résolution des transferts de chaleur en 3D dans un four de réchauffage sidérurgique de brames d'acier. Dans ce but, MACZM est appliquée avec un maillage multi-grille et le NRPA est appliqué au four en le découpant en zones, permettant d'avoir un temps de calcul très rapide une précision élevée. Ceci rend les méthodes utilisées de très grande importance pour la conception de stratégies de contrôle efficaces et précises. / The release of CUDA by NVIDIA in 2007 has tremendously increased GPU programmability, thus allowing scientific and engineering applications to take advantage of the high GPU compute capability. In this work, we present ultra-fast solutions for radiation and diffusion heat transfer on the GPU. First, the Multiple Absorption Coefficient Zonal Method (MACZM) for computing direct radiative exchange factors in 3D semi-transparent media is reviewed and validated. Then, an efficient implementation for MACZM is presented, based on discrete geometry algorithms, and an optimized GPU CUDA parallelization. The CUDA implementation achieves 300 to 600 times speed-up. The Non-recursive Plating Algorithm (NRPA), a non-recursive version of the plating algorithm for computing total exchange factors is then formulated. Due to low-complexity matrix multiplication algorithms, the NRPA has lower complexity than the PA does and it runs up to 750 times faster on the GPU by comparison to the CPU PA. On the other hand, an efficient GPU implementation for the Locally One Dimensional (LOD) finite difference split method for solving heat diffusion is presented, based on an optimiwed alternation between parallelization schemes and equation solvers, achieving accelerations from 75 to 250 times. Finally, all the methods are applied together for solving 3D heat transfer in a steel reheating furnace. A multi-grid approach is applied for MACZM and a zone-by zone computation for the NRPA. As a result, high precision and very fast computation time are achieved, making the methods of high interest for building precise and efficient control units.