A review on the complexity of scheduling manufacturing shops

Abstract EN

Most of the classical machine scheduling problems have been shown in the literature to be efficiently solvable or NP-complete.

This paper presents a survey of the basic literature on methods of NP-completeness proof and results obtained in the area of machine scheduling and sequencing.

In addition, it defines the general job shop scheduling problem and shows that it belongs to the NP-complete class.

Furthermore, changes in the structure of the general form of the job shop problem that brings it out of the NP-complete class are presented, and related solutions available in the literature are referenced.