Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This work presents three evolutionary strategies to solve the problem of scheduling a given set of n jobs to m identical parallel machines with the objective of minimizing makespan. There is a sequence dependent setup times. We also compares our method with two other well succeeded heuristics, one is a tabu search based heuristic and the second is a memetic approach, which combines a population-based method with local search procedures. As benchmarks for smallsized instances, optimal values are used provide by a dichotomous search. For larger instances, the comparisons try to show the robust behavior in solution quality as well as in computational effort of our evolutionary strategy. / Este trabalho propõe três estratégias evolutivas para resolver o problema de seqüenciamento de n tarefas em m máquinas paralelas idênticas, buscando minimizar o tempo máximo de finalização (makespan). São considerados tempos de preparação dependentes da seqüência. Os métodos propostos são comparados com outras duas heurísticas de qualidade comprovada, uma baseada em Busca Tabu e outra baseada em Algoritmos Meméticos. Para algumas instâncias de pequeno porte, comparações são feitas com o valor ótimo obtido através de uma busca dicotômica. Para instâncias maiores, as comparações demonstram a robustez e a boa qualidade das soluções encontradas pelas estratégias evolutivas através da comparação com as outras heurísticas.

Um importante problema de programação da produção surge em indústrias de papel integrando o problema de planejamento em múltiplas máquinas paralelas com o problema de corte. O problema de dimensionamento de lotes deve determinar a quantidade de jumbos (bobinas grandes de papel) de diferentes tipos de papel a serem produzidos em cada máquina. Estes jumbos são então cortados para atender a demanda de itens (bobinas menores de papel). O planejamento, que minimiza custos de produção e preparação, deve produzir jumbos (cada máquina produz jumbos de larguras diferentes) que diminuam a perda no processo de corte. Por outro lado, o melhor número de jumbos do ponto de vista de minimizar a perda no processo de corte pode acarretar em altos custos de preparação. Ambos são problemas de otimização combinatória não trivial, o que tem motivado extensas pesquisas nas últimas décadas, entretanto, essa combinação não é bem explorada na literatura. Neste trabalho, são propostos um modelo de otimização integrado e métodos heurísticos de solução. Foram realizados experimentos computacionais com o intuito de analisar o desempenho dos métodos propostos e os resultados apresentaram- se bastante satisfatórios, significando que tais métodos são apropriados para tratar o problema integrado. / An important production programming problem arises in paper industries coupling mul- tiple machine scheduling with cutting stock. From machine scheduling the problem of determining the quantity of jumbos (large rolls of paper) of different types of paper to be produced in each machine arises. These jumbos are then cut to meet the demand for items (smaller rolls of paper). Scheduling that minimizes setups and production costs may produce jumbos (each machine produces jumbos of a specific width) which may increase waste in the cutting process. On the other hand, the best number of jumbos in the point of view of minimizing waste in the cutting process may lead to high setup costs. Both problems are non-trivial combinatorial optimization problems, which have motivated ex- tensive research in the last decades, however their combination is not well explored in the literature. In this work, a coupled optimization modelling and heuristic solution methods are proposed. Computational experiments are devised in order to analyze the performance of the methods and the results had been presented sufficiently satisfactory, meaning that such methods are appropriate to deal with the integrated problem.

Um importante problema de programação da produção surge em indústrias de papel integrando o problema de planejamento em múltiplas máquinas paralelas com o problema de corte. O problema de dimensionamento de lotes deve determinar a quantidade de jumbos (bobinas grandes de papel) de diferentes tipos de papel a serem produzidos em cada máquina. Estes jumbos são então cortados para atender a demanda de itens (bobinas menores de papel). O planejamento, que minimiza custos de produção e preparação, deve produzir jumbos (cada máquina produz jumbos de larguras diferentes) que diminuam a perda no processo de corte. Por outro lado, o melhor número de jumbos do ponto de vista de minimizar a perda no processo de corte pode acarretar em altos custos de preparação. Ambos são problemas de otimização combinatória não trivial, o que tem motivado extensas pesquisas nas últimas décadas, entretanto, essa combinação não é bem explorada na literatura. Neste trabalho, são propostos um modelo de otimização integrado e métodos heurísticos de solução. Foram realizados experimentos computacionais com o intuito de analisar o desempenho dos métodos propostos e os resultados apresentaram- se bastante satisfatórios, significando que tais métodos são apropriados para tratar o problema integrado. / An important production programming problem arises in paper industries coupling mul- tiple machine scheduling with cutting stock. From machine scheduling the problem of determining the quantity of jumbos (large rolls of paper) of different types of paper to be produced in each machine arises. These jumbos are then cut to meet the demand for items (smaller rolls of paper). Scheduling that minimizes setups and production costs may produce jumbos (each machine produces jumbos of a specific width) which may increase waste in the cutting process. On the other hand, the best number of jumbos in the point of view of minimizing waste in the cutting process may lead to high setup costs. Both problems are non-trivial combinatorial optimization problems, which have motivated ex- tensive research in the last decades, however their combination is not well explored in the literature. In this work, a coupled optimization modelling and heuristic solution methods are proposed. Computational experiments are devised in order to analyze the performance of the methods and the results had been presented sufficiently satisfactory, meaning that such methods are appropriate to deal with the integrated problem.

