Polynomial time approximation algorithms for machine scheduling: Ten open problems (Q1806342)

From the authors' prologue: In the early days of scheduling, the work of the theoretical research branch mainly consisted of classifying scheduling problems into easy (i.e. polynomially solvable) and hard (i.e. NP-hard) ones. Nowadays, researchers have become interested in a better understanding and a much finer classification of the hard problems; one very active branch of research classifies hard scheduling problems according to their approximability. The authors summarize and discuss what in their opinion are the most outstanding open questions in the approximation of scheduling problems. All scheduling problems discussed are minimization problems, where the goal is to find a feasible schedule with minimum possible cost. They consider only scheduling problems that are NP-hard and distinguish between positive results, which establish the existence of some approximation algorithm, and negative results, which disprove the existence of certain approximation results under the assumption \(P\neq NP\). 69 references are listed.