Constraint guided accelerated search for mixed blocking permutation flowshop scheduling. (February 2019)
- Record Type:
- Journal Article
- Title:
- Constraint guided accelerated search for mixed blocking permutation flowshop scheduling. (February 2019)
- Main Title:
- Constraint guided accelerated search for mixed blocking permutation flowshop scheduling
- Authors:
- Riahi, Vahid
Newton, M.A. Hakim
Su, Kaile
Sattar, Abdul - Abstract:
- Highlights: Studying mixed blocking flowshop scheduling problem (MBPFSP). A new Acceleration method for insertion neighbourhood operator. A constraint-guided local search algorithm for solving MBPFSP. Comprehensive numerical and statistical tests to evaluate the proposed methods. Abstract: Mixed Blocking Permutation Flowshop Scheduling Problem (MBPFSP) with the objective of makespan minimisation is NP-Hard. It has important industrial applications that include the cider production industry. MBPFSP has made some progress in recent years. However, within practical time limits, existing incomplete algorithms still either find low quality solutions or struggle with large problems. One key reason behind this is the typical way of using generic heuristics or metaheuristics that usually lack problem specific structural knowledge. In MBPFSP, a machine could be blocked with the currently finished job until the subsequent machine is available to process the same job. These blocking constraints affect the makespan. So MBPFSP search should naturally take explicit steps to take the blocking constraints into account. Unfortunately, existing research on MBPFSP just uses only the makespan to compare generated solutions, but the search otherwise is not aware of the blocking constraints. Moreover, existing such methods use either an exhaustive or a random neighbourhood generation strategy. In this work, we aim to advance MBPFSP search by better exploiting the problem specific structuralHighlights: Studying mixed blocking flowshop scheduling problem (MBPFSP). A new Acceleration method for insertion neighbourhood operator. A constraint-guided local search algorithm for solving MBPFSP. Comprehensive numerical and statistical tests to evaluate the proposed methods. Abstract: Mixed Blocking Permutation Flowshop Scheduling Problem (MBPFSP) with the objective of makespan minimisation is NP-Hard. It has important industrial applications that include the cider production industry. MBPFSP has made some progress in recent years. However, within practical time limits, existing incomplete algorithms still either find low quality solutions or struggle with large problems. One key reason behind this is the typical way of using generic heuristics or metaheuristics that usually lack problem specific structural knowledge. In MBPFSP, a machine could be blocked with the currently finished job until the subsequent machine is available to process the same job. These blocking constraints affect the makespan. So MBPFSP search should naturally take explicit steps to take the blocking constraints into account. Unfortunately, existing research on MBPFSP just uses only the makespan to compare generated solutions, but the search otherwise is not aware of the blocking constraints. Moreover, existing such methods use either an exhaustive or a random neighbourhood generation strategy. In this work, we aim to advance MBPFSP search by better exploiting the problem specific structural knowledge. We use the constraint and the objective functions to obtain such problem specific knowledge and we exploit such knowledge both in a constructive search method and in a local search method. In this paper, we also present an acceleration method to efficiently evaluate insertion-based neighbourhoods of MBPFSP. Our experimental results on three standard testbeds demonstrate that our proposed algorithms significantly improve over existing best-performing algorithms. … (more)
- Is Part Of:
- Computers & operations research. Volume 102(2019)
- Journal:
- Computers & operations research
- Issue:
- Volume 102(2019)
- Issue Display:
- Volume 102, Issue 2019 (2019)
- Year:
- 2019
- Volume:
- 102
- Issue:
- 2019
- Issue Sort Value:
- 2019-0102-2019-0000
- Page Start:
- 102
- Page End:
- 120
- Publication Date:
- 2019-02
- Subjects:
- Flowshop -- Scheduling -- 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.2018.10.003 ↗
- 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:
- 14561.xml