No / The Job Shop Scheduling Problem (JSSP) is a hard combinatorial optimisation problem. This paper presents a heuristic-based Genetic Algorithm (GA) or Hybrid Genetic Algorithm (HGA) with the aim of overcoming the GA deficiency of fine tuning of solution around the optimum, and to achieve optimal or near optimal solutions for benchmark JSSP. The paper also presents a detail GA parameter analysis (also called sensitivity analysis) for a wide range of benchmark problems from JSSP. The findings from the sensitivity analysis or best possible parameter combination are then used in the proposed HGA for optimal or near optimal solutions. The experimental results of the HGA for several benchmark problems are encouraging and show that HGA has achieved optimal solutions for more than 90% of the benchmark problems considered in this paper. The presented results will provide a reference for selection of GA parameters for heuristic-based GAs for JSSP.

Yes / Scheduling is an important element that has a major impact on the efficiency of all manufacturing processes. It plays an important role in optimising the manufacturing times and costs resulting in energy efficient processes. It has been estimated that more than 75% of manufacturing processes occur in small batches. In such environments, processes must be able to perform a variety of operations on a mix of different batches. Batch-job scheduling optimisation is the response to such low batch manufacturing problems. The optimisation of batch-job process scheduling problem is still a challenge to researchers and is far from being completely solved due to its combinatorial nature. In this paper, a novel hybrid heuristic (HybH) solution approach for batch-job scheduling problem is presented with the objective of optimising the overall Makespan (Cmax). The proposed HybH is the combination of Index Based Heuristic (IBH) and the Finished Batch-Job (FBJ) process schedule. The heuristic assigns the first operation to a batch-job using IBH and the remaining operations on the basis FBJ process schedule. The FBJ process schedule gives priority to the batch-job with early finished operations, without violating the constraints of process order. The proposed HybH is explained with the help of a detailed example. Several benchmark problems are solved from the literature to check the validity and effectiveness of the proposed heuristic. The presented HybH has achieved batch-job process schedules which have outperformed the traditional heuristics. The results are encouraging and show that the proposed heuristic is a valid methodology for batch process scheduling optimisation.

