Minimizing the total completion time in scheduling problems with sequence dependent setup times

Objectives and study method: The main goal of this thesis work is to develop tools to solve some scheduling problems obtaining quality solutions in an efficient way, reaching improvements in the production times. This work is dedicated to solving two kinds of scheduling problems. The first problem consists in giving a schedule for a set of jobs that should be processed in a set of machines. The term sequence dependent setup times means that the necessary time to get ready all the necessary to process a certain job depends on the job just performed. The second problem is actually four problems analyzed in two environments, and they are the single and parallel machine scheduling problem with learning and deterioration effects over sequence dependent setup times. The addressed method in both cases is, firstly, developing a mathematical formulation for each one able to obtain optimal solutions and verify its scope. Secondly, it is designed and developed a heuristic algorithm that provides good solutions in short periods of time, for the first problem. Contributions and conclusions: For the first problem, the computational experiments showed that time-dependent based formulations performed much better than the classic formulations and for the heuristic algorithm, this one has a better performance than the founded in the literature. Regarding to the second problem, in this work we present the first mathematical formulation for the case with learning and deterioration effects overs the sequence dependent setup times.