Publication Date


Document Type


First Advisor

Damodaran, Purushothaman

Degree Name

M.S. (Master of Science)

Legacy Department

Department of Industrial and Systems Engineering


Production scheduling; Electronic data processing--Batch processing; Production control


Batch processing machines are commonly used in metal working, chemical processing, and electronics manufacturing -- to name a few. Scheduling these machines optimally is a hard task; the number of decision variables used in the mathematical formulations grow exponentially. Consequently, commercial solvers used to solve the formulations require prohibitively long run times. Schedulers struggle to make good decisions due to the complexity of the problem. This research considers the problem of scheduling a single batch-processing machine such that the total number of tardy jobs is minimized. The machine can simultaneously process several jobs as a batch as long as the machine capacity is not violated. The batch processing time is equal to the largest processing time among those jobs in the batch. Two decisions are made to schedule jobs on the batch processing machines, namely grouping jobs to form batches and sequencing the batches formed on the machines. Both the decisions are interdependent as the composition of the batch affects the processing time of the batch. The problem under study is NP-hard. Consequently, solving a mathematical formulation to find optimal solutions is computationally intensive. A greedy randomized adaptive search procedure (GRASP) is proposed to solve the problem under study with the assumption of arbitrary job sizes, arbitrary processing times and arbitrary due dates. A novel construction phase for the GRASP approach is also proposed to improve the solution quality. In addition, a path-relinking procedure is also proposed for solving large sized problems effectively. The performance of the proposed GRASP approach is evaluated by comparing its results to a commercial solver. Experimental studies suggest that the solution obtained from the GRASP approach is superior compared to the commercial solver. The proposed approach will benefit schedulers to schedule jobs on batch processing machines more efficiently. The new solution approach proposed for the problem under study fills some gaps found in the literature and will encourage other researchers to try new solution approaches or consider solving other variants of the problem.


Advisors: Purushothaman Damodaran.||Committee members: Omar Ghrayeb; Murali Krishnamurthi.||Includes bibliographical references.||Includes illustrations.


64 pages




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