This paper surveys and extends the results on the complexity of machine scheduling problems. It begins with a brief review of NP-completeness, a central concept in computational complexity theory. The paper classifies scheduling problems on single, different, and identical machines and examines how various parameters influence their complexity. It lists problems for which polynomial-bounded algorithms exist and establishes NP-completeness for many other scheduling problems. The paper also discusses open questions in the field. The paper introduces the concept of NP-completeness, which is crucial for understanding the difficulty of solving certain problems. It explains that NP-completeness implies that a problem is as hard as the hardest problems in NP, and that no efficient algorithm is likely to exist for these problems. The paper then presents several NP-complete problems, including the Clique problem, Linear Arrangement problem, Directed Hamiltonian Circuit problem, Directed Hamiltonian Path problem, Partition problem, Knapsack problem, and 3-Partition problem. The paper discusses the classification of machine scheduling problems based on parameters such as the number of jobs, machines, and the type of scheduling (e.g., flow-shop, job-shop, parallel-shop). It also considers various optimization criteria, such as minimizing maximum completion time, total weighted completion time, and total tardiness. The paper presents the complexity of various machine scheduling problems, showing that many are NP-complete. It provides reductions to demonstrate the NP-completeness of these problems and discusses the implications of these results. The paper also addresses the distinction between binary and unary encodings in terms of complexity results. The paper concludes by highlighting the importance of understanding the complexity of scheduling problems and the challenges in finding efficient algorithms for NP-complete problems. It also points out some open questions in the field and suggests that further research is needed to resolve them.This paper surveys and extends the results on the complexity of machine scheduling problems. It begins with a brief review of NP-completeness, a central concept in computational complexity theory. The paper classifies scheduling problems on single, different, and identical machines and examines how various parameters influence their complexity. It lists problems for which polynomial-bounded algorithms exist and establishes NP-completeness for many other scheduling problems. The paper also discusses open questions in the field. The paper introduces the concept of NP-completeness, which is crucial for understanding the difficulty of solving certain problems. It explains that NP-completeness implies that a problem is as hard as the hardest problems in NP, and that no efficient algorithm is likely to exist for these problems. The paper then presents several NP-complete problems, including the Clique problem, Linear Arrangement problem, Directed Hamiltonian Circuit problem, Directed Hamiltonian Path problem, Partition problem, Knapsack problem, and 3-Partition problem. The paper discusses the classification of machine scheduling problems based on parameters such as the number of jobs, machines, and the type of scheduling (e.g., flow-shop, job-shop, parallel-shop). It also considers various optimization criteria, such as minimizing maximum completion time, total weighted completion time, and total tardiness. The paper presents the complexity of various machine scheduling problems, showing that many are NP-complete. It provides reductions to demonstrate the NP-completeness of these problems and discusses the implications of these results. The paper also addresses the distinction between binary and unary encodings in terms of complexity results. The paper concludes by highlighting the importance of understanding the complexity of scheduling problems and the challenges in finding efficient algorithms for NP-complete problems. It also points out some open questions in the field and suggests that further research is needed to resolve them.