Les problèmes de séquencement et d'ordonnancement forment une famille de problèmes combinatoires qui implique la programmation dans le temps d'un ensemble d'opérations soumises à des contraintes de capacités et de ressources. Nous contribuons dans cette thèse à la résolution de ces problèmes dans un contexte de satisfaction de contraintes et d'optimisation combinatoire. Nos propositions concernent trois aspects différents: comment choisir le prochain nœud à explorer (recherche)? comment réduire efficacement l'espace de recherche (propagation)? et que peut-on apprendre des échecs rencontrés lors de la recherche (apprentissage)? Nos contributions commencent par une étude approfondie des heuristiques de branchement pour le problème de séquencement de chaîne d'assemblage de voitures. Cette évaluation montre d'abord les paramètres clés de ce qui constitue une bonne heuristique pour ce problème. De plus, elle montre que la stratégie de branchement est aussi importante que la méthode de propagation. Deuxièmement, nous étudions les mécanismes de propagation pour une classe de contraintes de séquencement à travers la conception de plusieurs algorithmes de filtrage. En particulier, nous proposons un algorithme de filtrage complet pour un type de contrainte de séquence avec une complexité temporelle optimale dans le pire cas. Troisièmement, nous investiguons l'impact de l'apprentissage de clauses pour résoudre le problème de séquencement de véhicules à travers une nouvelle stratégie d'explication réduite pour le nouveau filtrage. L'évaluation expérimentale montre l'importance de l'apprentissage de clauses pour ce problème. Ensuite, nous proposons une alternative pour la génération retardée de variables booléennes pour encoder les domaines. Finalement, nous revisitons les algorithmes d'analyse de conflits pour résoudre les problèmes d'ordonnancement disjonctifs. En particulier, nous introduisons une nouvelle procédure d'analyse de conflits dédiée pour cette famille de problèmes. La nouvelle méthode diffère des algorithmes traditionnels par l'apprentissage de clauses portant uniquement sur les variables booléennes de disjonctions. Enfin, nous présentons les résultats d'une large étude expérimentale qui démontre l'impact de ces nouveaux mécanismes d'apprentissage. En particulier, la nouvelle méthode d'analyse de conflits a permis de découvrir de nouvelle bornes inférieures pour des instances largement étudiées de la littérature / Sequencing and scheduling involve the organization in time of operations subject to capacity and resource constraints. We propose in this dissertation several improvements to the constraint satisfaction and combinatorial optimization methods for solving these problems. These contributions concern three different aspects: how to choose the next node to explore (search)? how much, and how efficiently, one can reduce the search space (propagation)? and what can be learnt from previous failures (learning)? Our contributions start with an empirical study of search heuristics for the well known car-sequencing problem. This evaluation characterizes the key aspects of a good heuristic and shows that the search strategy is as important as the propagation aspect in this problem. Second, we carefully investigate the propagation aspect in a class of sequencing problems. In particular, we propose an algorithm for filtering a type of sequence constraints which worst case time complexity is lower than the best known upper bound, and indeed optimal. Third, we investigate the impact of clause learning for solving the car-sequencing problem. In particular, we propose reduced explanations for the new filtering. The experimental evaluation shows compelling evidence supporting the importance of clause learning for solving efficiently this problem. Next, we revisit the general approach of lazy generation for the Boolean variables encoding the domains. Our proposition avoids a classical redundancy issue without computational overhead. Finally, we investigate conflict analysis algorithms for solving disjunctive scheduling problems. In particular, we introduce a novel learning procedure tailored to this family of problems. The new conflict analysis differs from conventional methods by learning clauses whose size are not function of the scheduling horizon. Our comprehensive experimental study with traditional academic benchmarks demonstrates the impact of the novel learning scheme that we propose. In particular, we find new lower bounds for a well known scheduling benchmark

