Journal
IEEE TRANSACTIONS ON SYSTEMS MAN CYBERNETICS-SYSTEMS
Volume 53, Issue 3, Pages 1492-1503Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TSMC.2022.3198829
Keywords
Search problems; Metaheuristics; Scheduling; Probabilistic logic; Mathematical models; Job shop scheduling; Costs; Estimation of distribution algorithm (EDA); exploration and exploitation; fast local search; no-wait flow-shop scheduling problem (NFSSP); probabilistic model
Ask authors/readers for more resources
In this article, a matrix-cube-based estimation of distribution algorithm is proposed to solve the no-wait flow-shop scheduling problem with sequence-dependent setup times and release times. The algorithm demonstrates efficient exploration and exploitation in the solution space, leading to improved solutions compared to state-of-the-art algorithms.
The no-wait flow-shop scheduling problem (NFSSP) with sequence-dependent setup times (SDSTs) and release times (RTs) is applicable in many areas, such as steel production, food processing, and chemical processing. Estimation of the distribution algorithm (EDA) has recently been recognized as a prominent metaheuristic methodology in the field of evolutionary computation due to its excellent performance of global exploration. In this article, an innovative matrix-cube-based (i.e., 3-D) EDA (MCEDA) is first proposed to minimize the total earliness and tardiness (TET) of the NFSSP with SDSTs and RTs. This problem is NP-hard in the strong sense. First, a 3-D matrix cube is devised to learn the valuable information from promising solutions or excellent individuals. Second, an EDA model or probabilistic model based on the matrix cube and a special sampling method is presented to perform effective exploration in solution space and find promising regions. Third, based on a series of newly defined subneighborhoods, a new local search with both a speed-up scanning method and one search strategy is developed to execute exploitation from promising regions. Fourth, a speed-up evaluation method based on the problem's property is designed to reduce the computational complexity for calculating criterion and accelerate the search process. Owing to the reasonable hybridization of exploration and exploitation, MCEDA can perform very efficient search in solution space. Extensive test results on instances of such a just-in-time problem first show that MCEDA can achieve better solution than state-of-the-art algorithms in obviously less computation time. Additional experiments on instances of various NFSSPs further confirm the efficiency and robustness of MCEDA.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available