| In this dissertation we do a computational study of different methods to solve two scheduling problems: the job-shop and the flow-shop scheduling problems. In both problems we are given a set of jobs to be scheduled on a set of machines. The objective is to schedule the jobs on the machines so that we minimize the time by which all jobs are completed. These problems have been widely studied and various techniques have been used to solve them. In particular, the job-shop scheduling problem is notorious in the field of Operations Research for its intractability.; This dissertation is organized as follows. In Chapter 1, we define in detail both problems and present a literature review.; In Chapter 2, we review the branch-and-bound methods for the job-shop scheduling problem, with emphasis on the methods to obtaining lower bounds for this problem. Also, we propose a new method to obtain a lower bound for this scheduling problem that in theory is stronger than the previous known lower bounds which are obtained by solving a certain one-machine scheduling problem. We present computational results for some instances of the job-shop scheduling problem when this new lower bound is used.; In Chapter 3, we consider several approximation methods to solve the job-shop scheduling problem. We focus on local optimization methods, reviewing the application of the techniques known as local improvement and simulated annealing to this problem. We propose a variant of the above local optimization methods, known as large-step optimization, to solve the job-shop scheduling problem. We present computational results obtained from the application of all these methods to several instances of the problem. From the computational results we can conclude that the local improvement method is clearly inferior, even when several trials are performed. The large-step optimization methods outperformed the simulated annealing method, but the difference between these two became closer when the same amount of time was allowed for both. In many cases, the large-step optimization methods found an optimal schedule and in others the distance from the optimum or lower bound was small.; In Chapter 4, we consider the flow-shop scheduling problem, and we study and implement different versions of Sevast'yanov's algorithm, based on linear programming. Using Cplex, we did computational tests with random instances having up to 1000 jobs and 100 machines. If the size of the flow-shop scheduling problem is small or if the running time is not a critical factor, the Nawaz, Enscore and Ham approximation algorithm still performs better. But if the running time is an important factor, Sevast'yanov's algorithm can be a very good alternative especially in presence of very large scale instances with a relatively small number of machines. |
