The simultaneous analysis of production scheduling and preventive maintenance task attracts special attention of researchers due to its complexity and therefore the necessity to seek efficient methods for solving this kind of combinatorial problems. This paper presents a heuristic approach to solve this issue on job shop plants. The solution method includes a linear programming model, based on the Traveling