Les soins de santé à domicile (HHC) sont un large éventail de services de santé pouvant être dispensés à domicile pour une maladie ou une blessure. Ces dernières années, le secteur des soins de santé est devenu l'un des plus grands secteurs de l'économie des pays développés. L'un des défis les plus importants dans le domaine des HHC consiste à affecter plus efficacement les ressources en main-d'œuvre et les équipements sous des ressources limitées. Étant donné que le coût du transport est l’une des dépenses les plus critiques dans les activités de l’entreprise, il est très important d’optimiser le problème de routage des véhicules pour les sociétés HHC.Cependant, la majorité des travaux existants ne prennent en compte que le modèle déterministe. Dans la pratique de HHC, le décideur et les aidants rencontrent souvent des incertitudes. Il est donc essentiel d'intégrer l'incertitude dans le modèle pour établir un calendrier raisonnable pour la société HHC. Cette thèse aborde le problème du routage et de la planification HHC en prenant en compte respectivement la demande non déterministe, le service et le temps de parcours. Le corps principal de la thèse est composé de trois œuvres indépendantes.(1) Sur la base de la théorie de la crédibilité floue, nous avons proposé un modèle de programmation par contraintes de hasard flou (FCCP) pour le problème de routage HHC avec une demande floue. Ce modèle présente à la fois des caractéristiques d'optimisation combinatoire et de FCCP. Pour faire face au problème à grande échelle, nous avons développé un algorithme génétique hybride avec la simulation de Monte Carlo. Trois séries d'expériences ont été menées pour valider les performances du modèle et de l'algorithme proposés. Enfin, l’analyse de sensibilité a également porté sur l’observation du paramètre variable impliqué dans la prise de décision floue.(2) En fonction de l'activité des soignants de HHC, nous avons proposé un modèle de programmation stochastique en deux étapes avec recours (SPR) pour la livraison et la reprise simultanées avec des temps de trajet et de service stochastiques dans HHC. Pour résoudre le modèle, nous avons d’une part réduit le modèle au cas déterministe. Le solveur de Gurobi, le recuit simulé (SA), l’algorithme de chauve-souris, l’algorithme de luciole ont été proposés pour résoudre le modèle déterministe pour 56 instances respectivement. Enfin, le SA a été adopté pour traiter le modèle SPR. Une comparaison entre les solutions obtenues par les deux modèles a également été réalisée pour mettre en évidence la prise en compte des temps de parcours et de service stochastiques.(3) Pour garantir la qualité du service, sur la base d’un budget de la théorie de l’incertitude, nous avons proposé un modèle d’optimisation robuste (RO) pour HHC Routing, prenant en compte les exigences en termes de temps de déplacement et de service. La vérification de la solution réalisable a été réécrite en tant que fonction récursive complexe. Recherche tabou, SA, Recherche de voisinage variable sont également adaptés pour résoudre le modèle. Un grand nombre d'expériences ont été réalisées pour évaluer le modèle déterministe et le modèle RO. Une analyse de sensibilité des paramètres a également été effectuée. / Home health care (HHC) is a wide range of healthcare services that can be given in one's home for an illness or injury. In recent years, the healthcare industry has become one of the largest sectors of the economy in developed countries. One of the most significant challenges in HHC domain is to assign the labor resources and equipment more efficiently under limited resources. Since the transportation cost is one of the most critical spendings in the company activities, it is of great significance to optimize the vehicle routing problem for HHC companies.However, a majority of the existing work only considers the deterministic model. In the practical of HHC, the decision-makers and caregivers often encounter with uncertainties. So, it is essential to incorporate the uncertainty into the model to make a reasonable and robust schedule for HHC company. This thesis addresses the HHC routing and scheduling problem with taking into account the non-deterministic demand, uncertain service and travel time respectively. The main body the thesis is composed of three independent works.(1) Based on the Fuzzy Credibility Theory, we proposed a fuzzy chance constraint programming (FCCP) model for HHC routing problem with fuzzy demand. This model has both characteristics of combinatorial optimization and FCCP. To deal with the large-scale problem, we developed a Hybrid Genetic Algorithm with the Monte Carlo simulation. Three series of experiments were conducted to validate the performance of the proposed model and algorithm. At last the sensitivity analysis was also carried out the observe the variable parameter involved in the fuzzy decision-making.(2) According to the activity of the caregivers in HHC, we proposed a two-stage stochastic programming model with recourse (SPR) for the simultaneous delivery and pick-up with stochastic travel and service times in HHC. To solve the model, firstly, we reduced the model to the deterministic one. Gurobi Solver, Simulated Annealing (SA), Bat Algorithm (BA), Firefly Algorithm (FA) were proposed to solve the deterministic model for 56 instances respectively. At last the SA was adopted to address the SPR model. Comparison between the solutions obtained by the two models was also conducted to highlight the consideration of the stochastic travel and service times.(3) To guarantee the service quality, based on a budget of uncertainty theory, we proposed a Robust Optimization (RO) model for HHC Routing with considering skill requirements under travel and service times uncertainty. The feasible solution check was rewritten as a complex recursive function. Tabu Search, SA, Variable Neighborhood Search are adapted to solve the model. A large number of experiments had been performed to evaluate the deterministic model and the RO model.

