An MO‐GVNS algorithm for solving a multiobjective hybrid flow shop scheduling problem

• Published date: 01 January 2020
• DOI: http://doi.org/10.1111/itor.12662
• Author: Marcone Jamilson Freitas Souza,Sérgio Ricardo de Souza,Eduardo Camargo de Siqueira
• Date: 01 January 2020

Intl. Trans. in Op. Res. 27 (2020) 614–650

DOI: 10.1111/itor.12662

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

An MO-GVNS algorithm for solving a multiobjective hybrid

flow shop scheduling problem

Eduardo Camargo de Siqueiraa, Marcone Jamilson Freitas Souzaband

S´

ergio Ricardo de Souzac

aFederal Institute of Education, Science and Technology of Triˆ

angulo Mineiro (IFTM), Paracatu,MG 38600-000, Brazil

bFederal Universityof Ouro Preto (UFOP), Ouro Preto, MG 35400-000, Brazil

cFederal Center of Technological Education of Minas Gerais (CEFET-MG), Av. Amazonas, 7675 – Nova Gameleira, Belo

Horizonte, MG 30510-000, Brazil

E-mail: eduardosiqueira@iftm.edu.br [de Siqueira]; marcone@ufop.edu.br [Souza]; sergio@dppg.cefetmg.br [de Souza]

Received 7 February2018; received in revised form 22 November 2018; accepted 4 March 2019

Abstract

This paper addresses the multiobjective hybrid flow shop (MOHFS) scheduling problem. In the MOHFS

problem considered here,we have a set of jobs that must be performedin a set of stages. At each stage, we have

a set of unrelated parallel machines.Some jobs may skip stages. The evaluation criteria are the minimizations

of makespan, the weighted sum of the tardiness, and the weighted sum of the earliness. For solving it, an

algorithm based on the multiobjective general variable neighborhood search (MO-GVNS) metaheuristic,

named adapted MO-GVNS, is proposed. This work also presents and compares the results obtained by

the adapted MO-GVNS with those of four other algorithms: multiobjective reduced variable neighborhood

search, nondominated sorting genetic algorithm II (NSGA-II), and NSGA-III, and another MO-GVNS

from the literature. The results were evaluatedbased on the Hypervolume, Epsilon, and Spacing metrics, and

statistically validated by the Levene test and confidence interval charts. The results showed the efficiency of

the proposed algorithm for solving the MOHFS problem.

Keywords:multiobjective hybrid flow shop; MO-GVNS; HFS; multiobjective optimization; VNS

1. Introduction

Scheduling problems arecommon mainly in industrial production and consist of defining a sequence

of jobs to be performed on a set of machines, meeting one or more objectives. In this work, a

multiobjective scheduling optimization problem in a flow shop (FS) hybrid environment, with very

well known characteristics in real-world problems, is addressed. Some features of the approached

problem are the existence of unrelated parallel machines at each stage, due dates, tardiness and

earliness costs, eligibility machine and skip stages. In this problem, known in the literature as

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

E.C. de Siqueira et al. / Intl. Trans.in Op. Res. 27 (2020) 614–650 615

multiobjective hybridflow shop (MOHFS), we consider the objectives of minimizing the makespan,

the weighted sum of tardiness, and the weighted sum of the earliness. Its detailed description is

provided in Section 3.

Multiobjective optimization problems are characterized by involving two or more conflicting

objectives simultaneously. Therefore, it is not possible to find a single solution thatoptimiz es all the

objectives at the same time. In other words, for this class of problems, the challenge is to seek a set

of efficient solutions, the so-called Paretofrontiers (Ehrgott, 2005). Ishibuchi et al. (2008) presented

a review of evolutionary multiobjective algorithms, pointing out the difficulty for solving problems

with many objectives using algorithms existing up to thatdate. Tosurpass these difficulties, Deb and

Jain (2014) proposed the nondominated sorting genetic algorithm III (NSGA-III). NSGA-III is a

genetic algorithm and represents an improvement of NSGA-II (Deb et al., 2002) for the treatment

of three or more objectives. NSGA-II, in turn, is an adaptation of its first version, NSGA, proposed

in Srinivas and Deb (1995). The selection process is based on the classification of dominance and

the crowdingdistance. In NSGA-II, this distance is calculated based on all points of the population,

and in NSGA-III it is calculated in relation to the reference points. Yuan et al. (2014) improved

NSGA-III including adaptive normalization and preservation of the diversity of reference points.

Algorithms based on multiobjective variable neighborhood search (MO-VNS) has been success-

fully applied for solving multiobjective combinatorial problems, since its first version proposed by

Geiger (2004). Schilde et al. (2009) extended the design of the variable neighborhood search (VNS)

method to the multiobjective case in order to plan tourist routes in a city. Liang et al. (2009) pre-

sented an MO-VNS algorithm to solve an identical parallel machine problem. Liang and Lo (2010)

developed an algorithm based on MO-VNS for solving the multiobjective redundancy allocation

problem. Arroyo et al. (2011) compared three multiobjective algorithms based on MO-VNS ap-

