IDEAS home Printed from https://ideas.repec.org/a/spr/operea/v22y2022i4d10.1007_s12351-021-00684-9.html
   My bibliography  Save this article

Scheduling in parallel machines with two objectives: analysis of factors that influence the Pareto frontier

Author

Listed:
  • Julio Mar-Ortiz

    (Universidad Autónoma de Tamaulipas)

  • Alex J. Ruiz Torres

    (Universidad de Puerto Rico)

  • Belarmino Adenso-Díaz

    (Universidad de Oviedo)

Abstract

This paper explores the characteristics of solutions when scheduling jobs in a shop with parallel machines. Three classical objective functions were considered: makespan, total completion time, and total tardiness. These three criteria were combined in pairs, resulting in three bi-objective formulations. These formulations were solved using the ε-constraint method to obtain a Pareto frontier for each pair. The objective of the research is to evaluate the Pareto set of efficient schedules to characterize the solution sets. The characterization of the solutions sets is based on two performance metrics: the span of the objective functions' values for the points in the frontier and their closeness to the ideal point. Results that consider four experimental factors indicate that when the makespan is one of the objective functions, the range of the processing times among jobs has a significant influence on the characteristics of the Pareto frontier. Simultaneously, the slack of due dates is the most relevant factor when total tardiness is considered.

