Scheduling blocking flowshops with setup times via constraint guided and accelerated local search. (September 2019)
- Record Type:
- Journal Article
- Title:
- Scheduling blocking flowshops with setup times via constraint guided and accelerated local search. (September 2019)
- Main Title:
- Scheduling blocking flowshops with setup times via constraint guided and accelerated local search
- Authors:
- Newton, M.A. Hakim
Riahi, Vahid
Su, Kaile
Sattar, Abdul - Abstract:
- Highlights: Studying mixed blocking flowshop scheduling problems with sequence-dependent setup times (PFSP-BS). A new acceleration method to compute makespan for each solution in the insertion neighbourhood. A constraint-guided local search algorithm to solve PFSP-BS instances. Comprehensive numerical and statistical tests to evaluate the proposed methods. Abstract: Permutation flowshop scheduling problem (PFSP) is a classical NP-Hard combinatorial optimisation problem. Existing PFSP variants capture different realistic scenarios, but significant modelling gaps still remain with respect to many real-world industrial applications. Inspired by the cider industry, in this paper, we propose a new PFSP variant that generalises over simultaneous use of several types of blocking constraints and various settings of sequence-dependent setup times. We also present a computational model for makespan minimisation of the new variant and show that solving this variant remains NP-Hard. For this PFSP variant, we then present an acceleration method to compute makespan efficiently and thus evaluate the neighbourhoods generated by insertion operators. We develop a new constructive heuristic taking both blocking constraints and setup times into account. We also develop a new local search algorithm that uses a constraint guided intensification method and a random-path guided diversification method. Our comprehensive experimental results on a set of benchmark instances demonstrate that ourHighlights: Studying mixed blocking flowshop scheduling problems with sequence-dependent setup times (PFSP-BS). A new acceleration method to compute makespan for each solution in the insertion neighbourhood. A constraint-guided local search algorithm to solve PFSP-BS instances. Comprehensive numerical and statistical tests to evaluate the proposed methods. Abstract: Permutation flowshop scheduling problem (PFSP) is a classical NP-Hard combinatorial optimisation problem. Existing PFSP variants capture different realistic scenarios, but significant modelling gaps still remain with respect to many real-world industrial applications. Inspired by the cider industry, in this paper, we propose a new PFSP variant that generalises over simultaneous use of several types of blocking constraints and various settings of sequence-dependent setup times. We also present a computational model for makespan minimisation of the new variant and show that solving this variant remains NP-Hard. For this PFSP variant, we then present an acceleration method to compute makespan efficiently and thus evaluate the neighbourhoods generated by insertion operators. We develop a new constructive heuristic taking both blocking constraints and setup times into account. We also develop a new local search algorithm that uses a constraint guided intensification method and a random-path guided diversification method. Our comprehensive experimental results on a set of benchmark instances demonstrate that our proposed algorithms significantly outperform several state-of-the-art adapted algorithms. … (more)
- Is Part Of:
- Computers & operations research. Volume 109(2019)
- Journal:
- Computers & operations research
- Issue:
- Volume 109(2019)
- Issue Display:
- Volume 109, Issue 2019 (2019)
- Year:
- 2019
- Volume:
- 109
- Issue:
- 2019
- Issue Sort Value:
- 2019-0109-2019-0000
- Page Start:
- 64
- Page End:
- 76
- Publication Date:
- 2019-09
- Subjects:
- Scheduling -- Flowshop -- Setup times -- Blocking constraints -- Local search
Operations research -- Periodicals
Electronic digital computers -- Periodicals
004.05 - Journal URLs:
- http://www.sciencedirect.com/science/journal/03050548 ↗
http://www.elsevier.com/journals ↗ - DOI:
- 10.1016/j.cor.2019.04.024 ↗
- Languages:
- English
- ISSNs:
- 0305-0548
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 3394.770000
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 10970.xml