An extended event graph with negative places and tokens for time window constraints

We introduce places with negative holding times and tokens with negative token counts into a timed event graph in order to model and analyze time window constraints. We extend the enabling and firing rules for such an extended event graph named a negative event graph (NEG). We develop necessary and sufficient conditions based on the circuits for which the NEG is live, that is, an infinite sequence of feasible firing epochs exist for each transition. We prove that the minimum cycle time is the same as the maximum circuit ratio of the circuits with positive token counts. We also show that when there exists circuits with negative token counts, the maximum cycle time is bounded and the same as the minimum circuit ratio of such circuits. A scheduling example for a robot-based cluster tool with wafer residency time constraints for semiconductor manufacturing is explained.
Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
Issue Date
2005-10
Language
ENG
Keywords

ARMED CLUSTER TOOLS; CYCLIC JOB SHOPS; SCHEDULES

Citation

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, v.2, no.4, pp.319 - 332

ISSN
1545-5955
DOI
10.1109/TASE.2005.851236
URI
http://hdl.handle.net/10203/1699
Appears in Collection
IE-Journal Papers(저널논문)
Files in This Item
22_NEG-Print.pdf(699.28 kB)Download
  • Hit : 652
  • Download : 594
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button
⊙ Cited 66 items in WoSClick to see citing articles inrecords_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0