 A truncated column generation algorithm for the parallel batch scheduling problem to minimize total flow timeOnur Ozturk European Journal of Operational Research, 2020, vol. 286, issue 2, 432-443 Abstract: In this paper, we present a column generation based decomposition method for the parallel batch scheduling of jobs on identical parallel machines. Jobs have different release dates, processing times and sizes while machines have limited capacity. The objective is the minimization of total flow time, i.e., sum of completion times of all processed jobs. The straightforward mixed integer linear programming model of the problem is efficient for small size instances. To deal with larger instances, we develop a time indexed column generation model in which each column represents the set of jobs processed together in the same batch and the time instant for the beginning of batch processing. We obtain approximate solutions with a rounding technique followed by another mathematical model to schedule batches on machines. Numerical test results show that the proposed model is able to return high quality solutions within short computation times. Keywords: Batch scheduling; Mathematical modeling; Dynamic programming; Column generation; Time index modeling (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:eee:ejores:v:286:y:2020:i:2:p:432-443 DOI: 10.1016/j.ejor.2020.03.044 Access Statistics for this article European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati More articles in European Journal of Operational Research from Elsevier |
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.