Submitted by GISLAINE MARA MELEGA null (gis_laine_m@hotmail.com) on 2017-03-27T18:20:11Z No. of bitstreams: 1 TESE_Gislaine Melega_Matemática.pdf: 2710288 bytes, checksum: 9c3a4e388e7584cf0423182dcfdcced8 (MD5) / Approved for entry into archive by Luiz Galeffi (luizgaleffi@gmail.com) on 2017-03-29T19:23:05Z (GMT) No. of bitstreams: 1 melega_gm_dr_sjrp.pdf: 2710288 bytes, checksum: 9c3a4e388e7584cf0423182dcfdcced8 (MD5) / Made available in DSpace on 2017-03-29T19:23:05Z (GMT). No. of bitstreams: 1 melega_gm_dr_sjrp.pdf: 2710288 bytes, checksum: 9c3a4e388e7584cf0423182dcfdcced8 (MD5) Previous issue date: 2017-02-21 / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / Nesta tese, estamos interessados em tratar de maneira integrada dois conhecidos problemas da literatura. Esta integração é referida na literatura como problema integrado de dimensionamento de lotes e corte de estoque. A ideia consiste em considerar simultaneamente, as decisões relacionadas com ambos os problemas, de modo a capturar a interdependência entre estas decisões e, assim, obter uma melhor solução global. Propõe-se um modelo matemático geral para o problema integrado de dimensionamento de lotes e corte de estoque (GILSCS), que considera vários níveis de integração e nos permite classificar a literatura, em termos de modelos matemáticos, dos problemas integrados. A classificação é organizada a partir de dois principais aspectos de integração que são: a integração através dos períodos de tempo e a integração entre os níveis de produção. Em um horizonte de planejamento que considera vários períodos, o estoque fornece uma ligação entre os períodos. Esta integração, por períodos de tempo, constitui o primeiro tipo de integração. O problema geral também considera a produção em diferentes níveis: objetos são fabricados ou comprados e então são cortados para produzir peças menores e estas, por sua vez, constituem componentes para a produção dos produtos finais. A integração entre os diferentes níveis de produção consiste no segundo tipo de integração. A revisão da literatura também possibilita direcionar interessantes áreas para pesquisas futuras. O comportamento da solução para este tipo de problema, com três níveis e vários períodos, é estudado a partir do desenvolvimento de métodos de solução considerando abordagens que superam as dificuldades do problema, que consistem no alto número de padrões de corte, estruturas em vários níveis (multiestágios) e variáveis binárias de preparo. Os métodos de solução propostos para o problema GILSCS são baseados em duas abordagens conhecidas da literatura, usadas com sucesso para resolver os problemas separadamente, que são o procedimento de geração de colunas e heurísticas de decomposição do tipo relax-and-fix. Estas estratégias e suas variações são combinadas à um pacote de otimização em um estudo computacional com dados gerados aleatoriamente. Uma revisão da literatura, em termos de métodos de solução, para o problema integrado também é apresentada. Outras contribuições desta tese consistem em propor diferentes modelos matemáticos para o problema integrado, combinando modelos alternativos para cada um dos problemas separadamente. Neste estudo, o objetivo é comparar e avaliar, com um extensivo estudo computacional, a qualidade e o impacto das diferentes formulações. O outro trabalho trata de uma aplicação do problema integrado em um indústria de móveis de pequeno porte, em que restrições específicas do ambiente industrial são abordadas, como estoque de segurança e ciclos da serra. A solução obtida pelo modelo proposto é comparada com uma simulação da prática da empresa. / In this thesis, the subject of interest is in treating, in an integrated way, two wellknown problems in the literature. This integration is referred in the literature as the integrated lot-sizing and cutting stock problem. The basic idea is to consider, simultaneously, the decisions related to both problems so as to capture the interdependency between these decisions in order to obtain a better global solution. We propose a mathematical model for a general integrated lot-sizing and cutting stock (GILSCS) problem. This model considers multiple dimensions of integration and enables us to classify the current literature, in terms of mathematical models, in this field. The main classification of the literature is organized around two types of integration. In a planning horizon which consists of multiple periods, the inventory provides a link between the periods. This integration across time periods constitutes the first type of integration. The general problem also considers the production in different levels: objects are fabricated or purchased and then, they are cut to produce the pieces which are then assembled as components in the production of final products. The integration between these production levels constitutes the second type of integration. The literature review also enables us to point out interesting areas for future research. The behavior of a solution to this type of problem, with three levels of production and several time periods, is studied considering the development of solution approaches that overcome the difficulties of the problem, which are the high number of cutting patterns, multi-level structures and the binary values of the setup variables. The solution methods proposed to the GILSCS problem are based on two known strategies from the literature which are used successfully to solve the problems separately, which are the column generation procedure and decomposition heuristics based on relax-and-fix procedure. These strategies and their variations are combined into an optimization package in a computational study with randomly generated data. A literature review, in terms of solution methods, to the integrated problem, is also presented. Other contributions of this thesis consist of proposing different mathematical models for the integrated problem combining alternative models for each one of the problems separately. In this study, the aim is to compare and evaluate, with an extensive computational study, the quality and the impact of these dfifferent formulations. Another study is an application of the integrated problem in a small furniture factory, in which specific constraints related to the industrial environment are addressed, such as, safety stock level constraints and saw cycles constraints. The solution obtained from the proposed model is compared to a simulation of the common practice in the company. / FAPESP: 2012/20631-2