Abstract: This dissertation addresses the optimization of the flowshop scheduling problem with sequence-dependent setup times. The goal of the decision-maker is to provide a schedule that minimizes the time at which all jobs in the system are processed. The goal of this work is to provide the decision-maker with efficient ways of deriving such schedules. This type of problem arises in many manufacturing environments. In the printing industry, for example, presses must be cleaned and settings changed when ink color, paper size or receiving medium differ from one job to the next. Setup times are strongly dependent on the job order. In the container manufacturing industry machines must be adjusted whenever the dimensions of the containers are changed, while in printed circuit board assembly, rearranging and restocking component inventories on the magazine rack is required between batches. In each of these situations, sequence-dependent setup times play a major role and must be considered explicitly when modeling the problem.
This research includes the implementation of heuristic approaches to obtain feasible solutions of high quality, the development of lower bounding procedures, the study of the set of feasible solutions from the polyhedral perspective, and the integration of all of these components into exact optimization schemes. The first is based on branch and cut and the second on branch and bound. The proposed procedures are found to be very effective, providing good approximations of the true optimal to a large class of data instances, and optimal solutions in other cases.
Another contribution of this work is the development of a technique to randomly generate data instances with real-world attributes.