摘要
为有效解决考虑物料搬运设备的Job Shop调度问题,建立了非线性规划模型及改进析取图模型.在此基础上,以最小化最大完工时间makespan为调度目标,构造了两阶段结构式启发式调度算法.第一阶段,将析取图分解为机床调度析取子图和搬运设备调度析取子图,提出一个双层递进启发式算法.上层利用分支思想求解机床调度析取子图,根据上层结果,求解搬运设备调度析取子图.在第一阶段解的基础上,第二阶段构造了基于块理论的调度优化启发式算法.最后对算法进行了仿真分析,结果表明所提出的算法是有效、可行的.
Take the scheduling problems of the Job Shop with material handling equipment into consideration, we established the non-linear programming model and modified disjunctive graph model. Afterwards, a two-stage structural heuristic algorithm was constructed to minimize the makespan. In the first stage, a hierarchical heuristic algorithm was constructed by dividing the disjunctive graph into sub-graphs of scheduling problems for the machines and handling equipment, respectively. The sub-graphs of scheduling problems for the machines in the upper level were solved based on a branch method, while for the handling equipment in the second level were according to the upper level results. In the second stage, a heuristic algorithm based on the block theory was presented to optimize the scheduling solutions. Finally, simulation experiments were designed and indicated that the proposed algorithm is valid and feasible.
出处
《东北大学学报（自然科学版）》
EI
CAS
CSCD
北大核心
2016年第1期138-142,共5页
Journal of Northeastern University(Natural Science)
基金
国家自然科学基金资助项目(61273035
71471135)
关键词
析取图
物料搬运
调度
JOB
SHOP
启发式算法
disjunctive graph
material handling
scheduling
Job Shop
heuristic algorithm
