Coordinated scheduling on parallel machines with batch delivery

This paper considers coordinated scheduling on parallel identical machines with batch delivery. Jobs are first processed on m parallel and identical machines in the manufacturing facility and then delivered to the customer in batches. There are v identical transporters that can carry up to c jobs in one shipment. The objective is to minimize the sum of job arrival times. We show that the problem is NP-hard in the strong sense if m is part of the input. Besides, we propose the first approximation algorithm for the problem and prove that the worst case ratio of the algorithm is 2−1/m for any m.