In many flexible job shop scheduling problems, transportation scheduling problems are involved, increasing the difficulty in problem-solving. Here, a novel artificial Physarum polycephalum colony algorithm is proposed to help us address this problem. First, the flexible job shop scheduling problem with transportation constraints is modeled as a state transition diagram and a multi-objective function, where there are ten states in total for state transition, and the multi-objective function considers the makespan, average processing waiting time, and average transportation waiting time. Second, a novel artificial Physarum polycephalum colony algorithm is designed herein with two main operations: expansion and contraction. In the expansion operation, each mycelium can cross with any other mycelia and generate more offspring mycelia, of which each includes multiple pieces of parental information, so the population expands to more than twice its original size. In the contraction operation, a fast grouping section algorithm is designed to randomly group all mycelia according to the original population size, where each group selects the best fitness one to survive, but the other mycelia are absorbed to disappear, so the population size recovers to the original size. After multiple iterations, the proposed algorithm can find the optimal solution to the flexible job shop scheduling problem. Third, a series of computational experiments are conducted on several benchmark instances, and a selection of mainstream algorithms is employed for comparison. These experiments revealed that the proposed method outperformed many state-of-the-art algorithms and is very promising in helping us to solve these complex problems.