Minimizing total number of tardy jobs in two-stage flow shop using simulated annealing and column generation

Committee members: Nguyen, Christine; Wang, Ziteng.Advisor: Damodaran, Purushothaman.Includes illustrations.Includes bibliographical references.This research considers a scheduling problem where jobs need to be grouped in batches and scheduled in a two-stage flow shop with batch processing machines. The jobs are batched in such a way that machine capacity is not violated. The batches are scheduled in such a way to reduce the total number of tardy jobs. The problem under study, denoted as F2 | Batch | [Sigma]U[sub i] in scheduling literature, has received less attention. The problem under study is NP-hard. Consequently, commercial solvers used to solve mathematical formulations to find an optimal solution require prohibitively long run times. In this thesis, two solution approaches are proposed and their effectiveness are evaluated by comparing its performance with a commercial solver and a meta-heuristic (GRASP). A Column Generation (CG) approach is developed in IBM's ILOG CPLEX and Simulated Annealing (SA) approach is developed in Matlab to solve the problem. CG is an iterative algorithm used to solve large linear problems efficiently. SA is a local search algorithm which simulates the annealing process in a heat treatment operation. Two hundred and forty instances of jobs with varying sizes, processing times and due date are solved using the two approaches. The solution is compared to available solution in literature to determine the effectiveness in terms of solution quality and computation time. After comparing the solutions, it is observed that CG and SA outperform commercial solver on larger instances (100+ jobs) both in terms of solution quality and computation time. CG and SA also provided considerable time saving for larger job instances as opposed to GRASP.M.S. (Master of Science