This paper proposes a search decision rule (SDR) approach to the aggregate scheduling problem. The approach is tested by converting the objective function of the classic Holt, Modigliani, Muth and Simon paint factory scheduling problem into a 20 dimension response surface which is then explored by the SDR. Conjugate gradient, variable metric and pattern search methods are tested. All three methods demonstrate the ability to consistently descend to the neighborhood of the minimum. The pattern search technique is selected for incorporation into the SDR heuristic because of its excellent performance in terms of reducing the computation time required. Production and work force decisions made up by the SDR are comparable to those made by the linear decision rule and total costs are within 0.1%. By means of the search decision rule approach it should be possible to eliminate the restrictions imposed by linear and quadratic cost models and thereby pursue a more general and realistic approach to the aggregate scheduling problem.