Integrated production and delivery scheduling on a serial batch machine to minimize the makespan

In this paper, we study the integrated production and delivery scheduling on a serial batch machine. The objective is to minimize the makespan, i.e., the maximum delivery completion time of the jobs. We consider four distinct problems which depend on whether split is allowed in the production or delivery of the jobs. We present a polynomial-time algorithm for the first problem and show that other three problems are strongly NP-hard. Furthermore, we provide effective approximation algorithms for the three NP-hard problems.