[1]潘郁,达庆利.1|fuzzy|min∑ni=1Ci模型的禁忌搜索算法[J].东南大学学报(自然科学版),2006,36(5):852-856.[doi:10.3969/j.issn.1001-0505.2006.05.034]
 Pan Yu,Da Qingli.Tabu search algorithm for model 1|fuzzy|min∑ni=1Ci[J].Journal of Southeast University (Natural Science Edition),2006,36(5):852-856.[doi:10.3969/j.issn.1001-0505.2006.05.034]
点击复制

1|fuzzy|min∑ni=1Ci模型的禁忌搜索算法()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
36
期数:
2006年第5期
页码:
852-856
栏目:
数学、物理学、力学
出版日期:
2006-09-20

文章信息/Info

Title:
Tabu search algorithm for model 1|fuzzy|minni=1Ci
作者:
潘郁12 达庆利1
1 东南大学经济管理学院, 南京 210096; 2 南京工业大学管理管理科学与工程学院, 南京 210009
Author(s):
Pan Yu12 Da Qingli1
1 College of Economics and Management, Southeast University, Nanjing 210096, China
2 College of Management Science and Engineering, Nanjing University of Technology, Nanjing 210009, China
关键词:
排序模型 模糊加工时间 禁忌搜索算法 1|fuzzy|minni=1Ci
Keywords:
scheduling model fuzzy processing time tabu search algorithms 1|fuzzy|minni=1Ci
分类号:
O223;C931.1
DOI:
10.3969/j.issn.1001-0505.2006.05.034
摘要:
根据三角形模糊数的特性,在对总加工时间模糊度有约束的条件下,构造出NP-困难的1|fuzzy|minni=1Ci排序模型的禁忌搜索(TS)算法.构造的邻域函数为互换操作.针对1|fuzzy|minni=1Ci模型的特点,设计带有惩罚项的分段线性适应度函数,以规避解的不可行性.并且,取不同的禁忌长度,观察禁忌搜索状态随迭代步数的移动轨迹,以寻求较好的计算参数组合.实例计算表明,该算法的实际应用可行,具有良好的收敛性和较高的搜索效率,且目标函数轨迹呈三阶段变化模式.迭代步数充分大后,目标函数周期性振荡,陷入循环搜索.这种性质能够帮助选择禁忌(tabu)参数值,确定迭代终止条件.
Abstract:
According to the property of triangular fuzzy number, a tabu search(TS)algorithm about the scheduling model nondeter ministic polynomial hard(NP-hard)of 〖JB<2[〗1|fuzzy|minni=1Ci〖JB>2]〗 was constructed under the condition of restricted makespan fuzzy extent. The neighborhood function constructed was swap. Focusing on the characteristic of 1|fuzzy|minni=1Ci model, segmental linear fitness function with penalty function was designed to avoid the infeasible solution. Tabu length is also alterable. In order to explore better parameters combination, the move track of TS along with iterative process was observed. The practical example shows that the algorithm is feasible in practical case, and has better astringency and searching efficiency. The track of the objective function reports three-stage variation model. If the number of iterative process steps are big enough, the objective function will surge periodically, and fall into circulating search. This property is good for choosing values of tabu parameter, and helpful to determine the condition to finish iterative process.

参考文献/References:

[1] 唐国春,张峰,罗守成,等.现代排序论[M].上海:上海科学普及出版社,2003:5-12.
[2] Prade H.Using fuzzy set theory in a scheduling problem:a case study[J]. Fuzzy Set and Systems,1979,2(2):153-165.
[3] Sangsu Han Hiroaki,Ishii Susumu Fujii.One machine scheduling problem with fuzzy duedates[J]. European Journal of Operational Research,1994,79(1):1-12.
[4] Tsutomu Konno,Hiroaki Ishii.Two-machines scheduling problem with fuzzy allowable time constraint[J].Journal of the Operations Research Society of Japan,1998,41(4):487-491.
[5] 王成尧,高麟,汪定伟.模糊加工时间调度问题的研究[J].系统工程学报,1999,14(3):238-242.
  Wang Chengyao,Gao Lin,Wang Dingwei.Scheduling problems with fuzzy processing times[J]. Journal of Systems Engineering,1999,14(3):238-242.(in Chinese)
[6] Chanas Stefan,Kasperski Adam.On two single machine scheduling problems with fuzzy processing times and fuzzy due dates[J]. European Journal of Operational Research,2003,147(2):281-296.
[7] Peng Jin,Liu Baoding.Parallel machine scheduling models with fuzzy processing times[J].Information Sciences,2004,166(1-4):49-66.
[8] Liu Baoding,Liu Yiankui.Expected value of fuzzy variable and fuzzy expected value models[J]. IEEE Transactions on Fuzzy Systems,2002,10(4):445-450.
[9] Wang Chengyao,Wang Dingwei,Ip W H,et al.The single machine ready time scheduling problem with fuzzy processing times[J]. Fuzzy Sets and Systems,2002,127(2):117-129.
[10] 王凌.智能优化算法及其应用[M].北京:清华大学出版社,2001:62-68.

备注/Memo

备注/Memo:
基金项目: 国家自然科学基金资助项目(70471017)、江苏省教育厅留学回国人员科研基金资助项目(苏教外(2000)392号).
作者简介: 潘郁(1955—), 男,博士生,panyu@njut.edu.cn; 达庆利(联系人),男,教授,博士生导师,dql@public1.ptt.js.cn.
更新日期/Last Update: 2006-09-20