Publication Date

2019

Document Type

Dissertation/Thesis

First Advisor

Damodaran, Purushothaman

Degree Name

M.S. (Master of Science)

Legacy Department

Department of Industrial and Systems Engineering

Abstract

This research considers a scheduling problem where jobs need to be grouped into batches and the batches need to be scheduled on parallel batch processing machines with an objective to minimize the total number of tardy jobs. The jobs are assigned to batches in such a way that machine capacity is not violated. This research considers jobs with unequal ready times, unequal processing times and unequal sizes. The machines are identical in processing capabilities; however, their capacities are different. This research aims to develop effective solution approaches to solve the problem under study. A Mixed Integer Linear Programming (MILP) model is developed to find the optimal solution. However, the problem under study is NP-hard and commercial solvers require prohibitively long computational times and thus two heuristic approaches: Column Generation and Simulated Annealing are proposed.

The Column Generation (CG) approach is developed in IBM’s ILOG CPLEX and Simulated Annealing (SA) approach is developed in MATLAB. CG uses decomposition technique to decompose the main problem (MILP) into a master problem and sub-problem(s) and iteratively solve sub-problem(s) to generate feasible columns that improve the objective function. SA is a local search method and mimics the annealing process in a heat treatment operation. Unlike other heuristics, SA accepts some non-improving solutions based on some probability function to avoid being trapped in local optima.

A total of 810 instances of jobs with varying ready times, processing times, sizes, and due-dates were experimented using the exact solution method (or MILP model in commercial solver), CG and SA. The experimental results show that the CG outperforms the commercial solver on instances with 150 jobs or more in both - two machines and three machines configurations, while SA outperforms the commercial solver on instances with 100 jobs or more in two machines configuration and 150 jobs or more in three machines configuration. Furthermore, the computational experiments also show that the SA approach provided considerable time savings for solving every job instance.

Extent

85 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