Greedy solutions of selection and ordering problems

The greedy method is a well-known technique for approaching problems involving the selection and/or ordering of a set of elements from a given set so as to optimize a specific objective function. Theoretical frameworks dealing with the optimality of greedy methods, including greedoids and matroids, consider a greedy rule known as the best-in greedy algorithm. Considering selection and ordering problems, the primary goals of this study are: (1) To present a generalization of the best-in greedy algoroithm. (2) To present a necessary and sufficient condition for the optimality of the generalized best-in greedy algorithm. (3) To investigate the potential of the theoretical results in the characterization of heuristic design for NP-hard problems. In this pursuit, we apply the two aforementioned methods to solve the single-machine scheduling problem with sequence dependent set-ups where the objective is to minimize the total tardiness. An in-depth computational study indicates that the generalized best-in greedy algorithm can significantly outperform the best-in algorithm. (4) In addition, we present an efficient dynamic programming approach for a special class of greedoid structures that, under a sufficient (and realistic) condition, yields optimal solutions.