求解模糊作业车间调度问题的群体邻域搜索算法  

Solving Fuzzy Job Shop Scheduling Problems Through Swarm-Based Neighborhood Search Algorithm

作　　者：郑友莲[1,2] 李元香[2] 雷德明[3] 

机构地区：[1]湖北大学数学与计算机科学学院,湖北武汉430062 [2]武汉大学软件工程国家重点实验室,湖北武汉430072 [3]武汉理工大学自动化学院,湖北武汉430070

出　　处：《电子学报》2011年第10期2454-2458,共5页Acta Electronica Sinica

基　　金：国家863计划(No.2007AA01Z290);国家自然科学基金(No.60773009)

摘　　要：本文提出一种群体邻域搜索算法(Swarm-based Neighborhood Search,SNS),用于最小化模糊作业车间调度问题(Fuzzy Job Shop Scheduling Problem,FJSSP)的模糊makespan.该算法使用基于有序工序的编码,通过锦标赛选择和概率为1的动态调整互换操作更新群体.对调度结果的理论分析表明,模糊makespan能反映解的优劣.理论分析及大量实验证明,SNS具有较强的全局和局部优化能力,以及较快的收敛速度,在求解FJSSP方面具有较强的优势.This paper presents a swarm-based neighbourhood search algorithm（SNS） to minimize the maximum completion time of fuzzy job shop scheduling problem（FJSSP）.SNS uses an ordered operation-based representation,tournament selection and swap operation in which probability is 1 and swap-time is adjusted dynamically.The theoretical analyses on scheduling results show that fuzzy makespan can be used to evaluate the quality of solution.Theoretical analysis and a large number of experiments demonstrate that SNS has strong global and local optimization capabilities,faster convergence speed,and promising performance on FJSSP.

关 键 词：模糊作业车间调度 群体邻域搜索 互换 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]