The development and improvements in the area of cyber physical systems lead to new and complex applications in production environments and smart factories. The scheduling of machines and material handling systems has become a key component of production planning and control. At the moment the calculation of an optimal schedule for machines and autonomous guided vehicles (AGV) is only possible for small, nonrealistic scenarios. Due to the nature of mixed integer linear programming (MILP) the solution space has to be reduced or other approaches have to be used to find a near optimal solution for the job shop problem in suitable time frames. This work will adopt methods, which have been working well for regular job shops, to the new environment including AGVs.