IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v36y2018i3d10.1007_s10878-018-0291-9.html
   My bibliography  Save this article

On the m-clique free interval subgraphs polytope: polyhedral analysis and applications

Author

Listed:
  • Mohammed-Albarra Hassan

    (Université de Lorraine)

  • Imed Kacem

    (Université de Lorraine)

  • Sébastien Martin

    (Université de Lorraine)

  • Izzeldin M. Osman

    (Sudan University of Science and Technology)

Abstract

In this paper we study the m-clique free interval subgraphs. We investigate the facial structure of the polytope defined as the convex hull of the incidence vectors associated with these subgraphs. We also present some facet-defining inequalities to strengthen the associated linear relaxation. As an application, the generalized open-shop problem with disjunctive constraints (GOSDC) is considered. Indeed, by a projection on a set of variables, the m-clique free interval subgraphs represent the solution of an integer linear program solving the GOSDC presented in this paper. Moreover, we propose exact and heuristic separation algorithms, which are exploited into a Branch-and-cut algorithm for solving the GOSDC. Finally, we present and discuss some computational results.

Suggested Citation

  • Mohammed-Albarra Hassan & Imed Kacem & Sébastien Martin & Izzeldin M. Osman, 2018. "On the m-clique free interval subgraphs polytope: polyhedral analysis and applications," Journal of Combinatorial Optimization, Springer, vol. 36(3), pages 1074-1101, October.
    • Handle: RePEc:spr:jcomop:v:36:y:2018:i:3:d:10.1007_s10878-018-0291-9
    DOI: 10.1007/s10878-018-0291-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-018-0291-9
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-018-0291-9?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    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. Mokotoff, E. & Chretienne, P., 2002. "A cutting plane algorithm for the unrelated parallel machine scheduling problem," European Journal of Operational Research, Elsevier, vol. 141(3), pages 515-525, September.
    2. Eva Vallada & Rubén Ruiz, 2012. "Scheduling Unrelated Parallel Machines with Sequence Dependent Setup Times and Weighted Earliness–Tardiness Minimization," Springer Optimization and Its Applications, in: Roger Z. Ríos-Mercado & Yasmín A. Ríos-Solís (ed.), Just-in-Time Systems, chapter 0, pages 67-90, Springer.
    3. K. Aardal & C. P. M. Van Hoesel, 1999. "Polyhedral techniques in combinatorial optimization II: applications and computations," Statistica Neerlandica, Netherlands Society for Statistics and Operations Research, vol. 53(2), pages 131-177, July.
    4. Nicholas G. Hall & Marc E. Posner, 2001. "Generating Experimental Data for Computational Testing with Machine Scheduling Applications," Operations Research, INFORMS, vol. 49(6), pages 854-865, December.
    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. Ahmadian, Mohammad Mahdi & Khatami, Mostafa & Salehipour, Amir & Cheng, T.C.E., 2021. "Four decades of research on the open-shop scheduling problem to minimize the makespan," European Journal of Operational Research, Elsevier, vol. 295(2), pages 399-426.
    2. Furini, Fabio & Ljubić, Ivana & San Segundo, Pablo & Zhao, Yanlu, 2021. "A branch-and-cut algorithm for the Edge Interdiction Clique Problem," European Journal of Operational Research, Elsevier, vol. 294(1), pages 54-69.

    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. Giorgi Tadumadze & Simon Emde & Heiko Diefenbach, 2020. "Exact and heuristic algorithms for scheduling jobs with time windows on unrelated parallel machines," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(2), pages 461-497, June.
    2. Karen Aardal & Cor Hurkens & Jan Karel Lenstra & Sergey Tiourine, 2002. "Algorithms for Radio Link Frequency Assignment: The Calma Project," Operations Research, INFORMS, vol. 50(6), pages 968-980, December.
    3. Lin, B.M.T. & Liu, S.T., 2008. "Maximizing the reward in the relocation problem with generalized due dates," International Journal of Production Economics, Elsevier, vol. 115(1), pages 55-63, September.
    4. Ali Kordmostafapour & Javad Rezaeian & Iraj Mahdavi & Mahdi Yar Farjad, 2022. "Scheduling unrelated parallel machine problem with multi-mode processing times and batch delivery cost," OPSEARCH, Springer;Operational Research Society of India, vol. 59(4), pages 1438-1470, December.
    5. Zhi-Long Chen & Nicholas G. Hall, 2010. "The Coordination of Pricing and Scheduling Decisions," Manufacturing & Service Operations Management, INFORMS, vol. 12(1), pages 77-92, April.
    6. Antonio J. Conejo & Nicholas G. Hall & Daniel Zhuoyu Long & Runhao Zhang, 2021. "Robust Capacity Planning for Project Management," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1533-1550, October.
    7. Absalom E Ezugwu & Olawale J Adeleke & Serestina Viriri, 2018. "Symbiotic organisms search algorithm for the unrelated parallel machines scheduling with sequence-dependent setup times," PLOS ONE, Public Library of Science, vol. 13(7), pages 1-23, July.
    8. Sobel, Matthew J. & Szmerekovsky, Joseph G. & Tilson, Vera, 2009. "Scheduling projects with stochastic activity duration to maximize expected net present value," European Journal of Operational Research, Elsevier, vol. 198(3), pages 697-705, November.
    9. Wenhui Zhao & Nicholas G. Hall & Zhixin Liu, 2020. "Project Evaluation and Selection with Task Failures," Production and Operations Management, Production and Operations Management Society, vol. 29(2), pages 428-446, February.
    10. Hartmann, Sönke, 2002. "Generating scenarios for simulation and optimization of container terminal logistics," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 564, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    11. George Vairaktarakis & Jamshid Hosseini, 2008. "Forming partnerships in a virtual factory," Annals of Operations Research, Springer, vol. 161(1), pages 87-102, July.
    12. Allahverdi, Ali & Aydilek, Harun, 2014. "Total completion time with makespan constraint in no-wait flowshops with setup times," European Journal of Operational Research, Elsevier, vol. 238(3), pages 724-734.
    13. Choi, Byung-Cheon & Yoon, Suk-Hun & Chung, Sung-Jin, 2007. "Minimizing maximum completion time in a proportionate flow shop with one machine of different speed," European Journal of Operational Research, Elsevier, vol. 176(2), pages 964-974, January.
    14. Leo Lopes & Kate Smith-Miles, 2013. "Generating Applicable Synthetic Instances for Branch Problems," Operations Research, INFORMS, vol. 61(3), pages 563-577, June.
    15. Vinod, V. & Sridharan, R., 2011. "Simulation modeling and analysis of due-date assignment methods and scheduling decision rules in a dynamic job shop production system," International Journal of Production Economics, Elsevier, vol. 129(1), pages 127-146, January.
    16. Aldowaisan, Tariq & Allahverdi, Ali, 2004. "New heuristics for m-machine no-wait flowshop to minimize total completion time," Omega, Elsevier, vol. 32(5), pages 345-352, October.
    17. Bentao Su & Naiming Xie & Yingjie Yang, 2021. "Hybrid genetic algorithm based on bin packing strategy for the unrelated parallel workgroup scheduling problem," Journal of Intelligent Manufacturing, Springer, vol. 32(4), pages 957-969, April.
    18. Joonyup Eun & Chang Sup Sung & Eun-Seok Kim, 2017. "Maximizing total job value on a single machine with job selection," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(9), pages 998-1005, September.
    19. Mokotoff, Ethel, 2004. "An exact algorithm for the identical parallel machine scheduling problem," European Journal of Operational Research, Elsevier, vol. 152(3), pages 758-769, February.
    20. Benjamin C. Shelbourne & Maria Battarra & Chris N. Potts, 2017. "The Vehicle Routing Problem with Release and Due Dates," INFORMS Journal on Computing, INFORMS, vol. 29(4), pages 705-723, November.

    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:spr:jcomop:v:36:y:2018:i:3:d:10.1007_s10878-018-0291-9. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.