In this thesis, we consider a rescheduling problem on non-identical parallel machines with controllable processing times. A period of unavailability occurs on one of the machines due to a machine failure, material shortage or broken tool. These disruptions may cause the original schedule to become inecient and sometimes infeasible. In order to generate a new and feasible schedule, we are dealing with two conflicting measures called the eciency and stability measures simultaneously. The eciency measure evaluates the satisfaction of a desired objective function value and the stability measure evaluates the amount of change between the schedule before and after the disruption. In this study, we measure stability by the number of disrupted jobs. In this thesis, the job is referred as a disrupted job if it completes processing after its planned completion time in the original schedule. The eciency is measured by the additional manufacturing cost of jobs. Decreasing number of disrupted jobs requires compressing the processing time of a job which cause an increase in its additional manufacturing cost. For that reason we cannot minimize these objectives at the same time. In order to handle this, we developed a mixed integer programming model for the considered problem by applying the epsilon-constraint approach. This approach makes focusing on the single objective possible to get efficient solutions. Therefore, we studied the problem of minimizing additional manufacturing cost subject to a limit on the number of disrupted jobs. We also considered a convex compression cost function for each job and solved a cost minimization problem by applying conic quadratic reformulation for the model. The convexity of cost functions is a major source of diculty in finding optimal integer solutions in this problem, but applying strengthened conic reformulation has eliminated this diculty. In addition, we prepare an improvement search algorithm in order to find good solution in reasonable CPU times. We use our heuristic procedure on optimality properties we showed for a single machine subproblem. We made computational experiments on small and medium scale test problems. Afterwards, we compare the performance of the improvement search algorithm and mathematical model for their solution quality and durations.

Simultaneous lot-sizing and scheduling problem is the problem to decide what products to be produced on which machine and in which order, as well as the quantity of each product. Problems of this type are hard to solve. Therefore, they were studied for years, and a considerable number of papers is published to solve different lotsizing and scheduling problems, specifically real-case problems. This work proposes a Real-Coded Genetic Algorithm (RCGA) with a new chromosome representation to solve a non-identical parallel machine capacitated lot-sizing and scheduling problem with sequence dependent setup times and costs, machine cost and backlogging. Such a problem can be found in real world production line at furniture manufacturer in Sweden. Backlogging is an important concept in this problem, and it is often ignored in the literature. This study implements three different types of crossover; one of them has been chosen based on numerical experiments. Four mutation operators have been combined together to allow the genetic algorithm to scan the search area and maintain genetic diversity. Other steps like initializing of the population and a reinitializing process have been designed carefully to achieve the best performance and to prevent the algorithm from trapped into the local optimum. The proposed algorithm is implemented and coded in MATLAB and tested for a set of standard medium to large-size problems taken from the literature. A variety of problems were solved to measure the impact of different characteristics of problems such as the number of periods, machines, and products on the quality of the solution provided by the proposed RCGA. To evaluate the performance of the proposed algorithm, the average deviation from the lower bound and runtime for the proposed RCGA are compared with three other algorithms from the literature. The results show that, in addition to its high computational speed, the proposed RCGA outperforms the other algorithms for non-identical parallel machine problems, while it is outperformed by the other algorithms for problems with the more identical parallel machine. The results show that the different characteristics of problem instances, like increasing setup cost, and size of the problem influence the quality of the solutions provided by the proposed RCGA negatively.

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.