This paper studies a coordinated scheduling problem of production on parallel machines and batch delivery where
the finished jobs must be deliveried in a limited time. The objective is to minimize the sum of the makespan and the total
delivery cost. Through the complexity analysis, it is proved that the problem is strongly NP-hard, and a heuristic algorithm
is provided with the worst-case ratio 4 − 1/m??. A special case is also considered, where the jobs in a batch delivery must be
processed on the same machine. For this case, it is proved that the problem is strongly NP-hard, and two heuristic algorithms
are provided with the worst-case ratio 2−1/m?? and 4−1/m?? according to the comparation with the limited waiting time and
the processing times, respectively.