全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

求解较大规模JSSP的自适应混合遗传算法

DOI: 10.13190/jbupt.200706.5.020, PP. 5-9

Keywords: Job,Shop调度问题,遗传算法,自适应,模糊逻辑控制器

Full-Text   Cite this paper   Add to My Lib

Abstract:

针对一类以最小化加权拖期时间为调度目标的JobShop调度问题(JSSP),提出一种自适应混合遗传算法。首先,在遗传算法迭代求解过程中,为降低调度问题的求解规模,基于所定义的调度特征量——资源冲突可能性,将所有操作动态划分为资源冲突可能性较高的操作和资源冲突可能性较低的操作,分别直接和间接参与染色体编码。然后,基于上述划分,遗传算法中的染色体由直接参与编码的操作序列构成的基因串、表示启发式规则的基因串(用于确定间接参与染色体编码的操作的加工优先顺序)和标志串3段基因串组成。另外,构造了一个模糊逻辑控制器用于自适应调节第一段基因串的长度,以提高算法性能。数值仿真结果表明,在求解一类较大规模的JSSP时所提算法是有效的。

References

[1]  Lee M, Takagi H. Dynamic control of genetic algorithm using fuzzy logic techniques//Proceedings of the 5th International Conference on Genetic Algorithms. San Francisco: Morgan Kaufmann, 1993: 76-83.
[2]  Zeng X, Rabenasolo B. A fuzzy logic based design for adaptive genetic algorithms//Proceedings of the 5th European Congress on Intelligent Techniques and Soft Computing. Germany: Verlag Mainz, 1997: 660-664.
[3]  Gen M, Tsujimura Y, Kubota E. Solving job-shop scheduling problem using genetic algorithms//Proceedings of the 16th International Conference on Computers and Industrial Engineering. Japan: Ashikaga, 1994: 576-579.
[4]  Giffler B, Thompson G L. Algorithms for solving production scheduling problems[J]. Operations Research, 1960, 8(4): 487-503.
[5]  Garey M R, Johnson D S. Computers and intractability: a guide to theory of NP-completeness[M]. NewYork: W H Freeman and Co Ltd, 1979.
[6]  Liu Min, Wu Cheng. Genetic algorithms for the optimal common due date assignment and the optimal scheduling policy in parallel machine earliness/tardiness scheduling problems[J]. Robotics and Computer-Integrated Manufacturing, 2006, 22(4):279-287.
[7]  Liu Min, Wu Cheng. Scheduling algorithm based on evolutionary computing in identical parallel machine production line[J]. Robotics and Computer-Integrated Manufacturing, 2003, 19(5):401-407.
[8]  Kirkpatrick S, Gelatt C D, Vecchi M P. Optimization by simulated annealing[J]. Science, 1983, 220(4598):671-680.
[9]  Golver F, Taillard E, De W D. A user's guide to tabu search[J]. Annals of Operations Research, 1993, 41(1): 3-28.
[10]  Banzhaf W, Nordin P, Keller R E, et al. Genetic programming: an introduction on the automatic evolution of computer programs and its application[M]. San Franci-sco: Morgan Kaufmann, 1998.
[11]  Dasgupta D, Michalewicz Z. Evolutionary algorithms in engineering applications[M]. Berlin: Springer Verlag, 1997.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133