摘要
针对车间调度问题 ,提出了一种改进的拉氏松弛算法 .在增加辅助目标函数的基础上 ,通过对子问题的限制和搜索策略的改变 ,使拉氏算法的计算量减少 ,近优解的搜索能力有很大改善 .本文还提出了一种基因优化算法 ,充分利用拉氏算法得到的多个近优解 ,进一步优化结果 .仿真结果表明对车间调度问题得到了较好的结果 .本方法也可用于其它有约束的规划问题 .
In this paper,we propose an improved Lagrangian relaxation algorithm to solve job shop scheduling problems.Besides the addition of augmented objective,we expand the search scope of near optimal solutions and improve the computational efficiency greatly by restricting the solution scope of sub problems and modifying the search method of dual problem.At the same time,we develop a genetic algorithm combining with the LR(Lagrangian relaxation)method.Using the numerous useful solutions we get in the Lagrangian relaxation as the original genes,we can improve the solution further.Test results show that these methods achieve satisfied outcome for job shop problems.They can also be applyed to other programming problems with constraints.
出处
《控制理论与应用》
EI
CAS
CSCD
北大核心
2000年第1期31-34,共4页
Control Theory & Applications
基金
国家 8 63计划!( 863 -5 11-95 0 8-0 0 3 )
关键词
车间调度问题
拉氏松弛
遗传算法
job shop scheduling problem
Lagrangian relaxation
genetic algorithm