<p>The Ph.D. thesis addresses a comprehensive study of the bee colony<br />optimization meta-heuristic method (BCO). Theoretical analysis of the<br />method is conducted with the tools of probability theory. Necessary and<br />sufficient conditions are presented that establish convergence of the BCO<br />method towards an optimal solution. Three parallelization strategies and five<br />corresponding implementations are proposed for BCO for distributed-memory<br />systems. The influence of method&rsquo;s parameters on the performance of the<br />BCO algorithm for two combinatorial optimization problems is analyzed<br />through the experimental study.</p> / <p>Докторска дисертације се бави испитивањем метахеуристичке методе<br />оптимизације колонијом пчела. Извршена је теоријска анализа<br />асимптотске конвергенције методе посматрањем конвергенције низа<br />случајних променљивих. Установљени су довољни и потребни услови<br />за које метода конвергира ка оптималном решењу. Предложене су три<br />стратегије паралелизације и пет одговарајућих имплементација конст-<br />руктивне варијанте методе за рачунаре са дистрибуираном меморијом.<br />Извршено је експериментално испитивање утицаја параметара методе<br />на њене перформансе за два различита комбинаторна проблема:<br />проблем распоређивања и проблем задовољивости.</p> / <p>Doktorska disertacije se bavi ispitivanjem metaheurističke metode<br />optimizacije kolonijom pčela. Izvršena je teorijska analiza<br />asimptotske konvergencije metode posmatranjem konvergencije niza<br />slučajnih promenljivih. Ustanovljeni su dovoljni i potrebni uslovi<br />za koje metoda konvergira ka optimalnom rešenju. Predložene su tri<br />strategije paralelizacije i pet odgovarajućih implementacija konst-<br />ruktivne varijante metode za računare sa distribuiranom memorijom.<br />Izvršeno je eksperimentalno ispitivanje uticaja parametara metode<br />na njene performanse za dva različita kombinatorna problema:<br />problem raspoređivanja i problem zadovoljivosti.</p>

Dans cette thèse, nous nous intéressons principalement à l’étude du fonctionnement cyclique mono-produit des ateliers de traitement de surface. Notre contribution porte sur le problème d’ordonnancement associé connu dans la littérature sous le nom Cyclic Hoist Scheduling Problem (CHSP). L’objet de cette thèse est de proposer des méthodes efficaces pour la résolution des problèmes de traitement de surface dans le cas où les produits à traiter sont du même type. Nous traitons en particulier le cas où le nombre des robots présents sur la ligne est égal à deux, ce qui augmente le nombre des contraintes du problème, sachant que dans le cas mono robot, ce problème a été prouvé NP-Complet. Pour cela, nous proposons une méthode qui combine deux heuristiques et un programme linéaire mixte. Cette méthode permet notamment d’affecter les mouvements de transport à l’un des deux robots tout en gérant les risques de collision entre eux, lorsque la gamme opératoire des produits à traiter suit l’implantation des cuves.Par la suite, nous proposons une extension du modèle au cas de lignes complexes. Enfin, nous étudions le cas d’un fonctionnement mixte, pour lequel il est nécessaire de traiter dans une même installation des produits différents et des rafales de produits identiques. Dans ces conditions, la solution la plus intéressante pour les industriels est de pouvoir alterner des modes de production dynamiques et cycliques. Pour cela, nous proposons une méthode efficace permettant de résoudre le problème d’ordonnancement associé à la phase transitoire relative à ce type de fonctionnement. Elle consiste en particulier à chercher les dates d’entrée au plus tôt des produits. La principale difficulté identifiée consiste ici à passer du mode dynamique au mode cyclique, c’est-à-dire à rejoindre un cycle à partir d’une solution courante donnée, en supposant que ce cycle est connu à priori. Les méthodes élaborées dans les divers cas traités sont validées par des tests sur des benchmarks de la littérature. / In this thesis, our interest is focused on the Cyclic Hoist Scheduling Problem (CHSP) in automated electroplating lines. The aim of this study is to propose an algorithm to solve the two-hoists cyclic scheduling problem. This one consists in finding a repetitive sequence of hoists’ moves, while avoiding collision between the hoists which share a common track. The objective is to minimize the period of this repetitive cycle for single part-type production. This problem was proved to be NP-complete for lines with a single hoist. The fact that two hoists are available on the line increases the number of constraints of the problem. Then we propose a solving method combining two heuristics and a Mixed Integer Linear Program. It enables us to solve both assignment and sequencing problems, while considering spatial constraints related to hoist’moves.Subsequently, we propose an extension of the model which is adapted to complex lines. Finally, our interest is focused on solving a HSP for which it is necessary to treat in the same facility a batch of various products and a batch of identical products. Under these conditions, the most interesting solution for manufacturers is to be able to alternate the production of two batches. For this goal, we propose an efficient method to solve the scheduling problem associated. Finally, our proposed methods are validated by experimentations based on benchmarks from the literature.

