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.

Submitted by Elton Lever (elton@icomp.ufam.edu.br) on 2018-08-23T20:26:01Z No. of bitstreams: 1 DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5) / Approved for entry into archive by Secretaria PPGI (secretariappgi@icomp.ufam.edu.br) on 2018-08-23T20:35:20Z (GMT) No. of bitstreams: 1 DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-08-24T13:35:27Z (GMT) No. of bitstreams: 1 DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5) / Made available in DSpace on 2018-08-24T13:35:28Z (GMT). No. of bitstreams: 1 DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5) Previous issue date: 2017-06-22 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This dissertation addresses the class of job scheduling problems with precedence constraints and unit execution times, in identical parallel processors. Such a class of problems is of great importance in computational complexity theory, since small varia- tions in the conditions involved in scheduling make an easy problem very difficult. Two major problems involve the condition of the number of processors, where, if the number of processors is variable, given as input, such problem is proved to be NP-complete, but if the number of processors is fixed, the problem is still open. In this context, the focus of the research involves the problem already proven to be NP-complete, where for which we investigated the main approximation algorithms in the literature and their proofs of approximation ratio of the optimal, such as of the Garey & Jonhson’s 2-approximation algorithm, of the Hu, of the Coffman & Graham, and of the Gangal & Ranade with 2 − (7/(3P + 1)), the best approximation ratio in the literature. The approximation ratio proofs of such algorithms were detailed. As the main contribution of this research, were proved the optimality for specific classes of acyclic directed graphs involving trees (prece- dence trees, such as in-tree and out-tree) for the best approximation algorithms literature. / Esta dissertação aborda a classe de problemas de escalonamento de tarefas com restrições de precedências e tempos unitários em processadores paralelos idênticos. Tal classe de problemas tem uma grande importância em teoria da complexidade computacional, uma vez que pequenas variações nas condições envolvidas no esca- lonamento, fazem com que um problema fácil se torne muito difícil. Dois grandes problemas envolvem a condição do número de processadores, onde, se o número de processadores for variável, dado como entrada, tal problema é provado ser NP-completo, mas, se o número de processadores for fixo, o problema ainda está em aberto. Neste contexto, o foco da pesquisa envolve o problema já provado ser NP-completo, onde para qual se investigou os principais algoritmos aproximativos existentes na literatura e suas provas de razão de aproximação do ótimo, tais como o algoritmo 2-aproximativo de Garey & Jonhson e as melhorias de Hu, Coffman & Graham e de Gangal & Ranade (GR) com 2 −(7/(3P+1)), o de melhor razão de aproximação da literatura. As provas de razão de aproximação de tais algoritmos foram detalhadas. Como principal contribuição da pesquisa, foram determinados casos especiais ótimos, para classes específicas de grafos direcionados acíclicos que envolvem arborescências (árvores de precedência, como in-tree e out-tree) para o melhor algoritmos aproximativo da literatura. / Compreender o que querem em alguns momentos.

In this thesis we have tackled a few scheduling problems under energy constraint, since the energy issue is becoming crucial, for both economical and environmental reasons. In the first chapter, we exhibit tight bounds on the energy metric of a classical algorithm that minimizes the makespan of independent tasks. In the second chapter, we schedule several independent but concurrent pipelined applications and address problems combining multiple criteria, which are period, latency and energy. We perform an exhaustive complexity study and describe the performance of new heuristics. In the third chapter, we study the replica placement problem in a tree network. We try to minimize the energy consumption in a dynamic frame. After a complexity study, we confirm the quality of our heuristics through a complete set of simulations. In the fourth chapter, we come back to streaming applications, but in the form of series-parallel graphs, and try to map them onto a chip multiprocessor. The design of a polynomial algorithm on a simple problem allows us to derive heuristics on the most general problem, whose NP-completeness has been proven. In the fifth chapter, we study energy bounds of different routing policies in chip multiprocessors, compared to the classical XY routing, and develop new routing heuristics. In the last chapter, we compare the performance of different algorithms of the literature that tackle the problem of mapping DAG applications to minimize the energy consumption.

Dans cette thèse, nous nous sommes intéressés à des problèmes d'ordonnancement sous contrainte d'énergie, puisque la réduction de l'énergie est devenue une nécessité, tant sur le plan économique qu'écologique. Dans le premier chapitre, nous exhibons des bornes strictes sur l'énergie d'un algorithme classique qui minimise le temps d'exécution de tâches indépendantes. Dans le second chapitre, nous ordonnançons plusieurs applications chaînées de type « streaming », et nous étudions des problèmes contraignant l'énergie, la période et la latence. Nous effectuons une étude de complexité exhaustive, et décrivons les performances de nouvelles heuristiques. Dans le troisième chapitre, nous étudions le problème de placement de répliques dans un réseau arborescent. Nous nous plaçons dans un cadre dynamique, et nous bornons à minimiser l'énergie. Après une étude de complexité, nous confirmons la qualité de nos heuristiques grâce à un jeu complet de simulations. Dans le quatrième chapitre, nous revenons aux applications « streaming », mais sous forme de graphes série-parallèles, et nous tentons de les placer sur un processeur multi-cœur. La découverte d'un algorithme polynomial sur un problème simple nous permet la conception d'heuristiques sur le problème le plus général dont nous avons établi la NP-complétude. Dans le cinquième chapitre, nous étudions des bornes énergétiques de politiques de routage dans des processeurs multi-cœurs, en comparaison avec le routage classique XY, et développons de nouvheuristiques de routage. Dans le dernier chapitre, nous étudions expérimentalement le placement d'applications sous forme de DAG sur des machines réelles. / In this thesis we have tackled a few scheduling problems under energy constraint, since the energy issue is becoming crucial, for both economical and environmental reasons. In the first chapter, we exhibit tight bounds on the energy metric of a classical algorithm that minimizes the makespan of independent tasks. In the second chapter, we schedule several independent but concurrent pipelined applications and address problems combining multiple criteria, which are period, latency and energy. We perform an exhaustive complexity study and describe the performance of new heuristics. In the third chapter, we study the replica placement problem in a tree network. We try to minimize the energy consumption in a dynamic frame. After a complexity study, we confirm the quality of our heuristics through a complete set of simulations. In the fourth chapter, we come back to streaming applications, but in the form of series-parallel graphs, and try to map them onto a chip multiprocessor. The design of a polynomial algorithm on a simple problem allows us to derive heuristics on the most general problem, whose NP-completeness has been proven. In the fifth chapter, we study energy bounds of different routing policies in chip multiprocessors, compared to the classical XY routing, and develop new routing heuristics. In the last chapter, we compare the performance of different algorithms of the literature that tackle the problem of mapping DAG applications to minimize the energy consumption.