 A column generation approach for scheduling a batch processing machine with makespan objectiveNicholas Wiechman and Purushothaman Damodaran International Journal of Industrial and Systems Engineering, 2015, vol. 21, issue 3, 334-355 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. (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:ids:ijisen:v:21:y:2015:i:3:p:334-355 Access Statistics for this article More articles in International Journal of Industrial and Systems Engineering from Inderscience Enterprises Ltd |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.