The economy of a developing nation like India depends on various sectors such as: Agriculture, Commerce and Industries, Finance, Communication and Information Technology, etc. The manufacturing industries play a key role in contributing to the economy of a nation. They mainly consist of industries like steel casting, automobiles and other heavy manufacturing. This research study is related to automobile industry and particularly the gear manufacturers. The automobile industry is an important industry from the manufacturing point of view. This is due to the fact that it has deep forward and backward linkages with several key segments of the economy and it has a strong multiplier effect. Hence, it is capable of being the driver of economic growth. The recent trend among the automobile manufacturing organizations is to outsource individual components to sub-contractors and conduct the sub-assemblies and assemblies in-house. Some components like gears are important in terms of quality. So in case of these components the automobile manufacturing organizations normally partially outsource the components. They carry out the important finishing operations in-house. Due to this practice, many micro to medium scale gear manufacturers have emerged as sub-contractors to different automobile manufacturing organizations. There is a high amount of competition among different gear manufacturers. To survive the competition any gear manufacturer must focus on the three major aspects: cost, quality and delivery. The focus in this study is on the delivery aspect. Precisely, this thesis attempts to address the scheduling problems in automobile gear manufacturing by proposing efficient solution methodologies in order to aid the gear manufacturers in the delivery of orders in the form of semi-finished gears, to the customers (i.e. automobile manufacturing organizations). The automobile gear manufacturing process can be broadly divided into three distinct stages, starting from the machining of the gear blanks. These three stages in automobile gear manufacturing are: pre heat treatment (pre-HT), heat treatment (HT) and post heat treatment (post-HT). Out of these three stages, the gear manufacturers carry out the first two stages namely pre-HT and HT, and deliver the semi-finished gears to the automobile manufacturing organizations. As most of the operations are carried out by the gear manufacturers, the real research problem lies in identifying bottleneck operations in both pre-HT and HT stages. By addressing the bottleneck operations, one can expect to have a competitive advantage among the gear manufacturers and in turn among the automobile manufacturing organizations. Since every gear manufacturer is involved in both: the pre-HT stage and the HT stage of gear manufacturing, they will always try to achieve both: throughput (from their own company’s perspective) and due date compliance (from the customer’s i.e. automobile manufacturing organizations’ perspective). In order to meet these two objectives for the gear manufacturer, there are two research problems identified in this thesis based on the bottleneck operations: one at the pre-HT stage and the other at the HT stage. The Research Problem 1, identified in the pre HT stage consists of a variety of machining operations. In all the pre-HT operations, one single gear is processed on a machine at a time. The machines used in these operations are essentially the discrete processors as known in the scheduling literature. Among the different operations carried out in the pre-HT stage, the gear shaving operation is the final operation which takes a relatively longer processing time compared to other operations in this stage. Hence this operation becomes the bottleneck operation and the Research Problem 1 is related to this operation. Normally, there are more than one machines available for carrying out the gear shaving operations. The processing time of a job is independent of the type of machine used (identical parallel machines). However, since automobile gears vary widely in terms of size, all the available machines may not be able to process a given job (machine eligibility restrictions). The jobs are made available for processing as and when the job orders are received from the automobile manufacturing organizations. Thus all the jobs may not be available for processing at the same time (unequal release times or dynamic job arrivals). After a job is completed on a machine, a setup is incurred before processing the next job. The setup operations involve cleaning of the machine, changing of cutting tools and toolings, setting of the machining parameters and fine tuning of the machining parameters. The amount of time required for the setup depends on both, the job that has been completed and the job that is to be processed (sequence dependent setup time). Different jobs will have different priorities depending on the nature of the job order, monetary value of the job and urgency for the next stage (job weights). Since the pre-HT stage is an upstream stage in gear manufacturing, particularly to the heat treatment (HT) stage, the aim of this stage will be to feed the downstream stage as quickly as possible. Hence, a completion time based scheduling objective is considered. Since the release times of jobs are unequal, the flowtime of a job is of interest in determining the throughput. Also, since the jobs have different weights, the weighted flowtime is of significance. Therefore, the scheduling objective for Research Problem 1 is taken as minimizing the total weighted flowtime of the jobs in a scheduling window. A vast amount of literature is available on scheduling of parallel machines. However, to the best of our knowledge, no study has simultaneously addressed the job characteristics: unequal release times, sequence dependent setup times and machine eligibility restrictions for identical parallel machines to minimize the total weighted flowtime. The Research Problem 2 was identified at the HT stage of gear manufacturing. The aim of the HT stage in the metallurgical terms is to achieve case hardening of gears. The types of machines used in the HT stage are essentially the batch processing machines (BPM) or simply batch processors (BP). A BP unlike the discrete processor, can process several different jobs at a time. The constituent jobs that are processed together form a batch in the BP. The different operations of this stage are: hardening and soaking, quenching, tempering and shot blasting. The hardening and soaking operation typically takes a longer processing time (6-18 hours) as compared to the other operations (15 minutes to 90 minutes). Also, being the first operation of the HT stage, once the hardening and soaking operation is completed, the other operations can be streamlined. Hence the scheduling of this bottleneck operation is of managerial importance. The jobs arrive at the hardening and soaking operation as and when they are completed at the pre-HT stage (unequal release times). Different jobs may have different processing requirements corresponding to time and temperature setting. Therefore, although a BP can process multiple jobs at a time, jobs with different processing requirements cannot be processed together. Jobs that can be processed together are grouped in job families. Since jobs of different families cannot be processed together we get the situation of incompatible job families. The BP has a fixed and finite capacity (expressed in terms of mass). Jobs will have different masses – which represents the size of jobs (non-identical job sizes). While constructing a batch, a job can be split in case there is a capacity violation for the BP (job splitting). The same priorities of the jobs (job weights) as in the pre-HT stage, will continue in this stage as well. As the Research Problem 2 deals with downstream stage of the gear manufacturing the objective of scheduling will be efficient delivery of the job to the automobile manufacturing organizations. The non-conformance to the due date will result in tardiness of the job. Also, since the jobs have different weights, the weighted tardiness of a job is of significance. Therefore, the scheduling objective for Research Problem 2 is taken as minimizing the total weighted tardiness (TWT) of the jobs in a scheduling window. Compared to the discrete processors, the scheduling of batch processors is a relatively new field (about two decades old). However, a review of literature reveals that no study has simultaneously addressed in any problem domain, the characteristics: unequal release times, incompatible job families, non-identical job sizes and job splitting for scheduling batch processors to minimize the total weighted tardiness. For Research Problem 1, an integer linear programming (ILP) model is developed. A suitable numerical example is developed and the workability of the proposed ILP model is validated for a small sized problem. The computational intractability of the proposed ILP model is verified empirically. Due to the computational intractability, real life large-size problems cannot be solved using the proposed ILP model. This has motivated us to propose simple heuristic algorithms. Accordingly, ten heuristic algorithms are proposed. Out of these ten proposed heuristic algorithms, five heuristic algorithms allow the use of unforced idleness and the remaining five heuristic algorithms do not allow the use of unforced idleness. In scheduling, unforced idleness is a situation when a machine is kept idle even if there are jobs available for processing. In order to understand the performance of the proposed heuristic algorithms, various factors that can affect the performance of the heuristic algorithms are identified based on the literature as well as based on the knowledge gained from the industry. An experimental design is developed based on the identified factors with different levels. A series of computational experiments has been conducted for absolute evaluation of the heuristic algorithms: (a) in comparison with optimal solution for small size problem instances (there are 96 problem instances) and (b) in comparison with the estimated optimal solution for large size problem instances (there are 2880 problem instances). The evaluation is based on computational time and the quality of the solution. With respect to the computational time, it is observed that the time required for obtaining results from the heuristic algorithms is meager. For evaluating the quality of the solution, the two standard performance measures – Average Relative Percentage Deviation (ARPD) which indicates the average performance of the proposed heuristic algorithms and Maximum Relative Percentage Deviation (MRPD) which indicates the worst case performance of the proposed heuristic algorithms have been used. From the results of the experimental evaluation it is observed that the heuristic algorithms incorporating the information on machine eligibility restrictions along with other job characteristics worked relatively better compared to other proposed heuristic algorithms. It is also observed that system congestion plays an important role in determining the performance of the heuristic algorithms. Hence, a further study based on the effect of system congestion on different heuristic algorithms is carried out. The system congestion effect was controlled using the two problem factors: number of jobs and release time of jobs. The computational experiments were based on a total of 48 problem instances. Based on the results it was inferred that for congested systems, the proposed heuristic algorithms allowing unforced idleness perform better than the corresponding heuristic algorithms not allowing unforced idleness. For Research Problem 2, two situations are examined. The first situation pertains to the micro and small scale gear manufacturers. In this case, the gear manufacturers can have a single batch processor (BP) for the operation: hardening and soaking. The other situation pertains to small and medium scale gear manufacturers, and in this case, there are more than one batch processors with possibly different capacities (multiple non-identical batch processors). For the Research Problem 2 with single BP, an ILP model is developed. A suitable numerical example is developed and the workability of the proposed ILP model is validated for a small sized problem. The computational intractability of the proposed ILP model is verified empirically. Due to the computational intractability it is proposed to develop simple heuristic algorithms. Based on the pilot experimental analysis and based on the fact that allowing unforced idleness gave superior results in case of Research Problem 1, it is decided to incorporate unforced idleness while developing heuristic algorithms for the Research Problem 2 with single BP. Accordingly, three groups of heuristic algorithms are proposed for Research Problem 2 with single BP by allowing unforced idleness – (i) Seven variants of the heuristic algorithms are based on the computation of the weighted tardiness, (ii) Three variants of the heuristic algorithms based on computation of the composite job scores and (iii) Three variants of the heuristic algorithms based on the computation of composite family scores followed by the composite job scores. For evaluating the performance of the thirteen proposed heuristic algorithms various factors that can affect the workability of the heuristic algorithms are identified based on the literature as well as based on the knowledge gained from the industry. An experimental design is developed based on these factors with levels. A series of computational experiments has been conducted for absolute evaluation of the heuristic algorithms: (a) in comparison with optimal solution for small size problem instances (192 problem instances) and (b) in comparison with the estimated optimal solution for large size problem instances (7680 problem instances). The evaluation is based on computational time and the quality of the solution. With respect to the computational time, it is observed that the time required for obtaining results from the heuristic algorithms is meager. For evaluating the quality of the solution, the two standard performance measures – ARPD and MRPD, used in Research Problem 1, could not be used here due to the nature of the scheduling objective: minimizing the TWT (as the TWT tends to zero). Therefore, a suitable performance measure was identified in the literature and suitably modified for the Research Problem 2 with single BP under study. This performance measure gives stable results even when the TWT value approaches zero. From the results of the experimental evaluation it is observed that variants of heuristic algorithms based on accommodation of non-consecutive jobs while batch construction, perform better than the other variants of the heuristic algorithms. Following the research study on single BP sitaution, the multiple non-identical BPs situation of Research Problem 2 is studied. The ILP model proposed for the Research Problem 2 with single BP problem is suitably extended to account for multiple non-identical BPs and the workability of the model is demonstrated. Additionally, the proposed heuristic algorithms for the Research Problem 2 with single BP problem have been suitably modified for the multiple non-identical BP situation. After developing a suitable experimental design for Research Problem 2 with multiple non-identical BPs, a series of computational experiments has been conducted for absolute evaluation of the heuristic algorithms in comparison with the estimated optimal solution for large size problem instances, based on the 7680 problem instances. Similar performance measure as that used in the Research Problem 2 with single BP problem is used. The observations made from the experimental evaluation for the Research Problem 2 with multiple non-identical BPs are similar to and therefore consistent with those made for the Research Problem 2 with single BP problem. Finally, a sensitivity analysis to determine the effect of capacity of batch processor sets (BP sets) in terms of: number of batch processors and capacities of each batch processor, for Research Problem 2, is carried out. That is, considering different combinations of the two factors: number of batch processors and capacities of each batch processor, seven different BP sets are considered for the proposed sensitivity analysis. The effect on the scheduling objective: Total Weighted Tardiness for different problem configurations is studied by conducting computational experiments. It is observed that higher net capacities of the BP sets give a proportionately better advantage as compared to lower net capacities of the BP sets. Proportionately better advantage means that the percentage of improvement observed in the scheduling objective is higher than the percentage increase in the net capacity of the BP set. Another observation made is that for a given net capacity, it is better to have multiple BPs with smaller capacities than a single BP with high capacity. Although the problems pertaining to the gear manufacturing process simultaneously considering many real life situations have been addressed in this study, there are some limitations to it such as addressing of identical parallel machines instead of a general case of unrelated parallel machines (for Research Problem 1) and consideration of only deterministic situations for both the research problems. There are many immediate future research directions for the problem studied in this thesis such as overcoming the limitations mentioned in this study, proposing good lower bounds and additional heuristic algorithms, and coming up with integrating both, Research Problem 1 and Research Problem 2 and proposing solution methodologies for the integrated problem.

