Improved Approximation Algorithm for Scheduling on a Serial Batch Machine with Split-Allowed Delivery

This paper considers the integrated production and delivery scheduling on a serial batch machine, in which split is allowed in the delivery of the jobs. The objective is to minimize the makespan, i.e., the maximum delivery completion time of the jobs. Lu et al. (Theor Comput Sci 572:50–57, 2015) showed that this problem is strongly NP-hard, and presented a \(\frac{3}{2}\)-approximation algorithm. In this paper, we present an improved \(\frac{4}{3}\)-approximation algorithm for this problem. We also present a polynomial-time algorithm for the special case when all jobs have the identical weight.