A Hybrid Local Search Algorithm for the Sequence Dependent Setup Times Flowshop Scheduling Problem with Makespan Criterion

Yunhe Wang, Xiangtao Li and Zhiqiang Ma
Additional contact information
Yunhe Wang: School of Information and Science Technology, Northeast Normal University, Changchun 130117, China
Xiangtao Li: School of Information and Science Technology, Northeast Normal University, Changchun 130117, China
Zhiqiang Ma: School of Information and Science Technology, Northeast Normal University, Changchun 130117, China

Sustainability, 2017, vol. 9, issue 12, 1-35

Abstract: This paper focuses on the flowshop scheduling problem with sequence dependent setup times (FSSP-SDST), which has been an investigated object for decades as one of the most popular scheduling problems in manufacturing systems. A novel hybrid local search algorithm called HLS is presented to solve the flowshop scheduling problem with sequence dependent setup times with the criterion of minimizing the makespan. Firstly, the population is initialized by the Nawaz-Enscore-Hoam based problem-specific method ( NEHBPS ) to generate high quality individuals of the current population. Then, a global search embedded with a light perturbation is designed to produce a new population. After that, to improve the quality of individuals in the current population, a single insertion-based local search is applied. Meanwhile, a further local search strategy based on the insertion-based local search is used to find better solutions for the individuals which are non-improved. Finally, the heavy perturbation is used to explore potential solutions in the neighbor region. To validate the performance of HLS, we compare our proposed algorithm with other competitive algorithms on Taillard benchmark problems. From the experimental results, it can be concluded that the proposed algorithm outperforms the benchmark algorithms.

Keywords: optimal scheduling; sequence dependent setup times; local search; makespan (search for similar items in EconPapers)
JEL-codes: O13 Q Q0 Q2 Q3 Q5 Q56 (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://www.mdpi.com/2071-1050/9/12/2318/pdf (application/pdf)
https://www.mdpi.com/2071-1050/9/12/2318/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jsusta:v:9:y:2017:i:12:p:2318-:d:122861

Access Statistics for this article

Sustainability is currently edited by Ms. Alexandra Wu

More articles in Sustainability from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().