Integrated Scheduling of Production and Distribution Operations

Motivated by applications in the computer and food catering service industries, we study an integrated scheduling model of production and distribution operations. In this model, a set of jobs (i.e., customer orders) are first processed in a processing facility (e.g., manufacturing plant or service center) and then delivered to the customers directly without intermediate inventory. The problem is to find a joint schedule of production and distribution such that an objective function that takes into account both customer service level and total distribution cost is optimized. Customer service level is measured by a function of the times when the jobs are delivered to the customers. The distribution cost of a delivery shipment consists of a fixed charge and a variable cost proportional to the total distance of the route taken by the shipment. We study two classes of problems under this integrated scheduling model. In the first class of problems, customer service is measured by the average time when the jobs are delivered to the customers; in the second class, customer service is measured by the maximum time when the jobs are delivered to the customers. Two machine configurations in the processing facility---single machine and parallel machine---are considered. For each of the problems studied, we provide an efficient exact algorithm, or a proof of intractability accompanied by a heuristic algorithm with worst-case and asymptotic performance analysis. Computational experiments demonstrate that the heuristics developed are capable of generating near-optimal solutions. We also investigate the possible benefit of using the proposed integrated model relative to a sequential model where production and distribution operations are scheduled sequentially and separately. Computational tests show that in many cases a significant benefit can be achieved by integration.