plied to the single machine scheduling problem with sequence-dependent setup times and distinct

due windows. Liang and Chuang (2013) addressed a biobjective resource allocation problem by

MO-VNS. Rego et al. (2014) applied MO-VNS for solving a biobjective single machine scheduling

problem in whichthe setup time depends on the sequence and job family.Gomes et al. (2014) applied

MO-VNS for solving a biobjectiveresource constrained project scheduling problem with precedence

relations.Duarte et al. (2015) presented an adaptation of three variants of the VNS metaheuristic for

solving multiobjective optimization problems, namely multiobjective reduced VNS (MO-RVNS),

multiobjective variable neighborhood descent (MO-VND), and MO-GVNS. These variants are

used to solve two multiobjective combinatorial optimization problems, that is, the multiobjective

knapsack problem and the multiobjective antibandwidth–cutwidth problem. The results showed

that the MO-GVNS variant was more efficientfor solving the presented problems. This MO-GVNS

variant uses the MO-VND variant as local search, which alternates improvements in each objective

until no further improvements are found. According to the authors, atthe end of the procedure, the

MO-VND ensures that each point in the solution has been improved with respect to each objective

function and each neighborhood of the handled problem. In Masri et al. (2019), a hybrid method

that uses MO-VNS for exploring and intensifying the search in specific regions is applied to solve

the single-path multicommodity communicationflow problem. L ´

opez-S´

anchez et al. (2018) propose

four variants of a hybrid algorithm that combines greedy randomized adaptive search procedure

(GRASP) with variable neighborhood descent (VND) in multiobjective versions. The MO-VND is

used for improving the constructed solution generated by the multiobjective construction phase of

GRASP. These variants are used to solve a real-world waste collection problem.

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation of OperationalResearch Societies

616 E.C. de Siqueira et al. / Intl. Trans.in Op. Res. 27 (2020) 614–650

Inspired by these successful MO-VNS applications, in this work we propose an adaptation of

the MO-GVNS algorithm presented in Duarte et al. (2015) for solving the addressed MOHFS

problem. As in Duarte et al. (2015), our adapted algorithm also uses MO-VND as the local search

method. However, while MO-VND proposed by those authors improves each objective function

separately, in our proposal the MO-VND method is used for improving all objective functions

simultaneously. In addition, as another important difference between our proposal and the one

presented in Duarte et al. (2015), the adapted MO-GVNS includes a second local search method,

which is an intensification procedurebased on the Pareto dominance approach introduced in Arroyo

et al. (2011). The adapted MO-GVNS is compared to the MO-RVNS (our adapted MO-GVNS

without the local search), the original MO-GVNS from Duarte et al. (2015), NSGA-II, and NSGA-

III algorithms, outperforming all of them.

This paper brings two main contributions. The first one is the proposition of a new MO-VNS

variant, based on the MO-GVNS variant presented in Duarte et al. (2015). The second one is the

treatment of the MOHFS problem with three conflicting objectives. This situation is not commonly

discussed in the literature concerning this problem. It is important to note that an optimal solution

for the makespan is very efficient from a production point of view, but may be bad for the customer

who wants the service delivered without delays. On the other hand, an ideal solution for the

total weighted tardiness may satisfy the customer wishes but can be highly inefficient by decreasing

production capacity and increasing inventory costs. However, the best solution to the total weighted

earliness, in turn, may reduce inventory costs, but may increase the makespan or the tardiness

or both.

The remainder of the paper is outlined as follows. A literature review is presented in Section 2.

The machine environment, the characteristics and constraints of the problem, and the optimization

objectives are defined in Section 3. Sections 4 and 5 present the proposed algorithm and the

obtained results, respectively. Finally, Section 6 presents the conclusion and future prospects forthe

development of this work.

2. Literat ure review

The mono-objective hybrid flow shop (HFS) problem is addressed in several works of the litera-

ture. Some of these papers are quoted below. Naderi et al. (2010) draw attention to two important

questions about HFS: the sequence determination at each stage and the distribution of jobs on the

machines at each stage. These authors present an algorithm based on the iterated local search (ILS)

metaheuristic, showed in Lourenc¸o et al. (2003), to minimize makespan. Urlings and Ruiz (2010)

proposed genetic algorithms (Holland, 1975) to solve this HFS problem, with the characteristics

proposed by Ruiz et al. (2008), aiming at the minimization of makespan. Zandieh et al. (2010)

also worked with the same problem and proposed another genetic algorithm. In Defersha and

Chen (2012), the authors treat HFS with genetic algorithms on sequential and parallel computing

platforms. The tests showed that the parallel implementation greatly improved the computational

performance of the developed heuristics. In de Siqueira et al. (2013), an algorithm based on evo-

lutionary strategies is proposed to treat the HFS problem, also aiming at the minimization of

makespan. In these works, several characteristics of real problems are treated, as precedence con-

straints, time lags, and sequence-dependent setup times. In Dios et al. (2018), the HFS problem is

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation ofOperational Research Societies