东北大学学报（自然科学版）

东北大学学报:自然科学版 ›› 2016, Vol. 37 ›› Issue (1): 138-142.DOI: 10.12068/j.issn.1005-3026.2016.01.029

• 机械工程 • 上一篇    下一篇

基于析取图考虑物料搬运的Job Shop调度算法

周炳海， 周淑美， 赵猛   

  1. (同济大学 机械与能源工程学院， 上海201804)
  • 收稿日期:2014-05-14 修回日期:2014-05-14 出版日期:2016-01-15 发布日期:2016-01-08
  • 通讯作者: 周炳海
  • 作者简介:周炳海(1965-)，男，浙江浦江人，同济大学教授，博士生导师.
  • 基金资助:
    国家自然科学基金资助项目(61273035，71471135).

Disjunctive Graph-Based Scheduling Algorithm for Job Shop with Material Handling

ZHOU Bing-hai， ZHOU Shu-mei， ZHAO Meng   

  1. School of Mechanical Engineering， Tongji University， Shanghai 201804， China.
  • Received:2014-05-14 Revised:2014-05-14 Online:2016-01-15 Published:2016-01-08
  • Contact: ZHOU Bing-hai
  • About author:-
  • Supported by:
    -

RichHTML

0

PDF (PC)

942

摘要： 为有效解决考虑物料搬运设备的Job Shop调度问题，建立了非线性规划模型及改进析取图模型.在此基础上，以最小化最大完工时间makespan为调度目标，构造了两阶段结构式启发式调度算法.第一阶段，将析取图分解为机床调度析取子图和搬运设备调度析取子图，提出一个双层递进启发式算法.上层利用分支思想求解机床调度析取子图，根据上层结果，求解搬运设备调度析取子图.在第一阶段解的基础上，第二阶段构造了基于块理论的调度优化启发式算法.最后对算法进行了仿真分析，结果表明所提出的算法是有效、可行的.

关键词: 析取图, 物料搬运, 调度, Job Shop, 启发式算法

Abstract: 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.

Key words: disjunctive graph, material handling, scheduling, Job Shop, heuristic algorithm

中图分类号: