This paper deals with the 1 | p- batch , sj≤ b| ∑ Cj scheduling problem, where jobs are scheduled in batches on a single machine in order to minimize the total completion time. A size is given for each job, such that the total size of each batch cannot exceed a fixed capacity b. A graph-based model is proposed for computing a very effective lower bound based on linear programming; the model, with an exponential number of variables, is solved by column generation and embedded into both a heuristic price and branch algorithm and an exact branch and price algorithm. The same model is able to handle parallel-machine problems like Pm| p- batch , sj≤ b| ∑ Cj very efficiently. Computational results show that the new lower bound strongly dominates the bounds currently available in the literature, and the proposed heuristic algorithm is able to achieve high-quality solutions on large problems in a reasonable computation time. For the single-machine case, the exact branch and price algorithm is able to solve all the tested instances with 30 jobs and a good amount of 40-job examples.
Column generation for minimizing total completion time in a parallel-batching environment / Alfieri, A.; Druetto, A.; Grosso, A.; Salassa, F.. - In: JOURNAL OF SCHEDULING. - ISSN 1094-6136. - (2021). [10.1007/s10951-021-00703-9]
|Titolo:||Column generation for minimizing total completion time in a parallel-batching environment|
|Data di pubblicazione:||2021|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1007/s10951-021-00703-9|
|Appare nelle tipologie:|