Publication Date

2021

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 studies the scheduling of jobs with unequal ready times, unequal processing times, and unequal sizes on a single batch processing machine, with the objectives of minimizing makespan and maximum tardiness. For the batch process, the jobs are required to be grouped into batches and further these batches are scheduled on the machine to minimize the objectives, without violating the machine capacity. The problem under study can be denoted as 1|p-batch, sj, rj| Cmax,Tmax in the standard three-field notation. A thorough review of literature pertinent to the field of research has been conducted and two new approaches have been proposed in this research.Ghrayeb (2020) has shown this problem to be NP-hard and proposed a mathematical formulation using the weighted sum approach which was solved using IBM ILOG CPLEX. Additionally, Ghrayeb (2020) also proposed a simulated annealing (SA) and a greedy randomized adaptive search procedure (GRASP) to solve the problem for a set of 225 instances generated by varying values of job sizes, processing times, ready times, and due dates. Since the problem is NP-hard, the computational time to solve the problem under study may increase exponentially, which is not desired in real life. Therefore, a Particle Swarm Optimization (PSO) and an Ant Colony Optimization (ACO) algorithm are proposed for the problem. The proposed algorithms are analyzed in terms of the quality of the solution and run time required to solve the same dataset used in Ghrayeb (2020). The solutions from PSO and ACO are compared to the results from Simulated Annealing (SA), Greedy Randomized Adaptive Search Procedure (GRASP), and CPLEX found in Ghrayeb (2020) as well as Goal Programming (G), Goal Programming with Symmetry Breaking (G+), Goal Programming with Modified Symmetry Breaking (GM+), and Column Generation (CG) approaches found in Srinivasan Sampathi (2021). Additional metrics such as Mean Ideal Distance (MID), Diversification Matrix (DM), the Spread of Non-Dominance Solutions (SNS), and the number of non-dominated solutions are calculated for each of the proposed algorithms for a better evaluation of their performance. Based on the results, ACO seems to be a better approach for larger job instances for the proposed problem. Both ACO and PSO outperform CPLEX for 150-job instances. Despite ACO underperforming for smaller job instances, ACO offers significant time savings for all instances when compared to CPLEX and also provides higher-quality solutions. The findings of this research can be used by schedulers in the industry to effectively group the jobs into batches and schedule them on batch processing machines, easing the pain of scheduling a large number of jobs.

Extent

98 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