Batch Scheduling on Parallel Machines With Submodular Costs
- 22 September 2026
- journal article
- research article
- Published by Wiley in Naval Research Logistics (NRL)
Abstract
This paper is motivated by the characteristics in the quenching and tempering process of steel workpieces, where the batch processing time is increasing and exhibits diminishing marginal returns. We model the batch processing time using submodular functions and study batch scheduling problems on identical parallel machines with bounded machine capacity. When the batch processing time is characterized by a submodular function, we provide a counterexample for the single‐machine problem, showing that the full batch strategy is not always optimal. We then focus on the parallel‐machine problem, where we establish the worst‐case performance ratio of the full‐batch longest processing time (FBLPT) algorithm and present a corresponding tight instance. When the batch processing time is characterized by a value‐monotone submodular function, we establish the worst‐case performance ratio of Algorithm FBLPT and provide a tight instance, and further design a modified version of this algorithm and analyze its performance. Finally, when the batch processing time is characterized by a nondecreasing concave function of the total processing time of the jobs in a batch, we design the longest processing time first‐full batch‐batch moving algorithm. We then analyze its worst‐case performance ratios for both unbounded and bounded machine capacity cases, where the result for the unbounded case serves as a theoretical foundation for the analysis of the bounded case. The effectiveness of the proposed algorithms is verified through computational experiments.Keywords
Funding Information
- National Key Research and Development Program of China (2024YFB3311100)
- National Natural Science Foundation of China (52575599)
- China Scholarship Council (CSC202206290105)
This publication has 30 references indexed in Scilit:
- A Novel Two‐Stage Flexible Flow Shop Batch Scheduling Model for Grinding WorkshopsNaval Research Logistics (NRL), 2025
- Submodular batch scheduling on parallel machinesNaval Research Logistics (NRL), 2024
- Mixed batch scheduling with non-identical job sizes to minimize makespanOR Spectrum, 2024
- Mixed batch scheduling on identical machinesJournal of Scheduling, 2019
- Clique partitioning with value-monotone submodular costDiscrete Optimization, 2015
- Improved bounds for batch scheduling with nonidentical job sizesNaval Research Logistics (NRL), 2014
- Scheduling jobs with release dates on parallel batch processing machines to minimize the makespanOptimization Letters, 2012
- Minimizing makespan on a single batch processing machine with nonidentical job sizesNaval Research Logistics (NRL), 2001
- The complexity of one-machine batching problemsDiscrete Applied Mathematics, 1993
- Batch sizing and job sequencing on a single machineAnnals of Operations Research, 1990