Performance and efficiency of production systems is hugely influenced by the capability to efficiently manage material flows. Even if today’s approaches are oriented towards applying lean-agile paradigms, in several industrial contexts, which are characterized by high complexity and personalization of products together with high volatility in demand, production scheduling remains one of the most profitable techniques for achieving acceptable levels of efficiency. As a matter of fact, the consistent amount of models proposed by scientific literature is not able to address the majority of aspects and constraints involved in real industrial contexts scheduling, while, on the other hand, commercial scheduling softwares mainly act as a simple task loader, thus not allowing to obtain high system performances. Within the aim of reducing this gap, a new framework for addressing job shop scheduling in real industrial contexts is presented in this paper. In particular, the classical graph representation of the job shop problem is extended to include constraints and characteristics typically found in a real shop floor. Moreover, new strategies are proposed to solve the problem and a representative case is reported to show the suitability of the new approach. Finally, guidelines are reported to address future developments.