摘要
不确定型车间作业调度问题是由确定型车间作业调度问题转化而来的一个随机规划问题.针对目前求解SJSSP问题的启发式算法存在的一些局限,利用目标函数理想最值的条件,以最大加工时间最小化的期望为目标函数,提出了自适应超启发式遗传算法(Adaptive Hyper-Heuristics genetic algorithms,AHHGA),解决此类问题.在上层利用目标函数理想最值的条件,对于不同的场景选用不同的启发式规则.在下层根据上层选择的启发式规则,构造可行解,然后搜索获取最优解.通过上下两层的协同搜索,确保在有限的搜索范围内,找到性能更为优良的解,与此同时,尽可能的减少运算时间.仿真分析表明,对于FT类基准问题,当加工时间服从正态分布时,本文提出算法较目前求解此类问题的同类方法的求解质量具有一定的改进.
Stochastic job - shop scheduling problem （ SJSSP ） is a kind of stochastic programming problem which transformed from job - shop scheduling problem { JSSP）. The current methods to solve SJSSP ignored characteristics of SJSSP, which lead to large solution times and inefficient solution. Aiming at the problem, Adaptive Hyper-Heuristics genetic algorithms （AHHGA） is proposed combing with characteristics of SJSSP to solve SJSSP with the objective to minimize the expected value of makespan. The outer loop of the proposed algorithms is to determine heuristics rules on each scenario in scenario set. The inner loop is that within the hyper-heuristic framework, a genetic algorithm is employed on the high level and heuristics rules on each scenario in scenario set are used for con- structing scheduling timetables are work on the low level. Thus, the proposed algorithm ensure to find a better solution in a limit search scope with respect to characteristics of SJSSP. P-T benchmark-based problems where the processing times are subjected to inde- pendent normal distributions are solved effectively by AHHGA. The experiment results achieved by AHHGA are compared with quan- tum-inspired genetic algorithm （ QGA ） and standard genetic algorithm （GA） and a novel competitive co-evolutionary quantum genet- ic algorithm （ CCQGA）, which shows that AHHGA has better feasibility and effectiveness.
出处
《小型微型计算机系统》
CSCD
北大核心
2013年第9期2158-2163,共6页
Journal of Chinese Computer Systems
基金
国家自然科学基金项目(61074140)资助
山东省自然科学基金项目(ZR2009GQ016)资助
山东省高等学校科技计划项目(J09LG68)资助
山东理工大学特色项目支持工程项目(110018)资助
关键词
车间作业调度
遗传算法
生产管理
生产控制
job-shop scheduling
genetic algorithm
production management
production control
