Due to the increasing popularity of automated guided vehicles in modern industry and the valuable investment they require, their design and operational issues have been studied extensively in recent literature. On the other hand, machine scheduling remains an active research area since several decades. However, material handling operations should be synchronized with machine operations to get a better utilization of resources. In this article, we optimally solve an integrated production and material handling scheduling problem in a job-shop context. A mathematical programming model and a constraint programming model are presented for the problem and tested on problems from the literature. One of k-shortest paths between every two machines may be used for a material handling operation or a deadhead. When a path is chosen, all its segments are mobilized until the end of the handling operation or the deadhead. A commercial software (ILOG OPLStudio) was used for modeling and solving both models.