The central thesis of this dissertation is that by combining classical scheduling methodologies with those of inventory management and queueing theory we can better model, understand and solve complex real-world scheduling problems. In part II of this dissertation, we provide models of a realistic supply chain scheduling problem that capture both its combinatorial nature and its dependence on inventory availability. We present an extensive empirical evaluation of how well implementations of these models in commercially available software solve the problem. We are therefore able to address, within a specific problem, the need for scheduling to take into account related decision-making processes. In order to simultaneously deal with combinatorial and dynamic properties of real scheduling problems, in part III we propose to integrate queueing theory and deterministic scheduling. Firstly, by reviewing the queueing theory literature that deals with dynamic resource allocation and sequencing and outlining numerous future work directions, we build a strong foundation for the investigation of the integration of queueing theory and scheduling. Subsequently, we demonstrate that integration can take place on three levels: conceptual, theoretical and algorithmic. At the conceptual level, we combine concepts, ideas and problem settings from the two areas, showing that such combinations provide insights into the trade-off between long-run and short-run objectives. Next, we show that theoretical integration of queueing and scheduling can lead to long-run performance guarantees for scheduling algorithms that have previously been proved only for queueing policies. In particular, we are the first to prove, in two flow shop environments, the stability of a scheduling method that is based on the traditional scheduling literature and utilizes processing time information to make sequencing decisions. Finally, to address the algorithmic level of integration, we present, in an extensive future work chapter, one general approach for creating hybrid queueing/scheduling algorithms. To our knowledge, this dissertation is the first work that builds a framework for integrating queueing theory and scheduling. Motivated by characteristics of real problems, this dissertation takes a step toward extending scheduling research beyond traditional assumptions and addressing more realistic scheduling problems.

