Multiobjective pseudo‐variable neighborhood descent for a bicriteria parallel machine scheduling problem with setup time

• DOI: http://doi.org/10.1111/itor.12738
• Date: 01 May 2020
• Author: Thiago Alves de Queiroz,Leandro Resende Mundim
• Published date: 01 May 2020

Intl. Trans. in Op. Res. 27 (2020) 1478–1500

DOI: 10.1111/itor.12738

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Multiobjective pseudo-variable neighborhood descent for a

bicriteria parallel machine scheduling problem with setup time

Thiago Alves de Queirozaand Leandro Resende Mundimb

aInstitute of Mathematics and Technology,Federal University of Goi´

as – Catal˜

ao,

Av. Dr. LamartineP. Avelar, 1120, 75704-020, Catal˜

ao, GO, Brazil

bInstitute of Mathematical and Computer Sciences, University of S˜

ao Paulo,

Av. Trabalhador S˜

ao-Carlense, 400, 13566-590, S˜

ao Carlos, S˜

ao Paulo, Brazil

E-mail: taq@ufg.br [Queiroz];m undim@icmc.usp.br [Mundim]

Received 9 February2018; received in revised form 9 July 2019; accepted 30 September 2019

Abstract

A multiobjective variable neighborhood descent (VND) based heuristic is developed to solve a bicriteria

parallel machine scheduling problem. The problemconsiders two objectives, one related to the makespan and

the other to the flow time, where the setup time depends on the sequence, and the machines are identical.

The heuristic has a set of neighborhood structures based on swap, remove, and insertion moves. We propose

changing the local search inside the VND to a sequential search through the neighborhoods to obtain

nondominated points for the Pareto-front quickly. In the numerical tests, we consider a single-objective

version of the heuristic, comparing the results on 510 benchmark instances to show that it is quite effective.

Moreover, new instances are generated in accordance with the literature for the bicriteria problem, showing

the ability of the proposed heuristic to return an efficient set of nondominate solutions compared with the

well-known nondominated sorting genetic algorithm II.

Keywords:multiobjective variableneighborhood descent; parallel machine scheduling problem; sequence-dependent setup

time; makespan; flow time

1. Introduction

The parallel machine scheduling problem (PMSP) arises from many industrial environments in

which not only the makespanbut also the flow time are requisites for taking decisions.The makespan

is related to the maximum completion time of the jobs (i.e., Cmax), while the flowtime in this problem

represents the summation of the completion time of each job (i.e., Ci). In general, the PMSP

looks for a schedule of a set of jobs on a set of parallel machines, attaining a given objective (e.g.,

minimize the makespan, minimize the flow time, minimize the earliness, minimize the tardiness,

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.

T.A. Queiroz and L.R. Mundim / Intl. Trans. in Op. Res. 27 (2020) 1478–1500 1479

Fig. 1. Minimization of the makespan and the flow time: (a) minimizing the makespan,(b) minimizing the flow time,

and (c) minimizing both objectives.

minimize the cost of controlling jobs, or minimize a fuzzy makespan) (Mokotoff, 2004; Zarandi

and Kayvanfar, 2015; Cheng and Huang, 2017).

Figure 1 exemplifies an environment with two identical machines and eight jobs in which the

setup time is sequence-dependent. We note that the minimization of the makespan does not imply

that the flow time is attained at its minimum, and vice versa. In Fig. 1c, the makespan value is less

than that in Fig. 1b, whilethe flow time is less than that in Fig. 1a. Both objectives may be taken into

consideration when solving the PMSP, aiming at reducing the time machines are operating as well

as production costs (Lin and Ying, 2013). Several variants of the PMSP are NP-hard (Pinedo, 2008)

and may be found in manufacturing, air traffic control, project management, TV advertisements,

central unit processing scheduling, among others (Allahverdi, 2015).

The identical PMSP with sequence-dependent setup time is denoted as Pm|Sij|Cmax,ifthe

makespan is minimized. On the other hand, if the flow time is minimized, this problem is

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation of OperationalResearch Societies