IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v259y2017i1d10.1007_s10479-017-2503-6.html
   My bibliography  Save this article

Partially concurrent open shop scheduling with integral preemptions

Author

Listed:
  • Hagai Ilani

    (SCE – Shamoon College of Engineering)

  • Elad Shufan

    (SCE – Shamoon College of Engineering)

  • Tal Grinshpoun

    (Ariel University)

Abstract

Partially-concurrent open shop scheduling (PCOSS) was recently introduced as a common generalization of the well-known open shop scheduling model and the concurrent open shop scheduling model. PCOSS was shown to be NP-hard even when there is only one machine and all operations have unit processing time. In the present paper we study PCOSS problems with integral processing times that allow preemptions at integral time points. A special and simple subclass of the problems at focus is that of unit processing times, which is considered separately. For these two cases a schedule is related to the colouring of a graph called the conflict graph, which represents the operations that cannot be performed concurrently. This enables us to extract insights and solutions from the well-studied field of graph colouring and apply them to the recently introduced PCOSS model. We then focus on two special cases of the problem—the case where the conflict graph is perfect, and the case of uniform PCOSS, in which all the jobs, including their conflicts, are identical. The development of the PCOSS model was motivated from a real-life timetabling project of assigning technicians to a fleet of airplanes. The latter case of uniform PCOSS correlates to instances in which the fleet of airplanes is homogeneous.

Suggested Citation

  • Hagai Ilani & Elad Shufan & Tal Grinshpoun, 2017. "Partially concurrent open shop scheduling with integral preemptions," Annals of Operations Research, Springer, vol. 259(1), pages 157-171, December.
    • Handle: RePEc:spr:annopr:v:259:y:2017:i:1:d:10.1007_s10479-017-2503-6
    DOI: 10.1007/s10479-017-2503-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-017-2503-6
    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/s10479-017-2503-6?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. Wagneur, E. & Sriskandarajah, C., 1993. "Openshops with jobs overlap," European Journal of Operational Research, Elsevier, vol. 71(3), pages 366-378, 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. Hagai Ilani & Tal Grinshpoun & Elad Shufan, 2021. "Bounded colouring motivated by the limited resource partially concurrent open shop problem," Annals of Operations Research, Springer, vol. 302(2), pages 461-476, July.
    2. 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.

    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. Leung, Joseph Y-T. & Li, Haibing & Pinedo, Michael & Sriskandarajah, Chelliah, 2005. "Open shops with jobs overlap--revisited," European Journal of Operational Research, Elsevier, vol. 163(2), pages 569-571, June.
    2. Framinan, Jose M. & Perez-Gonzalez, Paz, 2018. "Order scheduling with tardiness objective: Improved approximate solutions," European Journal of Operational Research, Elsevier, vol. 266(3), pages 840-850.
    3. Tal Grinshpoun & Hagai Ilani & Elad Shufan, 2017. "The representation of partially-concurrent open shop problems," Annals of Operations Research, Springer, vol. 252(2), pages 455-469, May.
    4. Lin, B.M.T. & Kononov, A.V., 2007. "Customer order scheduling to minimize the number of late jobs," European Journal of Operational Research, Elsevier, vol. 183(2), pages 944-948, December.
    5. T.C. Edwin Cheng & Qingqin Nong & Chi To Ng, 2011. "Polynomial‐time approximation scheme for concurrent open shop scheduling with a fixed number of machines to minimize the total weighted completion time," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(8), pages 763-770, December.
    6. Ren-Xia Chen & Shi-Sheng Li, 2020. "Minimizing maximum delivery completion time for order scheduling with rejection," Journal of Combinatorial Optimization, Springer, vol. 40(4), pages 1044-1064, November.
    7. Wang, Guoqing & Cheng, T.C. Edwin, 2007. "Customer order scheduling to minimize total weighted completion time," Omega, Elsevier, vol. 35(5), pages 623-626, October.
    8. B. M. T. Lin & T. C. E. Cheng, 2011. "Scheduling with centralized and decentralized batching policies in concurrent open shops," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(1), pages 17-27, February.
    9. Framinan, Jose M. & Perez-Gonzalez, Paz & Fernandez-Viagas, Victor, 2019. "Deterministic assembly scheduling problems: A review and classification of concurrent-type scheduling models and solution procedures," European Journal of Operational Research, Elsevier, vol. 273(2), pages 401-417.
    10. Leung, Joseph Y.-T. & Li, Haibing & Pinedo, Michael, 2006. "Scheduling orders for multiple product types with due date related objectives," European Journal of Operational Research, Elsevier, vol. 168(2), pages 370-389, January.
    11. Leung, Joseph Y.-T. & Lee, C.Y. & Ng, C.W. & Young, G.H., 2008. "Preemptive multiprocessor order scheduling to minimize total weighted flowtime," European Journal of Operational Research, Elsevier, vol. 190(1), pages 40-51, October.
    12. 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.

    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:annopr:v:259:y:2017:i:1:d:10.1007_s10479-017-2503-6. 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.