On an extension of the Sort & Search method with application to scheduling theory

In this paper, we focus on the Sort & Search method initially proposed by Horowitz and Sahni (1974)  [6] to solve the knapsack problem, which has already show its applicability to derive exponential-time algorithms for some scheduling problems. We propose an extension of this method to a general class of problems called Multiple Constraint Problems and show that the extended Sort & Search method enables one to derive new exponential-time algorithms, with worst-case complexity, for two scheduling problems.