Permutation flowshop scheduling with time lag constraints and makespan criterion. (June 2018)
- Record Type:
- Journal Article
- Title:
- Permutation flowshop scheduling with time lag constraints and makespan criterion. (June 2018)
- Main Title:
- Permutation flowshop scheduling with time lag constraints and makespan criterion
- Authors:
- Wang, Bailin
Huang, Kai
Li, Tieke - Abstract:
- Highlights: Prove that the proposed scheduling problem has the reversibility property. Effectively construct an initial solution based on a transformation of the makespan. Present an insertion mechanism for solution construction. Use the reversibility property to improve time complexity and solution quality. Abstract: A permutation flowshop with time lag constraints requires that the time lag between consecutive operations of a job must be in the given interval. In this study, the scheduling of such flowshop with makespan minimization objective is investigated. We prove that this problem has the reversibility property, and present a two-stage constructive heuristic with time complexity O( n 2 m ), where n and m are the numbers of jobs and machines, respectively. The first stage generates a rank of jobs based on an equivalent formulation of the makespan, and the second stage constructs a schedule through an insertion mechanism. We apply the reversibility property to reduce the time complexity of insertion procedures in both two stages, and find a better solution by solving both the original problem and its reversed problem. To verify the effectiveness and efficiency of this heuristic, we compare its performance to the mixed integer linear programming (MILP) formulation of this problem for small-scale problems, and conduct a comprehensive computational study on the Taillard's benchmark.
- Is Part Of:
- Computers & industrial engineering. Volume 120(2018)
- Journal:
- Computers & industrial engineering
- Issue:
- Volume 120(2018)
- Issue Display:
- Volume 120, Issue 2018 (2018)
- Year:
- 2018
- Volume:
- 120
- Issue:
- 2018
- Issue Sort Value:
- 2018-0120-2018-0000
- Page Start:
- 1
- Page End:
- 14
- Publication Date:
- 2018-06
- Subjects:
- Scheduling -- Permutation flowshop -- Time lags -- Constructive heuristic -- Reversibility
Engineering -- Data processing -- Periodicals
Industrial engineering -- Periodicals
620.00285 - Journal URLs:
- http://www.sciencedirect.com/science/journal/03608352 ↗
http://www.elsevier.com/journals ↗ - DOI:
- 10.1016/j.cie.2018.04.021 ↗
- Languages:
- English
- ISSNs:
- 0360-8352
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 3394.713000
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 13020.xml