Complexity of Single Machine Hierarchical Scheduling: A Survey

In this paper we explore the complexity status of hierarchical scheduling on a single machine. We consider the case of two criteria where the second criterion is optimized subject to the constraint that the first meets its minimum value. Pairwise combinations of all performance measures traditionally treated in scheduling theory are considered. For every problem we either provide an NP-completeness proof or else a polynomial time algorithm. We survey most existing results in the topics involved and develop new results for problems not considered previously. Convenient tables summarizing the results are provided. Also, we discuss the managerial issues relating to each of the problems Considered.