Suggested Citation

  • Julio Mar-Ortiz & Alex J. Ruiz Torres & Belarmino Adenso-Díaz, 2022. "Scheduling in parallel machines with two objectives: analysis of factors that influence the Pareto frontier," Operational Research, Springer, vol. 22(4), pages 4585-4605, September.
    • Handle: RePEc:spr:operea:v:22:y:2022:i:4:d:10.1007_s12351-021-00684-9
    DOI: 10.1007/s12351-021-00684-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s12351-021-00684-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/s12351-021-00684-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. Biskup, Dirk & Herrmann, Jan & Gupta, Jatinder N.D., 2008. "Scheduling identical parallel machines to minimize total tardiness," International Journal of Production Economics, Elsevier, vol. 115(1), pages 134-142, September.
    2. Della Croce, Federico & T’kindt, Vincent & Ploton, Olivier, 2021. "Parallel machine scheduling with minimum number of tardy jobs: Approximation and exponential algorithms," Applied Mathematics and Computation, Elsevier, vol. 397(C).
    3. J. Behnamian & S. M. T. Fatemi Ghomi, 2016. "A survey of multi-factory scheduling," Journal of Intelligent Manufacturing, Springer, vol. 27(1), pages 231-249, February.
    4. Eduardo Pérez & Rahul R. Ambati & Alex J. Ruiz-Torres, 2018. "Maximising the number of on-time jobs on parallel servers with sequence dependent deteriorating processing times and periodic maintenance," International Journal of Operational Research, Inderscience Enterprises Ltd, vol. 32(3), pages 267-289.
    5. M. Ehrgott & S. Ruzika, 2008. "Improved ε-Constraint Method for Multiobjective Programming," Journal of Optimization Theory and Applications, Springer, vol. 138(3), pages 375-396, September.
    6. Simon Thevenin & Nicolas Zufferey & Jean-Yves Potvin, 2017. "Makespan minimisation for a parallel machine scheduling problem with preemption and job incompatibility," International Journal of Production Research, Taylor & Francis Journals, vol. 55(6), pages 1588-1606, March.
    7. 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.
    8. Nagar, Amit & Haddock, Jorge & Heragu, Sunderesh, 1995. "Multiple and bicriteria scheduling: A literature survey," European Journal of Operational Research, Elsevier, vol. 81(1), pages 88-104, February.
    9. S. M. Mousavi & I. Mahdavi & J. Rezaeian & M. Zandieh, 2018. "An efficient bi-objective algorithm to solve re-entrant hybrid flow shop scheduling with learning effect and setup times," Operational Research, Springer, vol. 18(1), pages 123-158, April.
    10. Gupta, Jatinder N. D. & Ruiz-Torres, Alex J., 2000. "Minimizing makespan subject to minimum total flow-time on identical parallel machines," European Journal of Operational Research, Elsevier, vol. 125(2), pages 370-380, September.
    11. Chuleeporn Kusoncum & Kanchana Sethanan & Rapeepan Pitakaso & Richard F. Hartl, 2021. "Heuristics with novel approaches for cyclical multiple parallel machine scheduling in sugarcane unloading systems," International Journal of Production Research, Taylor & Francis Journals, vol. 59(8), pages 2479-2497, April.
    12. Lin, Yang-Kuei & Fowler, John W. & Pfund, Michele E., 2013. "Multiple-objective heuristics for scheduling unrelated parallel machines," European Journal of Operational Research, Elsevier, vol. 227(2), pages 239-253.
    13. Erenay, Fatih Safa & Sabuncuoglu, Ihsan & Toptal, Aysegül & Tiwari, Manoj Kumar, 2010. "New solution methods for single machine bicriteria scheduling problem: Minimization of average flowtime and number of tardy jobs," European Journal of Operational Research, Elsevier, vol. 201(1), pages 89-98, February.
    14. Cheng-Hsiung Lee, 2018. "A dispatching rule and a random iterated greedy metaheuristic for identical parallel machine scheduling to minimize total tardiness," International Journal of Production Research, Taylor & Francis Journals, vol. 56(6), pages 2292-2308, March.
    Full references (including those not matched with items on IDEAS)

    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. Neufeld, Janis S. & Schulz, Sven & Buscher, Udo, 2023. "A systematic review of multi-objective hybrid flow shop scheduling," European Journal of Operational Research, Elsevier, vol. 309(1), pages 1-23.
    2. Jianxin Fang & Brenda Cheang & Andrew Lim, 2023. "Problems and Solution Methods of Machine Scheduling in Semiconductor Manufacturing Operations: A Survey," Sustainability, MDPI, vol. 15(17), pages 1-44, August.
    3. Ganesan, Viswanath Kumar & Sivakumar, Appa Iyer, 2006. "Scheduling in static jobshops for minimizing mean flowtime subject to minimum total deviation of job completion times," International Journal of Production Economics, Elsevier, vol. 103(2), pages 633-647, October.
    4. Ullrich, Christian A., 2013. "Integrated machine scheduling and vehicle routing with time windows," European Journal of Operational Research, Elsevier, vol. 227(1), pages 152-165.
    5. Chen, Bo & Zhang, Xiandong, 2019. "Scheduling with time-of-use costs," European Journal of Operational Research, Elsevier, vol. 274(3), pages 900-908.
    6. Vincent T’kindt & Federico Della Croce & Mathieu Liedloff, 2022. "Moderate exponential-time algorithms for scheduling problems," 4OR, Springer, vol. 20(4), pages 533-566, December.
    7. Burcu Yılmaz Kaya & Aylin Adem & Metin Dağdeviren, 2020. "A DSS-Based Novel Approach Proposition Employing Decision Techniques for System Design," International Journal of Information Technology & Decision Making (IJITDM), World Scientific Publishing Co. Pte. Ltd., vol. 19(02), pages 413-445, March.
    8. Vitayasak, Srisatja & Pongcharoen, Pupong & Hicks, Chris, 2017. "A tool for solving stochastic dynamic facility layout problems with stochastic demand using either a Genetic Algorithm or modified Backtracking Search Algorithm," International Journal of Production Economics, Elsevier, vol. 190(C), pages 146-157.
    9. Zeynep Adak & Mahmure Övül Arıoğlu Akan & Serol Bulkan, 0. "Multiprocessor open shop problem: literature review and future directions," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-23.
    10. Steuer, Ralph E. & Utz, Sebastian, 2023. "Non-contour efficient fronts for identifying most preferred portfolios in sustainability investing," European Journal of Operational Research, Elsevier, vol. 306(2), pages 742-753.
    11. Choo Jun Tan & Siew Chin Neoh & Chee Peng Lim & Samer Hanoun & Wai Peng Wong & Chu Kong Loo & Li Zhang & Saeid Nahavandi, 2019. "Application of an evolutionary algorithm-based ensemble model to job-shop scheduling," Journal of Intelligent Manufacturing, Springer, vol. 30(2), pages 879-890, February.
    12. Daniel Schubert & André Scholz & Gerhard Wäscher, 2017. "Integrated Order Picking and Vehicle Routing with Due Dates," FEMM Working Papers 170007, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    13. Donghun Lee & Hyeongwon Kang & Dongjin Lee & Jeonwoo Lee & Kwanho Kim, 2023. "Deep Reinforcement Learning-Based Scheduler on Parallel Dedicated Machine Scheduling Problem towards Minimizing Total Tardiness," Sustainability, MDPI, vol. 15(4), pages 1-14, February.
    14. Erenay, Fatih Safa & Sabuncuoglu, Ihsan & Toptal, Aysegül & Tiwari, Manoj Kumar, 2010. "New solution methods for single machine bicriteria scheduling problem: Minimization of average flowtime and number of tardy jobs," European Journal of Operational Research, Elsevier, vol. 201(1), pages 89-98, February.
    15. Rojanee Homchalee & Rapeepan Pitakaso & Orawich Kumphon, 2023. "Minimizing Energy Usage and Makespan of Elevator Operation in Rush Hour Using Multi-Objective Variable Neighborhood Strategy Adaptive Search with a Mobile Application," Mathematics, MDPI, vol. 11(8), pages 1-22, April.
    16. Tao Dai & Xiangqi Fan, 2021. "Multi-Stove Scheduling for Sustainable On-Demand Food Delivery," Sustainability, MDPI, vol. 13(23), pages 1-13, November.
    17. Hanane Krim & Nicolas Zufferey & Jean-Yves Potvin & Rachid Benmansour & David Duvivier, 2022. "Tabu search for a parallel-machine scheduling problem with periodic maintenance, job rejection and weighted sum of completion times," Journal of Scheduling, Springer, vol. 25(1), pages 89-105, February.
    18. Masar Al-Rabeeah & Santosh Kumar & Ali Al-Hasani & Elias Munapo & Andrew Eberhard, 2019. "Bi-objective integer programming analysis based on the characteristic equation," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 10(5), pages 937-944, October.
    19. Framinan, Jose M. & Leisten, Rainer & Ruiz-Usano, Rafael, 2002. "Efficient heuristics for flowshop sequencing with the objectives of makespan and flowtime minimisation," European Journal of Operational Research, Elsevier, vol. 141(3), pages 559-569, September.
    20. Mensendiek, Arne & Gupta, Jatinder N.D. & Herrmann, Jan, 2015. "Scheduling identical parallel machines with fixed delivery dates to minimize total tardiness," European Journal of Operational Research, Elsevier, vol. 243(2), pages 514-522.

    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:22:y:2022:i:4:d:10.1007_s12351-021-00684-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.