A simulation-based modified backtracking search algorithm for multi-objective stochastic flexible job shop scheduling problem with worker flexibility

A. Gnanavelbabu

doi:10.1016/j.asoc.2021.107960

2021-12-01

PRE

A. Gnanavelbabu *

Rylan H. Caldeira

DOI：10.1016/j.asoc.2021.107960

原文链接

原文求助

摘要

En 中文

The flexible shop scheduling problem (FJSSP) has been an extensively studied and applied manufacturing systems in recent years. However, research has mostly focused on addressing the FJSSP in its basic form by relaxing several practical constraints. In this work, we consider FJSSP with worker flexibility and uncertain processing times. A simheuristic approach addresses the multi-objective stochastic FJSSP with worker flexibility, minimizing the expected makespan and standard deviation of makespan. This approach integrates the Monte Carlo simulation (MCS) into the proposed multi-objective modified Backtracking Search Algorithm (MBSA) framework. MBSA employs an effective population initialization strategy, dynamic mutation and crossover operators, and a transfer criterion. MCS evaluates' promising' solutions generated by MBSA to guide the search process. Extensive experiments are performed considering three FJSSP benchmark data sets. At first, the best parameters for the MBSA are identified using the Taguchi method. Then, for the deterministic variant of the problem, MBSA is compared with two other metaheuristics to demonstrate its effectiveness. Finally, the stochastic variant is investigated considering two factors: variation level and the probability distribution of the processing times. Computational results statistically show a significant effect of these factors on the objectives, demonstrating the importance of selecting an appropriate probability distribution in an uncertain environment. (C) 2021 Elsevier B.V. All rights reserved.

Keyword:

Flexible job shop scheduling problem

Uncertain processing times

Simheuristic approach

Worker flexibility

Backtracking search algorithm