Welcome to the UPF Digital Repository

Using iterated local search for solving the flow-shop problem: parametrization, randomization and parallelization issues

Show simple item record

dc.contributor.author Juan, Angel A.
dc.contributor.author Ramalhinho-Lourenço, Helena
dc.contributor.author Mateo, Manuel
dc.contributor.author Luo, Rachel
dc.contributor.author Castella, Quim
dc.date.accessioned 2020-11-23T08:53:53Z
dc.date.available 2020-11-23T08:53:53Z
dc.date.issued 2013
dc.identifier.citation Juan AA, Lourenço HR, Mateo M, Luo R, Castella Q. Using iterated local search for solving the flow-shop problem: parametrization, randomization and parallelization issues. Int Trans Oper Res. 2013 Jul 2;21(1):103-26. DOI: 10.1111/itor.12028
dc.identifier.issn 0969-6016
dc.identifier.uri http://hdl.handle.net/10230/45862
dc.description.abstract Iterated local search (ILS) is a powerful framework for developing efficient algorithms for the permutation flow‐shop problem (PFSP). These algorithms are relatively simple to implement and use very few parameters, which facilitates the associated fine‐tuning process. Therefore, they constitute an attractive solution for real‐life applications. In this paper, we discuss some parallelization, parametrization, and randomization issues related to ILS‐based algorithms for solving the PFSP. In particular, the following research questions are analyzed: (a) Is it possible to simplify even more the parameter setting in an ILS framework without affecting performance? (b) How do parallelized versions of these algorithms behave as we simultaneously vary the number of different runs and the computation time? (c) For a parallelized version of these algorithms, is it worthwhile to randomize the initial solution so that different starting points are considered? (d) Are these algorithms affected by the use of a “good‐quality” pseudorandom number generator? In this paper, we introduce the new ILS‐ESP (where ESP is efficient, simple, and parallelizable) algorithm that is specifically designed to take advantage of parallel computing, allowing us to obtain competitive results in “real time” for all tested instances. The ILS‐ESP also uses “natural” parameters, which simplifies the calibration process. An extensive set of computational experiments has been carried out in order to answer the aforementioned research questions.
dc.description.sponsorship This work has been partially supported by the Spanish Ministry of Science and Innovation (grants TRA2010-21644-C03, ECO2009-11307, and DPI2007-61371), and by the CYTEDHAROSA Network (http://dpcs.uoc.edu).
dc.format.mimetype application/pdf
dc.language.iso eng
dc.publisher Wiley
dc.relation.ispartof International Transactions in Operational Research. 2013 Jul 2;21(1):103-26
dc.rights This is the peer reviewed version of the following article: Juan AA, Lourenço HR, Mateo M, Luo R, Castella Q. Using iterated local search for solving the flow-shop problem: parametrization, randomization and parallelization issues. Int Trans Oper Res. 2013 Jul 2;21(1):103-26, which has been published in final form at http://dx.doi.org/10.1111/itor.12028. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Use of Self-Archived Versions.
dc.title Using iterated local search for solving the flow-shop problem: parametrization, randomization and parallelization issues
dc.type info:eu-repo/semantics/article
dc.identifier.doi http://dx.doi.org/10.1111/itor.12028
dc.subject.keyword Flow-shop problem
dc.subject.keyword Scheduling
dc.subject.keyword Iterated local search
dc.subject.keyword Parallelizable algorithms
dc.subject.keyword Biased-randomized heuristics
dc.subject.keyword Metaheuristics
dc.subject.keyword Parameters setting
dc.relation.projectID info:eu-repo/grantAgreement/ES/3PN/TRA2010-21644-C03
dc.relation.projectID info:eu-repo/grantAgreement/ES/3PN/ECO2009-11307
dc.relation.projectID info:eu-repo/grantAgreement/ES/2PN/DPI2007-61371
dc.rights.accessRights info:eu-repo/semantics/openAccess
dc.type.version info:eu-repo/semantics/acceptedVersion

Thumbnail

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account

Statistics

In collaboration with Compliant to Partaking