.png){kind=icon}
.png){kind=icon}
Return
Exact algorithms to minimize makespan on single and parallel batch processing machines
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2020.01.065.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Batch-processing machine scheduling problem is one of the challenging problems in the machine scheduling literature where machines are capable of processing a batch of jobs simultaneously. In this paper, we tackle single and parallel batch processing machine scheduling problems with the objective of minimizing makespan. We propose a reformulation for parallel batch processing machine scheduling, which is based on decomposition in two levels, and an exact algorithm for its solution. To the best of our knowledge, there is no exact algorithm to solve this problem in the literature, except for its formulations solved by off-the-shelf solvers. In the first part of the proposed algorithm, we solve the single batch processing machine problem by a column-and-cut generation algorithm that provides a lower bound for the parallel machine problem. The second part of our proposed algorithm employs a search mechanism to find the minimum makespan for the parallel machine problem, which entails the solution of the reformulation of this problem by column generation at every iteration. The novel aspect of this column generation algorithm is the integration of batch generation and machine schedule generation in a single pricing subproblem. We test the performance of the proposed algorithms on randomly generated instances and show that, on average, they outperform the off-the-shelf solver. The major findings are that the single machine problem provides tight lower and upper bounds for the parallel machine problem, and the proposed algorithm for the parallel machine problem solves more instances to optimality than that for the single machine problem. (C) 2020 Elsevier B.V. All rights reserved.
Keywords:
Scheduling
Batch processing
Makespan minimization
Parallel machine scheduling
Column generation
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W