Single machine batch scheduling with release times and delivery costs

We study single machine batch scheduling with release times. Our goal is to minimize the sum of weighted flow times (or completion times) and delivery costs. Since the problem is strongly $\mathrm{𝒩𝒫}$ ‐hard even with no delivery cost and identical weights for all jobs, an approximation algorithm is presented for the problem with identical weights. This uses the polynomial time solution we give for the preemptive version of the problem. We also present an evolutionary metaheuristic algorithm for the general case. Computational results show very small gaps between the results of the metaheuristic and the lower bound.