Khurshid B, Maqsood S, Khurshid Y, Naeem K, Khalid QS. A hybridization of evolution strategies with iterated greedy algorithm for no-wait flow shop scheduling problems.
Sci Rep 2024;
14:2376. [PMID:
38287049 PMCID:
PMC10825172 DOI:
10.1038/s41598-023-47729-x]
[Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/15/2023] [Accepted: 11/17/2023] [Indexed: 01/31/2024] Open
Abstract
This study investigates the no-wait flow shop scheduling problem and proposes a hybrid (HES-IG) algorithm that utilizes makespan as the objective function. To address the complexity of this NP-hard problem, the HES-IG algorithm combines evolution strategies (ES) and iterated greedy (IG) algorithm, as hybridizing algorithms helps different algorithms mitigate their weaknesses and leverage their respective strengths. The ES algorithm begins with a random initial solution and uses an insertion mutation to optimize the solution. Reproduction is carried out using (1 + 5)-ES, generating five offspring from one parent randomly. The selection process employs (µ + λ)-ES, allowing excellent parent solutions to survive multiple generations until a better offspring surpasses them. The IG algorithm's straightforward search mechanism aids in further improving the solution and avoiding local minima. The destruction operator randomly removes d-jobs, which are then inserted one by one using a construction operator. The local search operator employs a single insertion approach, while the acceptance-rejection criteria are based on a constant temperature. Parameters of both ES and IG algorithms are calibrated using the Multifactor analysis of variance technique. The performance of the HES-IG algorithm is calibrated with other algorithms using the Wilcoxon signed test. The HES-IG algorithm is tested on 21 Nos. Reeves and 30 Nos. Taillard benchmark problems. The HES-IG algorithm has found 15 lower bound values for Reeves benchmark problems. Similarly, the HES-IG algorithm has found 30 lower bound values for the Taillard benchmark problems. Computational results indicate that the HES-IG algorithm outperforms other available techniques in the literature for all problem sizes.
Collapse