Heuristicas para a minimização dos atrasos em sequenciamento de maquinas paralelas com tempos de preparação dependentes da sequência

Abstract

Abstract Consider the problem of scheduling a set of jobs to be processed exactly once, on any machine of a set of unrelated parallel machines, without preemption. Each job has a due date, weight, and, for eachmachine, an associated processing time and sequence-dependent setup time. Throughout this work,the objective function considered is to minimize the total weighted tardiness of the jobs, but otherobjectives, such as the minimization of the makespan and the minimization of the total slackness, are also discussed.Initially, this work proposes and analyses efficient implementations of several local search based heuristics to tackle the problem. Aspects such as the algorithms' design and implementation aspectsare discussed. Then, the proposed heuristics are compared with other successful implementations, to highlight their advantages in terms of quality and computation time, specially for large instances.In order to measure the quality of the proposed solutions, their objective function values are compared to lower bounds of the problem. These bounds are obtained by a Non-Delayed Relax-and-Cut algorithm, based on a lagrangean relaxation of a time indexed formulation of the problem. It isalso used to develop a lagrangean heuristic, to obtain approximate solutions.To achieve maximum performance and memory saving, thus allowing to tackle large instances,the developed algorithms do not rely on third party solvers.Good solutions for instances with up to six machines and 200 jobs, and lower bounds for instan-ces with up to six machines and 80 jobs, were obtained within reasonable time. The obtained lowerbounds were particularly good for easy instances, proving the optimality of some solutions and pro-viding tight gaps for others. For more difficult instances, the obtained lower bounds were not so goodbut still significant.