Optimal release times in single-stage manufacturing systems with finite production inventory

The paper concerns a due-date matching problem in single-stage manufacturing systems with limited production-inventory buffering capacity. The objective is to determine parts\´ release times so as to minimize a weighted sum of the discrepancies between products\´ completion times and given due dates. This scheduling problem is formulated as an optimal control problem whose "plant" is modeled by a deterministic queue with finite output buffer, its controls are the release times, and its associated cost function penalizes products\´ earliness as well as tardiness. Although the optimal control problem appears to be nonconvex and nondifferentiable, we show that it is equivalent to a differentiable, convex programming problem with linear constraints. The problem may have a large number of variables and inequalities, but we decompose it into a finite sequence of one-dimensional problems. We then develop an algorithm for computing the optimal controls and demonstrate its efficacy by means of computational examples.