A new efficient biased random key genetic algorithm for open shop scheduling with routing by capacitated single vehicle and makespan minimization. (September 2021)

• Record Type: Journal Article
• Authors: Abreu, Levi R.; Tavares-Neto, Roberto F.; Nagano, Marcelo S.
• Is Part Of: Engineering applications of artificial intelligence. Volume 104(2021)
• Publication Date: 2021-09
• Subjects: Integrated scheduling -- Evolutionary algorithms -- Hybrid algorithms -- Open shop; Engineering -- Data processing -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Ingénierie -- Informatique -- Périodiques; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; Artificial intelligence; Engineering -- Data processing; Expert systems (Computer science); Periodicals; 620.00285
• DOI: 10.1016/j.engappai.2021.104373
• Languages: English
• ISSNs: 0952-1976

Abstract

Abstract: Over the last years, researchers have been paying particular attention to scheduling problems integrating production environments and distribution systems to adopt more realistic assumptions. This paper aims to present a new biased random key genetic algorithm with an iterated greedy local search procedure (BRKGA-IG) for open shop scheduling with routing by capacitated vehicles. We propose approximation and exact algorithms to obtain high-quality solutions in acceptable computational times. This paper presents a new integer linear programming model. The proposed integer model has not been addressed in the revised literature. The objective function adopted is makespan minimization, and we use the relative deviation as performance criteria. BRKGA-IG has a new decoding scheme for OSSP-VRP solutions, an intensive exploitation mechanism with an iterated greedy local search procedure, and a restart mechanism to reduce premature population convergence. With these new mechanisms, the extensive computational experience carried out shows that the proposed metaheuristic BRKGA-IG is promising in solving large-sized instances for the new proposed problem, outperforming all other tested methods. Highlights: We study an integrated open shop scheduling problem with the vehicle routing problem. This problem is modeled and solved by a MILP and a metaheuristic approach. The biased random key genetic algorithm and the iterated greedy algorithm are used. The proposed metaheuristic gets competitive results.