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

Minimizing flowtime for paired tasks

Author

Listed:
  • Courtad, Brenda
  • Baker, Kenneth
  • Magazine, Michael
  • Polak, George

Abstract

Certain service and production systems require that a single processor complete, for each job, a pair of ordered tasks separated in time by a minimal required delay. In particular, circumstances, this mode of operation can characterize a physician in a hospital Emergency Department, a painting crew at a construction site, or a work station in a job shop. Motivated by these scenarios, we formulate an applicable scheduling problem and investigate its solution. To determine an optimal schedule, we formulate an appropriate mixed integer model in which the key lever for process improvement is the batching of tasks. We further show that two special cases of this problem can be optimally solved efficiently. To expedite decision-making, we propose heuristic approaches supported by spreadsheet based software. Numerical results are then presented and insights discussed.

Suggested Citation

  • Courtad, Brenda & Baker, Kenneth & Magazine, Michael & Polak, George, 2017. "Minimizing flowtime for paired tasks," European Journal of Operational Research, Elsevier, vol. 259(3), pages 818-828.
    • Handle: RePEc:eee:ejores:v:259:y:2017:i:3:p:818-828
    DOI: 10.1016/j.ejor.2016.10.012
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221716308451
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2016.10.012?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. Munier-Kordon, Alix & Rebaine, Djamal, 2010. "The two-machine open-shop problem with unit-time operations and time delays to minimize the makespan," European Journal of Operational Research, Elsevier, vol. 203(1), pages 42-49, May.
    2. Peter Brucker & Sigrid Knust & Ceyda Oğuz, 2006. "Scheduling chains with identical jobs and constant delays on a single machine," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 63(1), pages 63-75, February.
    3. Zhang, Xiandong & van de Velde, Steef, 2010. "On-line two-machine open shop scheduling with time lags," European Journal of Operational Research, Elsevier, vol. 204(1), pages 14-19, July.
    4. Potts, Chris N. & Kovalyov, Mikhail Y., 2000. "Scheduling with batching: A review," European Journal of Operational Research, Elsevier, vol. 120(2), pages 228-249, January.
    5. Alix Munier & Francis Sourd, 2003. "Scheduling chains on a single machine with non-negative time lags," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 57(1), pages 111-123, April.
    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. Miguel Angel Ortíz-Barrios & Juan-José Alfaro-Saíz, 2020. "Methodological Approaches to Support Process Improvement in Emergency Departments: A Systematic Review," IJERPH, MDPI, vol. 17(8), pages 1-41, April.

    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. J-B Wang & J-J Wang & P Ji, 2011. "Scheduling jobs with chain precedence constraints and deteriorating jobs," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(9), pages 1765-1770, September.
    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.
    3. Jason Pan & Chi-Shiang Su, 2015. "Two parallel machines problem with job delivery coordination and availability constraint," Annals of Operations Research, Springer, vol. 235(1), pages 653-664, December.
    4. Elisabeth Lübbecke & Marco E. Lübbecke & Rolf H. Möhring, 2019. "Ship Traffic Optimization for the Kiel Canal," Operations Research, INFORMS, vol. 67(3), pages 791-812, May.
    5. Shahaboddin Shamshirband & Mohammad Shojafar & A. Hosseinabadi & Maryam Kardgar & M. Nasir & Rodina Ahmad, 2015. "OSGA: genetic-based open-shop scheduling with consideration of machine maintenance in small and medium enterprises," Annals of Operations Research, Springer, vol. 229(1), pages 743-758, June.
    6. Gahm, Christian & Uzunoglu, Aykut & Wahl, Stefan & Ganschinietz, Chantal & Tuma, Axel, 2022. "Applying machine learning for the anticipation of complex nesting solutions in hierarchical production planning," European Journal of Operational Research, Elsevier, vol. 296(3), pages 819-836.
    7. Biber Nurit & Mor Baruch & Schlissel Yitzhak & Shapira Dana, 2023. "Lot scheduling involving completion time problems on identical parallel machines," Operational Research, Springer, vol. 23(1), pages 1-29, March.
    8. Shen, Liji & Buscher, Udo, 2012. "Solving the serial batching problem in job shop manufacturing systems," European Journal of Operational Research, Elsevier, vol. 221(1), pages 14-26.
    9. Anurag Agarwal & Varghese S. Jacob & Hasan Pirkul, 2006. "An Improved Augmented Neural-Network Approach for Scheduling Problems," INFORMS Journal on Computing, INFORMS, vol. 18(1), pages 119-128, February.
    10. Cheng, T. C. Edwin & Janiak, Adam & Kovalyov, Mikhail Y., 2001. "Single machine batch scheduling with resource dependent setup and processing times," European Journal of Operational Research, Elsevier, vol. 135(1), pages 177-183, November.
    11. Melouk, Sharif & Damodaran, Purushothaman & Chang, Ping-Yu, 2004. "Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing," International Journal of Production Economics, Elsevier, vol. 87(2), pages 141-147, January.
    12. Vo[ss], Stefan & Witt, Andreas, 2007. "Hybrid flow shop scheduling as a multi-mode multi-project scheduling problem with batching requirements: A real-world application," International Journal of Production Economics, Elsevier, vol. 105(2), pages 445-458, February.
    13. 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.
    14. A. Dolgui & M. Kovalyov & K. Shchamialiova, 2011. "Multi-product lot-sizing and sequencing on a single imperfect machine," Computational Optimization and Applications, Springer, vol. 50(3), pages 465-482, December.
    15. N. Brauner & Y. Crama & A. Grigoriev & J. Klundert, 2005. "A Framework for the Complexity of High-Multiplicity Scheduling Problems," Journal of Combinatorial Optimization, Springer, vol. 9(3), pages 313-323, May.
    16. Fowler, John W. & Mönch, Lars, 2022. "A survey of scheduling with parallel batch (p-batch) processing," European Journal of Operational Research, Elsevier, vol. 298(1), pages 1-24.
    17. Esswein, Carl & Billaut, Jean-Charles & Strusevich, Vitaly A., 2005. "Two-machine shop scheduling: Compromise between flexibility and makespan value," European Journal of Operational Research, Elsevier, vol. 167(3), pages 796-809, December.
    18. A. G. Leeftink & R. J. Boucherie & E. W. Hans & M. A. M. Verdaasdonk & I. M. H. Vliegen & P. J. Diest, 2018. "Batch scheduling in the histopathology laboratory," Flexible Services and Manufacturing Journal, Springer, vol. 30(1), pages 171-197, June.
    19. Selvarajah, Esaignani & Steiner, George, 2006. "Batch scheduling in a two-level supply chain--a focus on the supplier," European Journal of Operational Research, Elsevier, vol. 173(1), pages 226-240, August.
    20. Matin, Hossein N.Z. & Salmasi, Nasser & Shahvari, Omid, 2017. "Makespan minimization in flowshop batch processing problem with different batch compositions on machines," International Journal of Production Economics, Elsevier, vol. 193(C), pages 832-844.

    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:259:y:2017:i:3:p:818-828. 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.