Publication Date

2017

Document Type

Dissertation/Thesis

First Advisor

Damodaran, Purushothaman

Degree Name

M.S. (Master of Science)

Legacy Department

Department of Industrial and Systems Engineering

LCSH

Industrial engineering

Abstract

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.

Comments

Advisors: Purushothaman Damodaran.||Committee members: Murali Krishnamurthi; Christine Nguyen; Ziteng Wang.||Includes bibliographical references.||Includes illustrations.

Extent

viii, 74 pages

Language

eng

Publisher

Northern Illinois University

Rights Statement

In Copyright

Rights Statement 2

NIU theses are protected by copyright. They may be viewed from Huskie Commons for any purpose, but reproduction or distribution in any format is prohibited without the written permission of the authors.

Media Type

Text

Download

Share

COinS