An elitist nondominated sorting hybrid algorithm for multi-objective flexible job-shop scheduling problem with sequence-dependent setups

摘要

In this paper, an elitist nondominated sorting hybrid algorithm, namely ENSHA, is proposed to solve the multi-objective flexible job-shop scheduling problem (MOFJSSP) with sequence-dependent setup times/costs (MOFJSSP_SDST/C). The objectives to be minimized are the maximal completion time (i.e., makespan) and the total setup costs (TSC). The makespan is an efficiency-focused objective whereas the TSC is an economic focused one. Existing works mainly consider the efficiency-focused multiple criteria. The main highlights of this paper are threefold, i.e., the operation-based sequence model, the problem-dependent job assignment rules and the novel evolutionary framework of ENSHA. For the operation-based sequence model, this is the first time that the sequence model of MOFJSSPs has been proposed and the TSC has been treated as an independent objective in MOFJSSPs. For the job assignment rules, the solution representation is first proposed, and then three job assignment rules are specifically designed to decode solutions or sequences into feasible scheduling schemes. For the novel evolutionary framework, it works with two populations, i.e., the main population (MP) and the auxiliary population (AP). First, ENSHA adopts the elitist nondominated sorting method for evolving MP to maintain high-quality solutions regarding both the convergence and diversity. Next, a machine learning strategy based on the estimation of distribution algorithm (EDA) is proposed to learn the valuable information from nondominated solutions in MP for building a probabilistic model. This model is then used to generate the offspring of AP. Furthermore, a simple yet effective cooperation-based refinement mechanism is raised to combine MP and AP, so as to generate MP of the next generation. Finally, experimental results on 39 benchmark instances and a real-life case study demonstrate the effectiveness and application values of the proposed ENSHA. (C) 2019 Elsevier B.V. All rights reserved.