A biased‐randomized iterated local search for the distributed assembly permutation flow‐shop problem

• Published date: 01 May 2020
• Author: Daniele Ferone,Sara Hatami,Angel A. Juan,Paola Festa,Eliana M. González‐Neira
• DOI: http://doi.org/10.1111/itor.12719
• Date: 01 May 2020

Intl. Trans. in Op. Res. 27 (2020) 1368–1391

DOI: 10.1111/itor.12719

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

A biased-randomized iterated local search for the distributed

assembly permutation flow-shop problem

Daniele Feronea, Sara Hatamib, Eliana M. Gonz´

alez-Neirac, Angel A. Juanb,e

and Paola Festad

aDepartment of Informatics, Systems and Communication (DISCo), University of Milano-Bicocca, Milano, Italy

bIN3—Department of Computer Science, Open University of Catalonia, Barcelona,Spain

cDepartmento de Ingenier´

ıa Industrial, Pontificia Universidad Javeriana, Bogot´

a, Colombia

dDepartment of Mathematics and Applications, University of Napoli FEDERICO II, Napoli, Italy

eEuncet Business School, Terrassa,Spain

E-mail: daniele.ferone@unimib.it [Ferone]; shatami@uoc.edu[Hatami];

eliana.gonzalez@javeriana.edu.co [Gonz´

alez-Neira]; ajuanp@uoc.edu [Juan]; paola.festa@unina.it[Festa]

Received 6 December 2018; receivedin revised form 14 August 2019; accepted 14 August 2019

Abstract

Modern production systems require multiple manufacturing centers—usually distributed among different

locations—where the outcomes of each center need to be assembled to generatethe final product. This paper

discusses the distributed assembly permutation flow-shop scheduling problem, which consists of two stages:

the first stage is composed of several productionfactories, each of them with a flow-shop configuration; in the

second stage, the outcomes of each flow-shopare assembled into a final product. The goal here is to minimize

the makespan of the entire manufacturing process. With this objective in mind, we present an efficient and

parameter-less algorithm that makes use of a biased-randomized iterated local search metaheuristic. The

efficiency of the proposed method is evaluated through the analysis of an extensive set of computational

experiments. The results show that our algorithm offers excellent performance when compared with other

state-of-the-art approaches, obtaining several new best solutions.

Keywords:permutation flow-shop scheduling; metaheuristic; assembly system; distributed manufacturingsystem; iterated

local search; biased randomization

1. Introduction

Most industries haveto face daily challenges generated, among other factors, by the globalization of

markets, technological innovation and breakthroughs, product diversification, reduced life cycles,

the need of higher customization, and demand volatility (Hu et al., 2011). To remain competitive

in such a global economy, industries need to address these challenges as efficiently as possible. In

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.

D. Feroneet al. / Intl. Trans. in Op. Res. 27 (2020) 1368–1391 1369

Productio n

sta ge:

distr ibuted

manufac turing

factories with

owshop

conguration

Assembly

stag e: single

assembly

machine

M

1

M

2

M

m

Ö. .

J

1

J

i

J

1

J

i

Ö

Ö

J

1

J

i

..

1

2

3

4

5

f

M

A

t

a

t

b

ÖÖ

Fig. 1. A schematic representation of the DAPFSP.

modern production industries, with increasingly complex and customized products, it is usual to

find enterprises with multiple manufacturing centers. Thus, instead of using a single manufacturing

location, production activities are distributed among different locations. This distributed approach

is aimed at reducing the production risk and costs byincreasing the production reliability,flexibility,

and responsiveness levels. As a consequence, there is an improvement in supplychain resilience under

uncertainty and dynamic conditions. Usually, however, the outputs from these distributed centers

need to be assembled in order to generate the final product. Assembly systems facilitate industries

to be more flexible by increasing their capability to produce a diversity of products according to the

market demand (Ferreira et al., 2014).

Due to its importance, a large number of articles in the production scheduling literature deal

with the permutation flow-shop problem (PFSP) and its variants (Reza Hejazi and Saghafian,

2005; Gupta and Stafford, 2006). In the traditional PFSP, the goal is to find a permutation of jobs

that minimizes the total completion time or makespan. However, in a distributed PFSP (DPFSP),

there is an additional decision that needs to be made before the actual scheduling of jobs, that is,

which jobs are assigned to each manufacturing center. Notice that this assignment decision will

have an impact on the scheduling possibilities, which represents an additional difficulty from the

optimization perspective.A PFSP that also incorporates an assembly stage is known as the assembly

PFSP (APFSP). The natural combination of the DPFSP with the APFSP leads to the so-called

distributed assembly PFSP (DAPFSP). Thus, the DAPFSPconsists of distributed production stages

plus an assembly stage (Fig. 1). The production stage includes distributed factories, each of them

modeled as a PFSP (Naderi and Ruiz, 2010). The assembly stage consists of a single assembly

machine. Recently, Komaki et al. (2019) presented a literature review in which they classified 126

publications considering combinations of flow-shop problems (FSPs) in a first stage with assembly

operation in a second stage. The DAPFSP is included in this revision of the literature. As pointed

out by these authors, the combination of FSPs with assembly operations can be present in different

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation of OperationalResearch Societies