A PSO and a Tabu search heuristics for the assembly scheduling problem of the two-stage distributed database application

作     者：Allahverdi, A Al-Anzi, FS 

作者机构：Kuwait Univ Dept Ind & Management Syst Engn Safat Kuwait Kuwait Univ Dept Comp Engn Safat Kuwait 

出 版 物：《COMPUTERS & OPERATIONS RESEARCH》 (计算机与运筹学研究)

年 卷 期：2006年第33卷第4期

页      面：1056-1080页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Kuwait University Research Administration  (EE 01/01) 

主　　题：assembly flowshop distributed database system scheduling maximum lateness particle swarm optimization Tabu search heuristic 

摘      要：The assembly flowshop scheduling problem has been addressed recently in the literature, There are many problems that can be modeled as assembly flowshop scheduling problems including queries scheduling on distributed database systems and computer manufacturing. The problem has been addressed with respect to either makespan or total completion time criterion in the literature. In this paper, we address the problem with respect to a due date-based performance measure, i.e., maximum lateness. We formulate the problem and obtain a dominance relation. Moreover, we propose three heuristics for the problem: particle swarm optimization (PSO), Tabu search. and EDD. PSO has been used in the areas of function optimization, artificial neural network training, and fuzzy system control in the literature. In this paper, we show how it can be used for scheduling problems. We have conducted extensive computational experiments to compare the three heuristics along with a random solution. The computational analysis indicates that Tabu outperforms the others for the case when the due dates range is relatively wide. It also indicates that the PSO significantly outperforms the others for difficult problems. i.e., tight due dates. Moreover, for difficult problems, the developed dominance relation helps reduce error by 65%. (c) 2004 Elsevier Ltd. All rights reserved.