Treffer: Optimising batch scheduling on non-identical parallel machines: lower bounds, MIP, branch-and-price, and heuristics.

This paper addresses a scheduling problem involving a set of diverse jobs processed in batches. Each job has its own processing time and size. Notably, the processing time of any batch is determined by the longest processing time among the jobs it contains. These batches are scheduled on parallel machines with non-identical capacities, ensuring that the total size of the jobs in any batch does not exceed the capacity of the assigned machine. The objective is to minimise the maximum makespan across all machines, where the makespan is defined as the sum of the processing times of all batches on a machine. To tackle this problem, the paper proposes lower bounds, a mixed-integer programming formulation, and a branch-and-price algorithm. Additionally, five rule-based heuristics and a beam search algorithm are introduced. An extensive computational study demonstrates that the proposed solution methods outperform existing approaches in the literature in terms of both solution quality and computational efficiency. Furthermore, the proposed methods achieve best-known solutions for the first time in the literature, demonstrating their significant improvement over existing approaches. [ABSTRACT FROM AUTHOR]

Copyright of International Journal of Production Research is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Volltext ist im Gastzugang nicht verfügbar. Login für vollen Zugriff.