A State Transition Diagram and an Artificial Physarum polycephalum Colony Algorithm for the Flexible Job Shop Scheduling Problem with Transportation Constraints
Open Access
Abstract
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.Keywords
Funding Information
- National Natural Science Foundation of China (71471102, 2020AEA012, A17-302-a13)
- Major Science And Technology Projects in Hubei Province of China (71471102, 2020AEA012, A17-302-a13)
- Yichang University Applied Basic Research Project in China (71471102, 2020AEA012, A17-302-a13)
This publication has 40 references indexed in Scilit:
- Embedded PSO for Solving FJSP on Embedded Environment (Industry 4.0 Era)Applied Sciences, 2022
- Surrogate-assisted population based ACO for resource constrained job scheduling with uncertaintySwarm and Evolutionary Computation, 2022
- Intelligent Transportation Systems along with the COVID-19 Pandemic will Significantly Change the Transportation MarketThe Open Transportation Journal, 2021
- Production and transport scheduling in flexible job shop manufacturing systemsJournal of Global Optimization, 2021
- Bi-local search based variable neighborhood search for job-shop scheduling problem with transport constraintsOptimization Letters, 2020
- A multistart biased random key genetic algorithm for the flexible job shop scheduling problem with transportationInternational Transactions in Operational Research, 2020
- A Node Selecting Approach for Traffic Network Based on Artificial Slime MoldIEEE Access, 2020
- Transfer-robot task scheduling in job shopInternational Journal of Production Research, 2020
- An Entropy-Robust Optimization of Mobile Commerce System Based on Multi-agent SystemArabian Journal for Science and Engineering, 2015
- Tabu search algorithms for job-shop problems with a single transport robotEuropean Journal of Operational Research, 2005