Title: A column generation approach for scheduling a batch processing machine with makespan objective

Authors: Nicholas Wiechman; Purushothaman Damodaran

Addresses: Department of Industrial and Systems Engineering, Northern Illinois University, DeKalb, IL 60115, USA ' Department of Industrial and Systems Engineering, Northern Illinois University, DeKalb, IL 60115, USA

Abstract: In this paper, the single machine batch scheduling problem with non-identical job processing times, non-identical job sizes, and a fixed machine size capacity is considered with the objective of minimising makespan. The problem is solved using a column generation approach in which the original problem is decomposed into a restricted master problem and a subproblem. The restricted master problem is then linearly relaxed and iteratively solved to optimality by utilising improving columns generated by solving the subproblem. Finally, the restricted master problem is resolved as an integer programme to obtain a final feasible solution. The results are compared to previous results obtained using simulated annealing, a genetic algorithm, and a commercial solver. The solution quality and run time compare very favourably with these other approaches, producing at least an equivalent solution in all of the test cases and generating a better solution in 65% of the cases that contained 50 or more jobs.

Keywords: batch processing machines; BPMs; single machine scheduling; column generation; makespan; simulated annealing; genetic algorithms.

DOI: 10.1504/IJISE.2015.072270

International Journal of Industrial and Systems Engineering, 2015 Vol.21 No.3, pp.334 - 355

Received: 22 Jul 2013
Accepted: 06 Jan 2014

Published online: 08 Oct 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article