Tese de Tadeu Knewitz Zubaran

Aluno: Tadeu Knewitz Zubaran
Orientador: Prof. Dr. Marcus Rolf Peter Ritt

Título: A Study on Shop Scheduling Problems
Linha de Pesquisa: Fundamentos da Computação
 
Data: 09/03/2018
Horário: 13h30min.
Local: Prédio 43412 – Sala 215 (sala de videoconferência), Instituto de Informática

Banca Examinadora:
Profa. Dra. Luciana Salete Buriol (UFRGS)
Prof. Dr. Olinto César Bassi de Araújo (UFSM)
Profa. Dra. Denise Lindstrom Bandeira (EA/UFRGS)

Presidente da Banca: Prof. Dr. Marcus Rolf Peter Ritt
Abstract: Shop scheduling is a combinatorial optimization type of problem in which we must allocate machines to jobs for specific periods time. A set of constraints defines which schedules are valid, and we must select one that minimizes or maximizes an objective function. In this work we use the makespan, which is the time the last job finishes.The literature contains several studies proposing techniques to solve shop models such as the job shop and open shop. These models allow the steps of the production processes to be either fully ordered or not ordered at all. With increasing complexity and size of industrial applications we find, more recently, several works which propose more general shop problems to model the production processes more accurately. The mixed shop, group shop and partial shop are examples of such models. In this work we propose an iterated tabu search for the partial shop, which is a general model and includes several other more restrictive shop models. The most important novel components of the solver are the initial solution generator, the neighbourhood, and the lower bound for the neighbourhood. In computational experiments we were able to show that the general partial shop solver is able to compete with, and sometimes surpass, the state-of-the-art solvers developed specifically for the partial, open, mixed and group shops. Sometimes a machine is a bottleneck in the production process, and is replicated. In the literature the parallel machines case has being included in several extensions of shop problems. In this thesis we also propose a technique to schedule the parallel machines heuristically, without including them explicitly in the representation of the problem. We use general techniques for the non-parallel machine cases to produce a fast tabu search heuristic results for the job shop with parallel machines.
Keywords: Shop Scheduling. Heuristics. Tabu Search. Iterated Greedy. Partial Order. Parallel Machines.