Optimal scheduling of products with common and unique components

Abstract

Consider the problem of scheduling the production of a set of products, each of which requires both common and unique components. The common components are common to all products, and the unique components are unique to a given product. A setup is required for each production batch of common components, and hence it has an incentive to combine common components for several products into a single batch. This, however, may delay the completions of other products, and the problem of batching, in addition to scheduling, arises naturally. This paper considers such a problem where both the batching and sequencing decisions are at issue. The total flow time, which is an effective measure of work-in-process inventory, is chosen as the criterion to be minimized. Based on the precedence relations derived from the properties of the problem, a dynamic programming procedure is developed to provide the optimal solution.