The synchronised asymmetric multiple travelling salesman problem in a job shop with transportation environment

In smart factories, transfer vehicles streamline the material handling of machines, leading to the complex job shop scheduling problem with transportation (JSSPT). Establishing a concise and effective mixed-integer linear programming (MILP) model for the JSSPT is challenging due to the intricate interaction of job scheduling and vehicle routing. To address the challenge, this paper described the JSSPT as a synchronised asymmetric multiple travelling salesman problem based on a disjunctive directed graph. A MILP model is subsequently developed, followed by an analysis of its inherent properties. Numerical experiments demonstrate that the proposed MILP model outperforms several published heuristic algorithms and MILP models on standard instances. Further analysis reveals that under specific parameters, the optimisation objectives of makespan and exit time align. Additionally, a heuristic strategy of scheduling vehicles prior to scheduling jobs yields better lower and upper bounds for the optimal solution compared to scheduling jobs first.