Publication Date

2018

Document Type

Dissertation/Thesis

First Advisor

Damodaran, Purushothaman

Degree Name

M.S. (Master of Science)

Legacy Department

Department of Industrial and Systems Engineering

LCSH

Engineering

Abstract

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.

Comments

Committee members: Nguyen, Christine; Wang, Ziteng.||Advisor: Damodaran, Purushothaman.||Includes illustrations.||Includes bibliographical references.

Extent

67 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