Minimizing total number of tardy jobs on a single batch processing machine by greedy randomized adaptive search procedure with path relinking

Advisors: Purushothaman Damodaran.Committee members: Omar Ghrayeb; Murali Krishnamurthi.Includes bibliographical references.Includes illustrations.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.M.S. (Master of Science