[1]谷文祥,李向涛,朱 磊,等.求解流水线调度问题的万有引力搜索算法[J].智能系统学报,2010,5(5):411-418.[doi:10.3969/j.issn.1673-4785.2010.05.006]
GU Wen-xiang,LI Xiang-tao,ZHU Lei,et al.A gravitational search algorithm for flow shop scheduling[J].CAAI Transactions on Intelligent Systems,2010,5(5):411-418.[doi:10.3969/j.issn.1673-4785.2010.05.006]
点击复制
GU Wen-xiang,LI Xiang-tao,ZHU Lei,et al.A gravitational search algorithm for flow shop scheduling[J].CAAI Transactions on Intelligent Systems,2010,5(5):411-418.[doi:10.3969/j.issn.1673-4785.2010.05.006]
求解流水线调度问题的万有引力搜索算法
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
5
期数:
2010年第5期
页码:
411-418
栏目:
学术论文—智能系统
出版日期:
2010-10-25
- Title:
- A gravitational search algorithm for flow shop scheduling
- 文章编号:
- 1673-4785(2010)05-0411-08
- Keywords:
- gravitational search algorithm; flow shop scheduling; local search; boundary mutation; largest rank rule; production time minimizing
- 分类号:
- TP301.6
- 文献标志码:
- A
- 摘要:
- 研究了以最大完工时间为目标的流水线调度问题，使用万有引力算法求解调度问题，提出了一种最大排序规则，利用物体间各个位置分量值存在的大小次序关系，并结合随机键编码的方法产生，将物体的连续位置转变成了一个可行的调度方案；提出了一种边界变异的策略使得越界的物体不再聚集在边界上，而是分布在边界附近的可行空间内，从而增加种群的多样性；结合交换算子和插入算子提出了一种新的局部搜索算法，有效地避免了算法陷入局部最优值，进一步提高了解的质量.最后证明了算法的收敛性，并且计算了算法的时间复杂度和空间复杂度，仿真实验说明了所得算法的有效性.
- Abstract:
- An improved gravitational search algorithm (IGSA) was proposed to solve the flow shop scheduling problem with the objective of minimizing production time. First, to make a GSA suitable for permutation of the flow shop scheduling problem (PFSSP), a new largest-rank-rule based on a random key was introduced to convert the continuous position of the GSA into the discrete job permutation so that the GSA could be used for solving PFSSP. Second, a new boundary mutation was proposed. This operation stopped the agents which have mutations as a result of using the above method from gathering at the border. They were distributed at a feasible distance from the boundary. This improvement also improved the population diversity. Third, by combining the communicating operator and inserting operator, the new local search was designed to help the algorithm escape from the local minimum. Finally, the convergence of the iterative algorithm and its complexities in time and space were proven. Additionally, simulations and comparisons based on PFSSP benchmarks were carried out, which show that the proposed algorithm is both effective and efficient.
- 参考文献/References:
-
［1］GAREY M R, JOHNSON D S. Computers and intractability: a guide to the theory of NP-completeness［M］. New York, USA: Freeman, 1990.
［2］RINNOOY KAN A H G. Machine scheduling problems: classification, complexity, and computations［M］. The Hague, The Netherlands: Nijhoff, 1976.
［3］CROCE F D, NARAYAN V, TADEI R. The two-machine total completion time flow shop problem［J］. European Journal of Operational Research, 1996, 90: 227-237.
［4］CROCE F D, GHIRARDI M, TADEI R. An improved branch-and-bound algorithm for the two machine total completion time flow shop problem［J］. European Journal of Operational Research, 2002, 139: 293-301.
［5］PALMER D S. Sequencing jobs through a multistage process in the minimum total time: a quick method of obtaining a near-optimum［J］. Operational Research Quarterly, 1965, 16: 101-107.
［6］GUPTA J N D. Heuristic algorithms for multistage flowshop scheduling problem［J］.AIIE Transactions, 1972, 4: 11-18.
［7］KUO Ihong, HORNG Shijinn, KAO Tzongwann, et al. An efficient flow-shop scheduling algorithm based on a hybrid particle swarm optimization model［J］. Lecture Notes in Computer Science, 2007, 4570: 303-312.
［8］LIAN Zhigang, GU Xingsheng, JIAO Bin. A novel particle swarm optimization algorithm for permutation flow-shop scheduling to minimize makespan［J］. Chaos, Solitons and Fractals, 2008, 35: 851-861.
［9］RASHEDI E, NEZAMABADI-POUR H, SARYAZDI S. GSA: a gravitational search algorithm［J］. Information Science, 2009, 179(13): 2232-2248.
［10］张长胜,孙吉贵,欧阳丹彤,等.求解车间调度问题的自适应混合粒子群算法［J］.计算机学报, 2009, 32(11): 2137-2146.
ZHANG Changsheng, SUN Jigui, OUYANG Dantong,et al. A self-adaptive hybrid particle swarm optimization algorithm for flow shop scheduling problem［J］. Chinese Journal of Computers, 2009, 32(11): 2137-2146.
［11］CARLIER J. Ordonnancements a contraintes disjonctives［J］. RAIRO Recherche Operationelle, 1978, 12: 333-351.
［12］REEVES C R, YAMADA T. Genetic algorithms, path relinking and the flowshop sequencing problem［J］. Evolutionary Computation, 1998, 6(1): 45-60.
［13］TAILLARD E. Benchmarks for basic scheduling problems［J］. European Journal of Operational Research, 1993, 64: 278-285.
［14］PONNAMBALAM S G, ARAVINDAN P, CHANDRASEKARAN S. Constructive and improvement flow shop scheduling heuristics: an extensive evaluation［J］. Production Planning & Control, 2001, 12(4): 335-344.
［15］WANG L, ZHENG D Z. An effective hybrid heuristic for flowshop scheduling［J］. International Journal of Advanced Manufacturing Technology, 2003, 21: 38-44.
- 相似文献/References:
-
[1]谷文祥,郭丽萍,殷明浩.模糊c-均值算法和万有引力算法求解模糊聚类问题[J].智能系统学报,2011,6(6):520.
GU Wenxiang,GUO Liping,YIN Minghao.A solution for a fuzzy clustering problem by applying fuzzy c-means algorithm and gravitational search algorithm[J].CAAI Transactions on Intelligent Systems,2011,6():520.
备注/Memo
收稿日期：2010-03-29.
基金项目：国家自然科学基金资助项目（60473042, 60573067, 60803102）.
通信作者：李向涛. E-mail: lixt314@nenu.edu.cn.
作者简介：
谷文祥，男，1947年生，教授、博士生导师，主要研究方向为智能规划与规划识别、形式语言与自动机、模糊数学及其应用.参加或承担国家自然科学基金、教育部重点项目、省科委项目多项，发表学术论文100余篇.
李向涛，男，1987年生，硕士研究生，主要研究方向为智能规划、智能信息处理.
朱 磊，男，1987年生，硕士研究生，主要研究方向为智能规划、智能信息处理.
更新日期/Last Update:
2010-11-26