IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v197y2009i2p532-540.html
   My bibliography  Save this article

A sufficient condition for the liveness of weighted event graphs

Author

Listed:
  • Marchetti, Olivier
  • Munier-Kordon, Alix

Abstract

Weighted event graphs (in short WEG) are widely used to model industrial problems and embedded systems. In an optimization context, fast algorithms checking the liveness of a marked WEG must be developed. The purpose of this paper is to develop a sufficient condition of liveness of a WEG. We first show that any unitary WEG can be transformed into a graph in which the values of the arcs adjacent to any transition depend on the transition. Then, a simple sufficient condition of liveness can be expressed on this new graph and polynomially computed. This condition is shown to be necessary for a circuit with two transitions.

Suggested Citation

  • Marchetti, Olivier & Munier-Kordon, Alix, 2009. "A sufficient condition for the liveness of weighted event graphs," European Journal of Operational Research, Elsevier, vol. 197(2), pages 532-540, September.
    • Handle: RePEc:eee:ejores:v:197:y:2009:i:2:p:532-540
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(08)00590-0
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Hanen, Claire, 1994. "Study of a NP-hard cyclic scheduling problem: The recurrent job-shop," European Journal of Operational Research, Elsevier, vol. 72(1), pages 82-101, January.
    2. Cavory, G. & Dupas, R. & Goncalves, G., 2005. "A genetic approach to solving the problem of cyclic job shop scheduling with linear constraints," European Journal of Operational Research, Elsevier, vol. 161(1), pages 73-85, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Palmer, Geraint I. & Harper, Paul R. & Knight, Vincent A., 2018. "Modelling deadlock in open restricted queueing networks," European Journal of Operational Research, Elsevier, vol. 266(2), pages 609-621.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Idir Hamaz & Laurent Houssin & Sonia Cafieri, 2018. "A robust basic cyclic scheduling problem," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(3), pages 291-313, September.
    2. Jacomine Grobler & Andries Engelbrecht & Schalk Kok & Sarma Yadavalli, 2010. "Metaheuristics for the multi-objective FJSP with sequence-dependent set-up times, auxiliary resources and machine down time," Annals of Operations Research, Springer, vol. 180(1), pages 165-196, November.
    3. Félix Quinton & Idir Hamaz & Laurent Houssin, 2020. "A mixed integer linear programming modelling for the flexible cyclic jobshop problem," Annals of Operations Research, Springer, vol. 285(1), pages 335-352, February.
    4. Peter Brucker & Thomas Kampmeyer, 2008. "Cyclic job shop scheduling problems with blocking," Annals of Operations Research, Springer, vol. 159(1), pages 161-181, March.
    5. Imai, Akio & Yamakawa, Yukiko & Huang, Kuancheng, 2014. "The strategic berth template problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 72(C), pages 77-100.
    6. Přemysl Šůcha & Zdeněk Hanzálek, 2011. "A cyclic scheduling problem with an undetermined number of parallel identical processors," Computational Optimization and Applications, Springer, vol. 48(1), pages 71-90, January.
    7. Penn, Michal & Raviv, Tal, 2009. "An algorithm for the maximum revenue jobshop problem," European Journal of Operational Research, Elsevier, vol. 193(2), pages 437-450, March.
    8. Hamaz, Idir & Houssin, Laurent & Cafieri, Sonia, 2024. "The robust cyclic job shop problem," European Journal of Operational Research, Elsevier, vol. 312(3), pages 855-865.
    9. Hanen, Claire & Hanzalek, Zdenek, 2020. "Grouping tasks to save energy in a cyclic scheduling problem: A complexity study," European Journal of Operational Research, Elsevier, vol. 284(2), pages 445-459.
    10. Munier, A., 1996. "The complexity of a cyclic scheduling problem with identical machines and precedence constraints," European Journal of Operational Research, Elsevier, vol. 91(3), pages 471-480, June.
    11. Zeng, Daniel D. & Dror, Moshe & Chen, Hsinchun, 2006. "Efficient scheduling of periodic information monitoring requests," European Journal of Operational Research, Elsevier, vol. 173(2), pages 583-599, September.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:197:y:2009:i:2:p:532-540. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.