Int. J. of Industrial and Systems Engineering   »   2015 Vol.21, No.3

 

 

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

 

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

 

Available online: 08 Oct 2015

 

 

Editors Full text accessAccess for SubscribersPurchase this articleComment on this article