A column generation approach for scheduling a batch processing machine with makespan objective Online publication date: Thu, 08-Oct-2015
by Nicholas Wiechman; Purushothaman Damodaran
International Journal of Industrial and Systems Engineering (IJISE), Vol. 21, No. 3, 2015
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.
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Industrial and Systems Engineering (IJISE):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.
If you still need assistance, please email subs@inderscience.com
Our Blog 
Follow us on Twitter 
Visit us on Facebook