IDEAS home Printed from https://ideas.repec.org/a/eee/oprepe/v12y2024ics2214716024000034.html

Pareto-optimal front generation for the bi-objective JIT scheduling problems with a piecewise linear trade-off between objectives

Author

Listed:
  • Babu, Sona
  • Girish, B.S.

Abstract

This paper proposes a novel method of Pareto front generation from a set of piecewise linear trade-off curves typically encountered in bi-objective just-in-time (JIT) scheduling problems. We have considered the simultaneous minimization of total weighted earliness and tardiness (TWET) and total flowtime (TFT) objectives in a single-machine scheduling problem (SMSP) with distinct job due dates allowing inserted idle times in the schedules. An optimal timing algorithm (OTA) is presented to generate the trade-off curve between TWET and TFT for a given sequence of jobs. The proposed method of Pareto front generation generates a Pareto-optimal front constituted of both line segments and points. Further, we employ a simple local search method to generate sequences of jobs and their respective trade-off curves, which are trimmed and merged to generate the Pareto-optimal front using the proposed method. Computational results obtained using problem instances of different sizes reveal the efficiency of the proposed OTA and the Pareto front generation method over the state-of-the-art methodologies adopted from the literature.

Suggested Citation

  • Babu, Sona & Girish, B.S., 2024. "Pareto-optimal front generation for the bi-objective JIT scheduling problems with a piecewise linear trade-off between objectives," Operations Research Perspectives, Elsevier, vol. 12(C).
    • Handle: RePEc:eee:oprepe:v:12:y:2024:i:c:s2214716024000034
    DOI: 10.1016/j.orp.2024.100299
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S2214716024000034
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.orp.2024.100299?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

    for a different version of it.

    References listed on IDEAS

    as
    1. 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.
    2. Guang Feng & Hoong Lau, 2008. "Efficient algorithms for machine scheduling problems with earliness and tardiness penalties," Annals of Operations Research, Springer, vol. 159(1), pages 83-95, March.
    3. Soylu, Banu, 2015. "Heuristic approaches for biobjective mixed 0–1 integer linear programming problems," European Journal of Operational Research, Elsevier, vol. 245(3), pages 690-703.
    4. Soylu, Banu, 2018. "The search-and-remove algorithm for biobjective mixed-integer linear programming problems," European Journal of Operational Research, Elsevier, vol. 268(1), pages 281-299.
    5. W J Chen, 2006. "Minimizing total flow time in the single-machine scheduling problem with periodic maintenance," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(4), pages 410-415, April.
    6. Wan, Guohua & Yen, Benjamin P. -C., 2002. "Tabu search for single machine scheduling with distinct due windows and weighted earliness/tardiness penalties," European Journal of Operational Research, Elsevier, vol. 142(2), pages 271-281, October.
    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. Huang, Xue & He, Hongyu & Bei, Hong-Bin & Zhao, Yanzhi & Wang, Ning & Chang, Yu, 2025. "Group-scheduling with simultaneous learning effects and convex resource allocations," Operations Research Perspectives, Elsevier, vol. 15(C).
    2. Babu, Sona & Girish, B.S., 2025. "Neighbourhood search-based metaheuristics for the bi-objective Pareto optimization of total weighted earliness-tardiness and makespan in a JIT single machine scheduling problem," Operations Research Perspectives, Elsevier, vol. 14(C).

    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. Nathan Adelgren & Akshay Gupte, 2022. "Branch-and-Bound for Biobjective Mixed-Integer Linear Programming," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 909-933, March.
    2. Babu, Sona & Girish, B.S., 2025. "Neighbourhood search-based metaheuristics for the bi-objective Pareto optimization of total weighted earliness-tardiness and makespan in a JIT single machine scheduling problem," Operations Research Perspectives, Elsevier, vol. 14(C).
    3. Arthur Kramer & Anand Subramanian, 2019. "A unified heuristic and an annotated bibliography for a large class of earliness–tardiness scheduling problems," Journal of Scheduling, Springer, vol. 22(1), pages 21-57, February.
    4. Soylu, Banu & Katip, Hatice, 2019. "A multiobjective hub-airport location problem for an airline network design," European Journal of Operational Research, Elsevier, vol. 277(2), pages 412-425.
    5. Fröhlich von Elmbach, Alexander & Scholl, Armin & Walter, Rico, 2019. "Minimizing the maximal ergonomic burden in intra-hospital patient transportation," European Journal of Operational Research, Elsevier, vol. 276(3), pages 840-854.
    6. Aritra Pal & Hadi Charkhgard, 2019. "A Feasibility Pump and Local Search Based Heuristic for Bi-Objective Pure Integer Linear Programming," INFORMS Journal on Computing, INFORMS, vol. 31(1), pages 115-133, February.
    7. Sourd, Francis, 2005. "Optimal timing of a sequence of tasks with general completion costs," European Journal of Operational Research, Elsevier, vol. 165(1), pages 82-96, August.
    8. Yunqiang Yin & Jianyou Xu & T. C. E. Cheng & Chin‐Chia Wu & Du‐Juan Wang, 2016. "Approximation schemes for single‐machine scheduling with a fixed maintenance activity to minimize the total amount of late work," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(2), pages 172-183, March.
    9. Konur, Dinçer & Campbell, James F. & Monfared, Sepideh A., 2017. "Economic and environmental considerations in a stochastic inventory control model with order splitting under different delivery schedules among suppliers," Omega, Elsevier, vol. 71(C), pages 46-65.
    10. Lakmali Weerasena & Aniekan Ebiefung & Anthony Skjellum, 2022. "Design of a heuristic algorithm for the generalized multi-objective set covering problem," Computational Optimization and Applications, Springer, vol. 82(3), pages 717-751, July.
    11. Hanane Krim & Rachid Benmansour & David Duvivier & Daoud Aït-Kadi & Said Hanafi, 2020. "Heuristics for the single machine weighted sum of completion times scheduling problem with periodic maintenance," Computational Optimization and Applications, Springer, vol. 75(1), pages 291-320, January.
    12. Aseem K. Mishra & Divya Shrivastava & Devesh Tarasia & Abdur Rahim, 2022. "Joint optimization of production scheduling and group preventive maintenance planning in multi-machine systems," Annals of Operations Research, Springer, vol. 316(1), pages 401-444, September.
    13. Missaoui, Ahmed & Ruiz, Rubén, 2022. "A parameter-Less iterated greedy method for the hybrid flowshop scheduling problem with setup times and due date windows," European Journal of Operational Research, Elsevier, vol. 303(1), pages 99-113.
    14. Kacem, Imed & Chu, Chengbin, 2008. "Efficient branch-and-bound algorithm for minimizing the weighted sum of completion times on a single machine with one availability constraint," International Journal of Production Economics, Elsevier, vol. 112(1), pages 138-150, March.
    15. Imed Kacem, 2009. "Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval," Journal of Combinatorial Optimization, Springer, vol. 17(2), pages 117-133, February.
    16. Sourd, Francis, 2005. "Punctuality and idleness in just-in-time scheduling," European Journal of Operational Research, Elsevier, vol. 167(3), pages 739-751, December.
    17. Hendel, Yann & Sourd, Francis, 2006. "Efficient neighborhood search for the one-machine earliness-tardiness scheduling problem," European Journal of Operational Research, Elsevier, vol. 173(1), pages 108-119, August.
    18. Shirvani, Nargess & Ruiz, Rubén & Shadrokh, Shahram, 2014. "Cyclic scheduling of perishable products in parallel machine with release dates, due dates and deadlines," International Journal of Production Economics, Elsevier, vol. 156(C), pages 1-12.
    19. Soylu, Banu, 2018. "The search-and-remove algorithm for biobjective mixed-integer linear programming problems," European Journal of Operational Research, Elsevier, vol. 268(1), pages 281-299.
    20. Simon Thevenin & Nicolas Zufferey & Marino Widmer, 2016. "Order acceptance and scheduling with earliness and tardiness penalties," Journal of Heuristics, Springer, vol. 22(6), pages 849-890, December.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:oprepe:v:12:y:2024:i:c:s2214716024000034. 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.journals.elsevier.com/operations-research-perspectives .

    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.