The central thesis of this dissertation is that by combining classical scheduling methodologies with those of inventory management and queueing theory we can better model, understand and solve complex real-world scheduling problems. In part II of this dissertation, we provide models of a realistic supply chain scheduling problem that capture both its combinatorial nature and its dependence on inventory availability. We present an extensive empirical evaluation of how well implementations of these models in commercially available software solve the problem. We are therefore able to address, within a specific problem, the need for scheduling to take into account related decision-making processes. In order to simultaneously deal with combinatorial and dynamic properties of real scheduling problems, in part III we propose to integrate queueing theory and deterministic scheduling. Firstly, by reviewing the queueing theory literature that deals with dynamic resource allocation and sequencing and outlining numerous future work directions, we build a strong foundation for the investigation of the integration of queueing theory and scheduling. Subsequently, we demonstrate that integration can take place on three levels: conceptual, theoretical and algorithmic. At the conceptual level, we combine concepts, ideas and problem settings from the two areas, showing that such combinations provide insights into the trade-off between long-run and short-run objectives. Next, we show that theoretical integration of queueing and scheduling can lead to long-run performance guarantees for scheduling algorithms that have previously been proved only for queueing policies. In particular, we are the first to prove, in two flow shop environments, the stability of a scheduling method that is based on the traditional scheduling literature and utilizes processing time information to make sequencing decisions. Finally, to address the algorithmic level of integration, we present, in an extensive future work chapter, one general approach for creating hybrid queueing/scheduling algorithms. To our knowledge, this dissertation is the first work that builds a framework for integrating queueing theory and scheduling. Motivated by characteristics of real problems, this dissertation takes a step toward extending scheduling research beyond traditional assumptions and addressing more realistic scheduling problems.

