Job-shop is the problem of allocating the tasks to machine tools with a time table satisfying a set of objectives. Currently researches on Job-shop generally take the independent production processing as the study case. It is still difficult to schedule the production processing with complex correlated features. Taking the shop with m machine tools and n waiting correlated tasks as the study case, this research proposes an evolutionary algorithm-based and correlated constraint-driven optimization method to overcome the above difficulty. First, the tasks are classed as the correlated tasks and independent tasks according to the correlated features and the priority levels, which construct the foundation of modeling for complex correlated constraints. And then, the objective function is built taking the lower production cost and higher equipment capacity factor as optimization objectives. Finally, the optimization model is developed and solved with the specialized evolution algorithm. The simulation with the Matlab demonstrates the feasibility of the novel methodology.