Journal
COMPUTERS & INDUSTRIAL ENGINEERING
Volume 59, Issue 4, Pages 647-662Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cie.2010.07.014
Keywords
Flexible job-shop scheduling problem; Multi-objective optimization; Variable neighborhood search; Public critical block; Tabu search
Funding
- National Science Foundation of China [60874075, 70871065]
- Science Research and Development of Provincial Department of Public Education of Shandong [J08LJ20, J09LG29, J08LJ59]
- Soft Science Foundation of Shandong [2009REB125]
Ask authors/readers for more resources
This paper proposes an effective hybrid tabu search algorithm (HTSA) to solve the flexible job-shop scheduling problem. Three minimization objectives - the maximum completion time (makespan), the total workload of machines and the workload of the critical machine are considered simultaneously. In this study, a tabu search (TS) algorithm with an effective neighborhood structure combining two adaptive rules is developed, which constructs improved local search in the machine assignment module. Then, a well-designed left-shift decoding function is defined to transform a solution to an active schedule. In addition, a variable neighborhood search (VNS) algorithm integrating three insert and swap neighborhood structures based on public critical block theory is presented to perform local search in the operation scheduling component. The proposed HTSA is tested on sets of the well-known benchmark instances. The statistical analysis of performance comparisons shows that the proposed HTSA is superior to four existing algorithms including the AL + CGA algorithm by Kacem, Hammadi, and Borne (2002b), the PSO + SA algorithm by Xia and Wu (2005), the PSO + TS algorithm by Zhang, Shao, Li, and Gao (2009), and the Xing's algorithm by Xing. Chen, and Yang (2009a) in terms of both solution quality and efficiency. (C) 2010 Elsevier Ltd. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available