[1]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]
Copy

A gravitational search algorithm for flow shop scheduling

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 5 Number of periods: 2010 5 Page number: 411-418 Column: 学术论文—智能系统 Public date: 2010-10-25
Title:
A gravitational search algorithm for flow shop scheduling
Author(s):
GU Wen-xiang;  LI Xiang-tao;  ZHU Lei;  ZHOU Jun-ping;  HU Yan-mei
Department of Computer Science, Northeast Normal University, Changchun 130117, China
Keywords:
gravitational search algorithm;  flow shop scheduling;  local search;  boundary mutation;  largest rank rule;  production time minimizing
CLC:
TP301.6
DOI:
10.3969/j.issn.1673-4785.2010.05.006
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.
Similar References:

Memo

-

Last Update: 2010-11-26

Copyright © CAAI Transactions on Intelligent Systems