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

A network flow-based method to solve performance cost and makespan open-shop scheduling problems with time-windows

Author

Listed:
  • Sedeño-Noda, A.
  • de Pablo, D. Alcaide López
  • González-Martín, C.

Abstract

This paper deals with several bicriteria open-shop scheduling problems where jobs are pre-emptable and their corresponding time-windows must be strictly respected. The criteria are a performance cost and the makespan. Network flow approaches are used in a lexmin procedure with a bounded makespan and the considered bicriteria problems are solved. Finally, the computational complexity of the algorithm and a numerical example are reported.

Suggested Citation

  • Sedeño-Noda, A. & de Pablo, D. Alcaide López & González-Martín, C., 2009. "A network flow-based method to solve performance cost and makespan open-shop scheduling problems with time-windows," European Journal of Operational Research, Elsevier, vol. 196(1), pages 140-154, July.
    • Handle: RePEc:eee:ejores:v:196:y:2009:i:1:p:140-154
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(08)00246-4
    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. Chen, Y. L., 1994. "Scheduling jobs to minimize total cost," European Journal of Operational Research, Elsevier, vol. 74(1), pages 111-119, April.
    2. A. Federgruen & H. Groenevelt, 1986. "Preemptive Scheduling of Uniform Machines by Ordinary Network Flow Techniques," Management Science, INFORMS, vol. 32(3), pages 341-349, March.
    3. Paolo Serafini, 1996. "Scheduling Jobs on Several Machines with the Job Splitting Property," Operations Research, INFORMS, vol. 44(4), pages 617-628, August.
    4. S. Thomas McCormick, 1999. "Fast Algorithms for Parametric Scheduling Come From Extensions to Parametric Maximum Flow," Operations Research, INFORMS, vol. 47(5), pages 744-756, October.
    5. James B. Orlin, 1993. "A Faster Strongly Polynomial Minimum Cost Flow Algorithm," Operations Research, INFORMS, vol. 41(2), pages 338-350, April.
    6. Sedeno-Noda, A. & Alcaide, D. & Gonzalez-Martin, C., 2006. "Network flow approaches to pre-emptive open-shop scheduling problems with time-windows," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1501-1518, November.
    7. Chen, Y. L., 1995. "A parametric maximum flow algorithm for bipartite graphs with applications," European Journal of Operational Research, Elsevier, vol. 80(1), pages 226-235, January.
    8. Yookun Cho & Sartaj Sahni, 1981. "Preemptive Scheduling of Independent Jobs with Release and Due Times on Open, Flow and Job Shops," Operations Research, INFORMS, vol. 29(3), pages 511-522, June.
    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. Mehdi Ghiyasvand, 2015. "Solving the parametric bipartite maximum flow problem in unbalanced and closure bipartite graphs," Annals of Operations Research, Springer, vol. 229(1), pages 397-408, June.

    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. Sedeno-Noda, A. & Alcaide, D. & Gonzalez-Martin, C., 2006. "Network flow approaches to pre-emptive open-shop scheduling problems with time-windows," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1501-1518, November.
    2. Shioura, Akiyoshi & Shakhlevich, Natalia V. & Strusevich, Vitaly A., 2018. "Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: A review of solution approaches," European Journal of Operational Research, Elsevier, vol. 266(3), pages 795-818.
    3. S. Thomas McCormick, 1999. "Fast Algorithms for Parametric Scheduling Come From Extensions to Parametric Maximum Flow," Operations Research, INFORMS, vol. 47(5), pages 744-756, October.
    4. Akiyoshi Shioura & Natalia V. Shakhlevich & Vitaly A. Strusevich, 2020. "Scheduling problems with controllable processing times and a common deadline to minimize maximum compression cost," Journal of Global Optimization, Springer, vol. 76(3), pages 471-490, March.
    5. Akiyoshi Shioura & Natalia V. Shakhlevich & Vitaly A. Strusevich, 2016. "Application of Submodular Optimization to Single Machine Scheduling with Controllable Processing Times Subject to Release Dates and Deadlines," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 148-161, February.
    6. Rubing Chen & Jinjiang Yuan & C.T. Ng & T.C.E. Cheng, 2019. "Single‐machine scheduling with deadlines to minimize the total weighted late work," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(7), pages 582-595, October.
    7. Mehdi Ghiyasvand, 2015. "Solving the parametric bipartite maximum flow problem in unbalanced and closure bipartite graphs," Annals of Operations Research, Springer, vol. 229(1), pages 397-408, June.
    8. 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.
    9. Lin, Hung-Tso & Lee, Hong-Tau & Pan, Wen-Jung, 2008. "Heuristics for scheduling in a no-wait open shop with movable dedicated machines," International Journal of Production Economics, Elsevier, vol. 111(2), pages 368-377, February.
    10. Jun-Ho Lee & Hyun-Jung Kim, 2021. "A heuristic algorithm for identical parallel machine scheduling: splitting jobs, sequence-dependent setup times, and limited setup operators," Flexible Services and Manufacturing Journal, Springer, vol. 33(4), pages 992-1026, December.
    11. Liaw, Ching-Fang, 2005. "Scheduling preemptive open shops to minimize total tardiness," European Journal of Operational Research, Elsevier, vol. 162(1), pages 173-183, April.
    12. Shoshana Anily, 1996. "The vehicle‐routing problem with delivery and back‐haul options," Naval Research Logistics (NRL), John Wiley & Sons, vol. 43(3), pages 415-434, April.
    13. László A. Végh, 2017. "A Strongly Polynomial Algorithm for Generalized Flow Maximization," Mathematics of Operations Research, INFORMS, vol. 42(1), pages 179-211, January.
    14. Amirmahdi Tafreshian & Neda Masoud & Yafeng Yin, 2020. "Frontiers in Service Science: Ride Matching for Peer-to-Peer Ride Sharing: A Review and Future Directions," Service Science, INFORMS, vol. 12(2-3), pages 44-60, June.
    15. László A. Végh, 2014. "Concave Generalized Flows with Applications to Market Equilibria," Mathematics of Operations Research, INFORMS, vol. 39(2), pages 573-596, May.
    16. Akiyoshi Shioura & Natalia V. Shakhlevich & Vitaly A. Strusevich, 2017. "Machine Speed Scaling by Adapting Methods for Convex Optimization with Submodular Constraints," INFORMS Journal on Computing, INFORMS, vol. 29(4), pages 724-736, November.
    17. Ravindra K. Ahuja & Dorit S. Hochbaum, 2008. "TECHNICAL NOTE---Solving Linear Cost Dynamic Lot-Sizing Problems in O ( n log n ) Time," Operations Research, INFORMS, vol. 56(1), pages 255-261, February.
    18. Sharma, Anuj & Verma, Vanita & Kaur, Prabhjot & Dahiya, Kalpana, 2015. "An iterative algorithm for two level hierarchical time minimization transportation problem," European Journal of Operational Research, Elsevier, vol. 246(3), pages 700-707.
    19. Zsolt T. Kosztyán & István Szalkai, 2020. "Multimode resource-constrained project scheduling in flexible projects," Journal of Global Optimization, Springer, vol. 76(1), pages 211-241, January.
    20. Klamroth, Kathrin & Wiecek, Margaret M., 2001. "A time-dependent multiple criteria single-machine scheduling problem," European Journal of Operational Research, Elsevier, vol. 135(1), pages 17-26, 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:eee:ejores:v:196:y:2009:i:1:p:140-154. 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.