A due date assignment algorithm for multiproduct manufacturing facilities

The order acceptance process is an important interface between a manufacturer and its customers. This paper considers a complex manufacturing facility, capable of simultaneously producing a large variety of products, e.g., printed wiring boards for telecommunications and electronic sytems. A requested due date is submitted with each customer order. A batch of orders is accumulated by the manufacturer for a certain period, e.g., one week or one day. For each order, production control must either confirm the requested due date or propose an alternate due date. (Some high-priority orders may be confirmed shortly upon receipt.) The authors develop a heuristic, the Due Date Assignment Algorithm, to solve the order acceptance problem. Its objective is to minimize the sum of weighted (positive) deviations of the assigned due dates from the requested dates. The heuristic first generates a menu of candidate schedules for each order. It then applies a Lagrangean relaxation scheme to an integer programming formulation of the problem. Finally, an interchange procedure is applied, if necessary, to obtain primal feasibility. Computational results revealed significant improvements over the often-used policy of assigning a due date to each single order upon its arrival.