Optimal scheduling in parallel and serial manufacturing systems via the maximum principle

The problems of M-machine, J-product, N-time point preemptive scheduling in parallel and serial production systems are the focus of this paper. The ob jective is to minimize the sum of the costs related to inventory level and production rate along a planning horizon. Although the problem is NP-hard, the application of the maximum principle reduces it into a well-tractable t ype of the two-point boundary value problem. As a result, algorithms of O(N MJ(k(N-L)+1)) and O(N(MJ)(k(N-L)+1)) time complexities are developed for pa rallel and serial production systems, respectively, where L is the time poi nt when the demand starts and k is the ratio of backlog cost MN over the in ventory cost. This compares favorably with the time complexity O((J+1)(MN)) of a naive enumeration algorithm.