Minimizing the Total Completion Time in a Two Stage Flow Shop with a Single Setup Server
M.S. Thesis Presentation by Muhammet Kolay Department of Industrial Engineering Bilkent University
In this thesis, we study a two stage flow shop problem with a single server. All jobs are available for processing at time zero.Processing of a job is preceded by a sequence independent setup operation on both machines. The setup and processing times of all jobs on the two machines are given. All setups are performed by the same server which can perform one setup at a time. Setups cannot be performed simultaneously with job processing on the same machine. Once the setup is completed for a job, processing can automatically progress without any further need for the server. Setup for a job may start on the second machine before that job finishes its processing on the first machine. Preemption of setup or processing operations is not allowed. A job is completed when it finishes processing on the second machine.The objective is to schedule the setup and processing operations on the two machines in such a way that the total completion time is minimized. This problem is known to be strongly NP-hard. We propose a new mixed integer programming formulation for small-sized instances and Variable Neighborhood Search (VNS) mechanisms for larger problems. We also develop several lower bounds to help assess the quality of heuristic solutions on large instances for which optimum solutions are not available. Experimental resultsindicate that the proposed heuristics provide reasonably effective solutions in a variety of instances and they are very efficient in terms of computational requirements.
Keywords: machine scheduling, flow shop, single setup server, total completion time, variable neighborhood search.
This thesis is supervised by Prof. Ulku Gurler Assoc. Prof. Mehmet Taner
