This paper surveys and extends the results on the complexity of machine scheduling problems. It begins with a brief review of computational complexity theory, focusing on the concept of NP-completeness. The authors classify scheduling problems into categories based on the number of jobs, machines, and different parameters such as flow-shop, permutation flow-shop, job-shop, and parallel-shop. They also consider various optimization criteria, including minimizing the maximum completion time, total completion time, lateness, and tardiness. The paper presents a classification of machine scheduling problems and discusses the complexity of these problems. Many of the problems are shown to be NP-complete, while others have polynomial-bounded algorithms. The authors provide reductions to establish NP-completeness for several problems and highlight the impact of minor changes in problem parameters on their complexity. They also discuss open problems and suggest potential areas for further research, emphasizing the importance of understanding the borderline between "easy" and "hard" scheduling problems. The paper concludes with a discussion on the limitations of the NP-completeness concept and the need for more refined complexity measures.This paper surveys and extends the results on the complexity of machine scheduling problems. It begins with a brief review of computational complexity theory, focusing on the concept of NP-completeness. The authors classify scheduling problems into categories based on the number of jobs, machines, and different parameters such as flow-shop, permutation flow-shop, job-shop, and parallel-shop. They also consider various optimization criteria, including minimizing the maximum completion time, total completion time, lateness, and tardiness. The paper presents a classification of machine scheduling problems and discusses the complexity of these problems. Many of the problems are shown to be NP-complete, while others have polynomial-bounded algorithms. The authors provide reductions to establish NP-completeness for several problems and highlight the impact of minor changes in problem parameters on their complexity. They also discuss open problems and suggest potential areas for further research, emphasizing the importance of understanding the borderline between "easy" and "hard" scheduling problems. The paper concludes with a discussion on the limitations of the NP-completeness concept and the need for more refined complexity measures.