IDEAS home Printed from https://ideas.repec.org/a/spr/operea/v18y2018i3d10.1007_s12351-017-0355-0.html
   My bibliography  Save this article

Scheduling efficiency on correlated parallel machine scheduling problems

Author

Listed:
  • Yang-Kuei Lin

    (Feng Chia University)

Abstract

This research examines correlated parallel machine scheduling problems since they better reflect real world manufacturing environments. We consider the problem of scheduling correlated parallel machines to minimize makespan and scheduling correlated parallel machines with release times to minimize total weighted tardiness. We consider different levels and combination of machine correlations and job correlations in the processing times. Mathematical models are applied to evaluate the influence of machine correlation and job correlation on computation results and computation time. Computational results show that as the machine and job correlations increase, the problem instances become more difficult for mathematical models to solve. This implies that branch-and-bound based algorithms might have more difficulty solving parallel machine scheduling problems with correlations than without correlations. We can use this result to forecast branch-and-bound based algorithm performance on correlated parallel machine scheduling problems and thus improve process behavior by selecting the most suitable algorithms.

Suggested Citation

  • Yang-Kuei Lin, 2018. "Scheduling efficiency on correlated parallel machine scheduling problems," Operational Research, Springer, vol. 18(3), pages 603-624, October.
    • Handle: RePEc:spr:operea:v:18:y:2018:i:3:d:10.1007_s12351-017-0355-0
    DOI: 10.1007/s12351-017-0355-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s12351-017-0355-0
    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/s12351-017-0355-0?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. Fanjul-Peyro, Luis & Ruiz, Rubén, 2010. "Iterated greedy local search methods for unrelated parallel machine scheduling," European Journal of Operational Research, Elsevier, vol. 207(1), pages 55-69, November.
    2. SOUSA, Jorge P. & WOLSEY, Laurence A., 1992. "A time indexed formulation of non-preemptive single machine scheduling problems," LIDAM Reprints CORE 984, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. 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.
    4. Tjark Vredeveld & Cor Hurkens, 2002. "Experimental Comparison of Approximation Algorithms for Scheduling Unrelated Parallel Machines," INFORMS Journal on Computing, INFORMS, vol. 14(2), pages 175-189, May.
    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. Yang-Kuei Lin & Tzu-Yueh Yin, 2022. "Generating bicriteria schedules for correlated parallel machines involving tardy jobs and weighted completion time," Annals of Operations Research, Springer, vol. 319(2), pages 1655-1688, December.

    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. Wang, Haibo & Alidaee, Bahram, 2019. "Effective heuristic for large-scale unrelated parallel machines scheduling problems," Omega, Elsevier, vol. 83(C), pages 261-274.
    2. 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.
    3. F. Rodriguez & C. Blum & C. García-Martínez & M. Lozano, 2012. "GRASP with path-relinking for the non-identical parallel machine scheduling problem with minimising total weighted completion times," Annals of Operations Research, Springer, vol. 201(1), pages 383-401, December.
    4. Kedad-Sidhoum, Safia & Solis, Yasmin Rios & Sourd, Francis, 2008. "Lower bounds for the earliness-tardiness scheduling problem on parallel machines with distinct due dates," European Journal of Operational Research, Elsevier, vol. 189(3), pages 1305-1316, September.
    5. Kerem Bülbül & Philip Kaminsky & Candace Yano, 2004. "Flow shop scheduling with earliness, tardiness, and intermediate inventory holding costs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 51(3), pages 407-445, April.
    6. de Lima, Vinícius L. & Alves, Cláudio & Clautiaux, François & Iori, Manuel & Valério de Carvalho, José M., 2022. "Arc flow formulations based on dynamic programming: Theoretical foundations and applications," European Journal of Operational Research, Elsevier, vol. 296(1), pages 3-21.
    7. Baptiste, Philippe & Sadykov, Ruslan, 2010. "Time-indexed formulations for scheduling chains on a single machine: An application to airborne radars," European Journal of Operational Research, Elsevier, vol. 203(2), pages 476-483, June.
    8. Abdessamad Ait El Cadi & Omar Souissi & Rabie Ben Atitallah & Nicolas Belanger & Abdelhakim Artiba, 2018. "Mathematical programming models for scheduling in a CPU/FPGA architecture with heterogeneous communication delays," Journal of Intelligent Manufacturing, Springer, vol. 29(3), pages 629-640, March.
    9. Sanjeev Swami & Jehoshua Eliashberg & Charles B. Weinberg, 1999. "SilverScreener: A Modeling Approach to Movie Screens Management," Marketing Science, INFORMS, vol. 18(3), pages 352-372.
    10. 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.
    11. 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.
    12. Balasubramanian, Hari & Fowler, John & Keha, Ahmet & Pfund, Michele, 2009. "Scheduling interfering job sets on parallel machines," European Journal of Operational Research, Elsevier, vol. 199(1), pages 55-67, November.
    13. Artur Alves Pessoa & Teobaldo Bulhões & Vitor Nesello & Anand Subramanian, 2022. "Exact Approaches for Single Machine Total Weighted Tardiness Batch Scheduling," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1512-1530, May.
    14. Yepes-Borrero, Juan C. & Perea, Federico & Ruiz, Rubén & Villa, Fulgencia, 2021. "Bi-objective parallel machine scheduling with additional resources during setups," European Journal of Operational Research, Elsevier, vol. 292(2), pages 443-455.
    15. Averbakh, Igor & Pereira, Jordi, 2015. "Network construction problems with due dates," European Journal of Operational Research, Elsevier, vol. 244(3), pages 715-729.
    16. Zhi Pei & Mingzhong Wan & Ziteng Wang, 2020. "A new approximation algorithm for unrelated parallel machine scheduling with release dates," Annals of Operations Research, Springer, vol. 285(1), pages 397-425, February.
    17. Leo Lopes & Kate Smith-Miles, 2013. "Generating Applicable Synthetic Instances for Branch Problems," Operations Research, INFORMS, vol. 61(3), pages 563-577, June.
    18. Francis Sourd, 2009. "New Exact Algorithms for One-Machine Earliness-Tardiness Scheduling," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 167-175, February.
    19. Pasquale Avella & Maurizio Boccia & Bernardo D’Auria, 2005. "Near-Optimal Solutions of Large-Scale Single-Machine Scheduling Problems," INFORMS Journal on Computing, INFORMS, vol. 17(2), pages 183-191, May.
    20. 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.

    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:operea:v:18:y:2018:i:3:d:10.1007_s12351-017-0355-0. 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.