Decisions, Operations, and Technology Management

The scheduling problem addressed in this paper concerns a manufacturer who produces a variety of product types and operates in a make-to-order environment. Each customer order consists of known quantities of the different product types, and must be delivered as a whole shipment. Periodically the manufacturer schedules the accumulated and unscheduled customer orders. Instances of this problem occur in the optical industry, pharmaceutical industry, computer manufacturing, furniture manufacturing, circuit board manufacturing, and electronic auto parts production. In this paper we show that the problem of minimizing the weighted sum of customer order delivery times is unary NP-hard. We characterize the optimal schedule, solve several special cases of the problem, derive tight lower bounds and propose several heuristic solutions. We report the results of a set of computational experiments to evaluate the lower bounding procedures and the heuristics, and to determine optimal solutions.