摘要
针对作业车间调度优化问题,研究对其进行求解的遗传算法的种群初始方法和邻域搜索机制。为提高初始种群的质量,采用主动调度、无延迟调度与启发式规则相结合的启发式方法初始群体;基于关键路径构造邻域结构,将关键工序的邻域搜索移动与基于工序的编码方式相结合,避免不可行解的产生以及染色体的检测修复等工作;对工序块的块首、块内和块尾工序分别定义了不同的邻域移动操作。基于主动解码得到的甘特图,根据工序的开工时间,正向标准化染色体,使染色体中的工序位置顺序与机器上的工序实际加工顺序一致。为扩大工序的邻域移动范围,对甘特图进行右移处理,根据工序的完工时间,反向标准化染色体。对正向和反向得到的两个标准化染色体进行邻域搜索。采用基准算例进行测试,验证了所提算法的有效性。
For the job shop scheduling optimization problem,population initialization method and neighborhood search mechanism of its solution genetic algorithm are studied.To improve the quality of the initial population,heuristic initialization method that combining active scheduling,non-delay scheduling with heuristic rules is adopted.Neighborhood structure is constructed based on the critical path.Neighborhood search moving of the key operations is carried out based on operation-based encoding to avoid infeasible solutions and chromosome testing-repair work.Different neighborhood moving for the first,inside and last operations of the operation block is defined respectively.Based on the active decoded gantt chart,to standardize the chromosome by the operation start time,and get the chromosome that the operation’s position order is in accordance with the actual processing order on machines.For the expansion of the range of operation neighborhood search,the right moving is operated on the gantt chart,and to standardize the chromosome reversely by the operation completion time.Neighborhood search is implemented on the two standardized chromosome individuals obtained by forward and reverse standardization.Benchmark problems are applied to test the proposed algorithm,and effectiveress is verified.
出处
《机械工程学报》
EI
CAS
CSCD
北大核心
2013年第16期160-169,共10页
Journal of Mechanical Engineering
基金
国家高技术研究发展计划(863计划
2011AA040601)
浙江省重点科技创新团队(2009R50015)资助项目
关键词
作业车间调度
遗传算法
种群初始化
邻域搜索
启发式规则
Job shop scheduling Genetic algorithm Population initialization Neighborhood search Heuristic rules
