Coordinated scheduling of production and delivery with production window and delivery capacity constraints

摘要

This paper addresses the problem of coordinated scheduling of production and delivery subject to the production window constraint and the delivery capacity constraint. We have a planning horizon consisting of 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. From the company point of view, we are interested in selecting a subset of jobs to process and deliver so as to maximize the total profit subject to the delivery capacity constraint. We consider both the single delivery time case and the multiple delivery time 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. When k is a constant, we developed the first PTAS for the single delivery case. For multiple delivery time case, we also develop a PTAS when the number of delivery times is a constant as well.