M.S. (Master of Science)
Department of Industrial and Systems Engineering
This research considers the scheduling problem where a set of jobs must be grouped into batches and then scheduled on batch processing machines in a two-stage flowshop. The jobs must be scheduled in such a way that the number of tardy jobs (jobs completed after their due date) is minimized. Each job has a different size, and both machines can hold multiple jobs, up to a fixed capacity. This problem has not received any attention in the literature until this point. The Greedy Randomized Adaptive Search Procedure (GRASP) meta-heuristic is proposed to solve this problem. A set of 240 data sets is generated using various numbers of jobs, processing times, job sizes, and machine capacities. Each of the data sets is solved using GRASP, and the results are compared to the solutions generated from solving the same data sets using a Mixed-Integer Linear Programming (MILP) model, which is solved in IBM's ILOG CPLEX software. The solutions from GRASP are compared to the solutions from CPLEX in order to determine the effectiveness of the GRASP algorithm. After comparing the GRASP solutions to the solutions from CPLEX, it is clear that GRASP outperforms CPLEX on large data sets (instances with 100 or more jobs). In smaller data sets, GRASP will sometimes generate equal or better solutions than CPLEX, but sometimes will generate worse solutions. It appears that the quality of the GRASP solution is affected by the sizes of the jobs in the batch and the machine capacity, but more study is needed to verify this. In all data sets with more than 10 jobs, GRASP provides significant time savings over CPLEX.
Screnock, Joshua, "Using GRASP to minimize the number of tardy jobs in a two-stage flowshop with batch processing machines" (2017). Graduate Research Theses & Dissertations. 6594.
viii, 74 pages
Northern Illinois University
Rights Statement 2