A polynomial algorithm for multi-robot 2-cyclic scheduling in a no-wait robotic cell

被引：27
作者：
Che, Ada [1 ]
Hu, Hongjian [1 ]
Chabrol, Michelle [2 ]
Gourgand, Michel [2 ]
机构：
[1] NW Polytech Univ, Sch Management, Xian 710072, Peoples R China
[2] Univ Clermont Ferrand, LIMOS, CNRS UMR 6158, F-63173 Aubiere, France
来源：
COMPUTERS & OPERATIONS RESEARCH | 2011年 / 38卷 / 09期
基金：
中国国家自然科学基金;
关键词：
Scheduling; No-wait robotic cell; Multiple robots; Polynomial algorithm; PROCESSING TIMES; HOIST; FLOWSHOP; CONSTRAINTS; WINDOW; LINE;
D O I：
10.1016/j.cor.2010.11.008
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
This paper addresses the multi-robot 2-cyclic scheduling problem in a no-wait robotic cell where exactly two parts enter and leave the cell during each cycle and multiple robots on a single track are responsible for transporting parts between machines. We develop a polynomial algorithm to find the minimum number of robots for all feasible cycle times. Consequently, the optimal cycle time for any given number of robots can be obtained with the algorithm. The proposed algorithm can be implemented in O(N(7)) time, where N is the number of machines in the considered robotic cell. (C) 2010 Elsevier Ltd. All rights reserved.
引用
收藏
页码：1275 / 1285
页数：11
相关论文
共 36 条
[1]   Part sequencing in three-machine no-wait robotic cells [J].
Agnetis, A ;
Pacciarelli, D .
OPERATIONS RESEARCH LETTERS, 2000, 27 (04) :185-192
[2]   Scheduling no-wait robotic cells with two and three machines [J].
Agnetis, A .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 123 (02) :303-314
[3]   Robotic cell scheduling with operational flexibility [J].
Akturk, MS ;
Gultekin, H ;
Karasan, OE .
DISCRETE APPLIED MATHEMATICS, 2005, 145 (03) :334-348
[4]   Identical part production in cyclic robotic cells: Concepts, overview and open questions [J].
Brauner, Nadia .
DISCRETE APPLIED MATHEMATICS, 2008, 156 (13) :2480-2492
[5]   Scheduling of coupled tasks and one-machine no-wait robotic cells [J].
Brauner, Nadia ;
Finke, Gerd ;
Lehoux-Lebacque, Vassilissa ;
Potts, Chris ;
Whitehead, Jonathan .
COMPUTERS & OPERATIONS RESEARCH, 2009, 36 (02) :301-307
[6]   Multi-degree cyclic scheduling of two robots in a no-wait flowshop [J].
Che, A ;
Chu, CB .
IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2005, 2 (02) :173-183
[7]   A polynomial algorithm for 2-degree cyclic robot scheduling [J].
Che, A ;
Chu, CB ;
Levner, E .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2003, 145 (01) :31-44
[8]   Multicyclic hoist scheduling with constant processing times [J].
Che, A ;
Chu, CB ;
Chu, F .
IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, 2002, 18 (01) :69-80
[9]   Optimal scheduling of material handling devices in a PCB production line: Problem formulation and a polynomial algorithm [J].
Che, Ada ;
Chu, Chengbin .
MATHEMATICAL PROBLEMS IN ENGINEERING, 2008, 2008
[10]   Multi-degree cyclic scheduling of a no-wait robotic cell with multiple robots [J].
Che, Ada ;
Chu, Chengbin .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2009, 199 (01) :77-88
1234