An exact approach for bi-objective non-identical batch processing machines scheduling

Shaoxiang Zheng (), Naiming Xie () and Qiao Wu ()
Additional contact information
Shaoxiang Zheng: Kunming University of Science and Technology
Naiming Xie: Institute of Grey System Studies, Nanjing University of Aeronautics and Astronautics
Qiao Wu: Nanjing University of Posts and Telecommunications

Annals of Operations Research, 2025, vol. 346, issue 3, No 13, 2307-2347

Abstract: Abstract Batch scheduling aims to allocate jobs into several batches on batch-processing machines, and thus increases the production efficiency and has pervasive applications. This paper investigates a novel batch-processing machine scheduling problem, in which non-identical machines are capable of processing a batch of jobs simultaneously only if the knapsack constraints are fulfilled. The objectives are to minimize makespan and total energy consumption. The mixed-integer linear programming (MILP) is established, and an exact algorithm is then proposed to tackle such a bi-objective optimization problem. In each step, the makespan is treated as a $$\epsilon $$ ϵ -constraint, and the problem can be thus regarded as a non-identical batch processing machine scheduling problem with a common deadline (NBPMP-DL), aiming to minimize the total energy consumption. A branch-and-price approach along with some acceleration strategies is devised to solve NBPMP-DL efficiently. The novel aspects of our branch-and-price algorithm are the introduction of the new branching scheme, the design of the label-setting method and the branch-and-bound algorithm for the pricing problem. In computational experiments, the presented method’s performance is tested on randomly generated instances, and the results show that, on average, they outperform the off-the-shelf solver and some state-of-art algorithms from literature in a statistical sense.

Keywords: Manufacturing; Bi-objective optimization; Batch processing; scheduling; Branch-and-price (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-025-06485-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:346:y:2025:i:3:d:10.1007_s10479-025-06485-z

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-025-06485-z

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().