Periodic Schedules for Bounded Timed Weighted Event Graphs

被引:21
作者
Benabid-Najjar, Abir [1 ]
Hanen, Claire [2 ]
Marchetti, Olivier [1 ]
Munier-Kordon, Alix [1 ]
机构
[1] Univ Paris 06, LIP6, F-75252 Paris, France
[2] Univ Paris 10, LIP6, F-92001 Nanterre, France
关键词
Periodic schedule; timed weighted event graphs (TWEGs); SYNCHRONOUS DATA-FLOW; PERFORMANCE EVALUATION; PARALLEL COMPUTATIONS; ALGORITHMS; SYSTEMS;
D O I
10.1109/TAC.2012.2191871
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Timed event graphs (TEGs) and timed weighted event graphs (TWEGs), which have multiple arc cardinalities, have been widely used for automated production systems such as robotic work cells or embedded systems. TWEGs are useful for modeling batch flows of entities such as batch arrivals or processing of jobs. Periodic schedules, that combine an explicit description of starting times and an easy implementation, are particularly interesting, and have been proved to be optimal for ordinary timed event graphs (TEGs). In this paper, we present polynomial algorithms to check the existence of periodic schedules of bounded TWEGs and to compute their optimal throughput. These results can be considered as generalizations of those for ordinary timed event graphs. We then establish that periodic schedules are suboptimal for TWEGs and may not exist even for a live TWEG. The gap between optimal throughput and throughput of an optimal periodic schedule is experimentally investigated for a subclass of TWEGs, namely timed weighted circuits.
引用
收藏
页码:1222 / 1232
页数:11
相关论文
共 29 条
[1]  
[Anonymous], 1984, Graphs and Algorithms
[2]  
[Anonymous], SYNCHRONISATION LINE
[3]  
[Anonymous], 1990, Introduction to Algorithms
[4]   LOOPED SCHEDULES FOR DATA-FLOW DESCRIPTIONS OF MULTIRATE SIGNAL-PROCESSING ALGORITHMS [J].
BHATTACHARYYA, SS ;
LEE, EA .
FORMAL METHODS IN SYSTEM DESIGN, 1994, 5 (03) :183-205
[5]   Tabu search algorithms for cyclic machine scheduling problems [J].
Brucker, P ;
Kampmeyer, T .
JOURNAL OF SCHEDULING, 2005, 8 (04) :303-322
[6]   A genetic approach to solving the problem of cyclic job shop scheduling with linear constraints [J].
Cavory, G ;
Dupas, R ;
Goncalves, G .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2005, 161 (01) :73-85
[7]   ALGEBRAIC TOOLS FOR THE PERFORMANCE EVALUATION OF DISCRETE EVENT SYSTEMS [J].
COHEN, G ;
MOLLER, P ;
QUADRAT, JP ;
VIOT, M .
PROCEEDINGS OF THE IEEE, 1989, 77 (01) :39-58
[8]  
Commoner F., 1971, Journal of Computer and System Sciences, V5, P511, DOI 10.1016/S0022-0000(71)80013-2
[9]  
DANTZIG GB, 1966, THEORY GRAPHS INT S, P77
[10]  
Dasdan A., 1999, Proceedings 1999 Design Automation Conference (Cat. No. 99CH36361), P37, DOI 10.1109/DAC.1999.781227