多工件类型的无等待机器人制造单元调度研究  

Optimal scheduling of no-wait robotic cell with multi-type parts

作　　者：晏鹏宇[1] 车阿大[1] 杨乃定[1] 钟娜[1] 

机构地区：[1]西北工业大学管理学院,西安710072

出　　处：《计算机工程与应用》2009年第9期13-17,共5页Computer Engineering and Applications

基　　金：国家自然科学基金No.50605052;国家教育部新世纪人才支持计划No.NCET-06-0875~~

摘　　要：首先将加工多工件类型的无等待机器人制造单元调度问题分解为两个相互联系的子问题:(1)多类型工件进入系统的排序问题;(2)机器人搬运作业的排序问题。从解决工件使用工作站和机器人可能发生的冲突入手,以工件进入系统的时间为决策变量,利用禁止区间法建立了问题的数学模型,并开发了一基于图论的动态分枝定界最优算法。最后,通过一自动化印刷电路板(PCB)生产线和随机算例验证了算法的有效性。It is shown that finding an optimal schedule for a no-wait robotic cell with multi-type parts is equivalent to finding two correlative sequences：parts input sequence and robot move sequence.The problem is solved by avoiding two types of conflicts which may occur when two or more parts use a workstation or the robot at the same time.The entering times of parts are choosen as the decision variables and a mathematic model is developed with the notion of prohibited intervals.A dynamic branch and bound algorithm based on the graph theory is proposed to search the optimal solution.The computational results on a automated printed circuit board （PCB） electroplating line and some random tests indicate that the algorithm is effective.

关 键 词：机器人制造单元 调度 多工件类型 无等待 分枝定界算法 

分 类 号：O211.1[理学—概率论与数理统计]