Publication Date

2020

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 proposes a methodology for solving the problem of scheduling 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. Jobs must be placed into batches and scheduled on the machine such that both objectives are minimized, and machine capacity is not violated. The problem under study can be denoted as 1|p-batch, sj, rj| Cmax,Tmax. Based on a review of relevant literature, this problem has not been considered before.

The problem under study is NP-hard. Consequently, meta-heuristics such as Simulated Annealing (SA) and a Greedy Randomized Adaptive Search Procedure (GRASP) are proposed. A mathematical formulation for the problem is also proposed. Since the problem is NP-hard, the commercial solver used to solve the mathematical model is not effective to solve larger problem instances. An experimental study is conducted to evaluate SA and GRASP in terms of the quality of solution and run time required to solve randomly generated problem instances. The experimental study compares the meta-heuristics to the commercial solver used to solve the mathematical formulation.

A set of 225 instances is generated by varying values of job sizes, processing times, ready times, and due dates. The problem is formulated as a minimization of the weighted sum of the objectives (αCmax + βTmax), where α = [0, 0.25, 0.5, 0.75, 1] and β = 1 – α. SA and GRASP are developed in Matlab R2015a, and all instances are solved for all values of α. Additionally, the mathematical formulation is solved using IBM ILOG CPLEX software for values of α.

To determine the quality of the meta-heuristics, the solutions obtained from SA and GRASP are compared to those obtained from CPLEX. Additionally, the Mean Ideal Distance (MID), Diversity Matrix (DM), Spread of Non-Dominance Solutions (SNS) and the number of non-dominated solutions are calculated for each meta-heuristic, and used to compare them.

Based on the results, both GRASP and SA outperform CPLEX for 150 job instances, with SA outperforming CPLEX for 100 job instances as well. GRASP provides a larger number of non-dominated solutions, but SA provides higher quality solutions. Overall, SA provides a larger proportion of solutions that are the same as or better than CPLEX. Both SA and GRASP have significantly shorter computational times than CPLEX.

The findings of this research directly benefit schedulers working for contract electronics manufacturers, who are faced with the ardent task of scheduling hundreds of jobs each day on their batch processing machine. The meta-heuristics proposed in the research give alternative solution approaches for practitioners and academics to explore further to solve the problem under study and extensions of it.

Extent

99 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