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 considers a real-time problem where jobs need to be batched and scheduled to a single batch processing machine to minimize makespan and maximum tardiness. Jobs must be placed in batches such that the machine capacity is not violated. The jobs considered have unequal ready times, unequal processing times, and unequal sizes. This research aims to develop an effective solution approach for the proposed problem. The problem under study can be denoted as 1|p-batch, sj, rj| Cmax, Tmax.

The problem under study is NP-Hard. A new Mixed Integer Linear Programming (MILP) formulation using Goal programming (MILP-G) and Column Generation (MILP-CG) are proposed as enhancements of formulations proposed in the literature and solved using the commercial solver. To avoid the symmetric solution in MILP two symmetry-breaking methods are proposed using goal programming (MILP-G+ and MILP-GM+) for a multi-objective function. An experimental study is conducted to evaluate the different goal programming formulation and Column Generation in terms of solution quality and run time.

A set of 225 instances is generated by varying the values of job size, ready time, processing time, and due date. All MILPs are solved using IBM ILOG CPLEX. This research compares the results of the proposed methods with the results of the weighted residual method (MILP-W) given by Ghrayeb (2020).

Based on the results, MILP-G+, and MILP-GM+ outperform MILP-W for 100 and 150 job instances. MILP-G performed better than MILP-W for 100 and 150 job instances but not always. MILP-CG took a long time for higher job instances to solve the subproblem and relaxed problem, so the solution quality was surprisingly low. The findings of this research directly benefit schedulers who are faced with the ardent task of scheduling hundreds of jobs each day on their batch processing machine. The MILPs 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

65 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