Batch Scheduling on Parallel Machines With Submodular Costs

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.