Les enjeux du développement durable, le réchauffement climatique, la pollution dans les grandes villes, la congestion et les nuisances sonores, l'augmentation des prix de carburants, sont parmi des nombreux facteurs qui incitent les pays développés à l'innovation dans les transports publics. Dans ce contexte, l'introduction des systèmes de vélos en libre-service, au cours de ces dernières années, est une des solutions adoptées par de nombreuses grandes villes. Malgré leur succès fulgurant dans le monde entier, il existe peu d'études fondamentales sur ce type transport urbain. Pourtant, leur exploitation et leur management par des opérateurs soulèvent de nombreuses questions notamment d'ordre opérationnel. Dans ce contexte, cette thèse s'adresse aux problèmes d'ordonnancement et de rééquilibrage des stations de vélos en libre-service. Ce sont des problèmes cruciaux pour la qualité de service et la viabilité économique de tels systèmes. Le rééquilibrage consiste à redistribuer le nombre de vélos entre les différentes stations afin de satisfaire au mieux les demandes des usagers. Cette régulation se fait souvent par le biais de véhicules spécifiques qui font des tournées autour des différentes stations. Ainsi, deux problèmes d'optimisation difficiles se posent : la recherche de la meilleure tournée du véhicule de régulation (ordonnancement de la tournée) et la détermination des nombres de véhicules à utiliser (rééquilibrage des stations). Dans cette optique, les travaux de cette thèse constituent une contribution à la modélisation et à l'optimisation de performances des systèmes de vélos en libre-service en vue de leur rééquilibrage et leur ordonnancement. Plusieurs méthodes d'optimisation et ont été développées et testées. De telles méthodes incorporent différentes approches de simulation ou d'optimisation comme les réseaux de Petri, les algorithmes génétiques, les algorithmes gloutons, les algorithmes de recherche par voisinage, la méthode arborescente de branch-and-bound, l'élaboration des bornes supérieures et inférieures, etc. Différentes facettes du problème ont été étudiées : le cas statique, le cas dynamique, l'ordonnancement et le rééquilibrage avec un seul (ou multiple) véhicule(s). Afin de montrer la pertinence de nos approches, la thèse comporte également plusieurs applications réelles et expérimentations / In our days, developed countries have to face many public transport problems, including traffic congestion, air pollution, global oil prices and global warming. In this context, Public Bike sharing systems are one of the solutions that have been recently implemented in many big cities around the world. Despite their apparent success, the exploitation and management of such transportation systems imply crucial operational challenges that confronting the operators while few scientific works are available to support such complex dynamical systems. In this context, this thesis addresses the scheduling and balancing in public bicycle-sharing systems. These problems are the most crucial questions for their operational efficiency and economic viability. Bike sharing systems are balanced by distributing bicycles from one station to another. This procedure is generally ensured by using specific redistribution vehicles. Therefore, two hard optimization problems can be considered: finding a best tour for the redistribution vehicles (scheduling) and the determination of the numbers of bicycles to be assigned and of the vehicles to be used (balancing of the stations). In this context, this thesis constitutes a contribution to modelling and optimizing the bicycle sharing systems' performances in order to ensure a coherent scheduling and balancing strategies. Several optimization methods have been proposed and tested. Such methods incorporate different approaches of simulation or optimization like the Petri nets, the genetic algorithms, the greedy search algorithms, the local search algorithms, the arborescent branch-and-bound algorithms, the elaboration of upper and lower bounds, ... Different variants of the problem have been studied: the static mode, the dynamic mode, the scheduling and the balancing by using a single or multiple vehicle(s). In order to demonstrate the coherence and the suitability of our approaches, the thesis contains several real applications and experimentations