We study the problem of coordinated scheduling of production and delivery subject to the production window constraint and the delivery capacity constraint. There are one or more delivery times each with a unique delivery capacity. There is a set of jobs each with a committed delivery time, processing time, production window, and profit. The company can earn the profit only if the job is processed in its production window and delivered before its committed delivery time. Our objective is to select a subset of jobs to process and deliver so as to maximize the total profit.

We consider both the single delivery time case and the multiple delivery times case. In both cases, the problem is strongly NP-hard since the subproblems at the production stage and at the delivery stage are both strongly NP-hard. Our goal is to design approximation algorithms. Suppose the jobs are k-disjoint, that is, the jobs can be partitioned into k lists of jobs such that the jobs in each list have disjoint production windows. We developed the first PTAS for the single delivery case when k is a constant and the first PTAS for multiple delivery times case as well when both k and the number of delivery times is a constant.