IDEAS home Printed from https://ideas.repec.org/a/spr/aqjoor/v21y2023i3d10.1007_s10288-022-00517-1.html
   My bibliography  Save this article

A parallel-machine scheduling problem with an antithetical property to maximize total weighted early work

Author

Listed:
  • Yunhong Min

    (Incheon National University)

  • Byung-Cheon Choi

    (Chungnam National University)

  • Myoung-Ju Park

    (Kyung Hee University)

  • Kyung Min Kim

    (Myongji University)

Abstract

In scheduling with early work, jobs are assigned to a machine by maximizing the parts of non-preemptive jobs executed before their due dates. This paper considers a weighted early work maximization problem on parallel, identical machines with an antithetical property, which holds that $$w_i \le w_j$$ w i ≤ w j implies $$d_i \ge d_j$$ d i ≥ d j for any two jobs i and j where $$w_j$$ w j and $$d_j$$ d j are weight and due date of job j, respectively. We show that the problem is weakly NP-hard. Due to the high complexity of dynamic programming, we develop three solution approaches: mixed-integer programming, heuristics, and a branch-and-bound algorithm. Through numerical experiments, we verify their performance.

Suggested Citation

  • Yunhong Min & Byung-Cheon Choi & Myoung-Ju Park & Kyung Min Kim, 2023. "A parallel-machine scheduling problem with an antithetical property to maximize total weighted early work," 4OR, Springer, vol. 21(3), pages 421-437, September.
  • Handle: RePEc:spr:aqjoor:v:21:y:2023:i:3:d:10.1007_s10288-022-00517-1
    DOI: 10.1007/s10288-022-00517-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10288-022-00517-1
    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/s10288-022-00517-1?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. Malgorzata Sterna & Kateryna Czerniachowska, 2017. "Polynomial Time Approximation Scheme for Two Parallel Machines Scheduling with a Common Due Date to Maximize Early Work," Journal of Optimization Theory and Applications, Springer, vol. 174(3), pages 927-944, September.
    2. Xin Chen & Malgorzata Sterna & Xin Han & Jacek Blazewicz, 2016. "Scheduling on parallel identical machines with late work criterion: Offline and online cases," Journal of Scheduling, Springer, vol. 19(6), pages 729-736, December.
    3. Chen, Xin & Liang, Yage & Sterna, Małgorzata & Wang, Wen & Błażewicz, Jacek, 2020. "Fully polynomial time approximation scheme to maximize early work on parallel machines with common due date," European Journal of Operational Research, Elsevier, vol. 284(1), pages 67-74.
    4. Dariusz Dereniowski & Wiesław Kubiak, 2018. "Shared processor scheduling," Journal of Scheduling, Springer, vol. 21(6), pages 583-593, December.
    5. Sterna, Malgorzata, 2011. "A survey of scheduling problems with late work criteria," Omega, Elsevier, vol. 39(2), pages 120-129, April.
    6. Enrique Gerstl & Gur Mosheiov, 2020. "Single machine scheduling to maximize the number of on-time jobs with generalized due-dates," Journal of Scheduling, Springer, vol. 23(3), pages 289-299, June.
    7. Kenneth R. Baker, 1984. "Sequencing Rules and Due-Date Assignments in a Job Shop," Management Science, INFORMS, vol. 30(9), pages 1093-1104, September.
    8. Byung-Cheon Choi & Myoung-Ju Park & Kyung Min Kim & Yunhong Min, 2021. "A Parallel Machine Scheduling Problem Maximizing Total Weighted Early Work," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 38(06), pages 1-16, December.
    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. Sterna, Małgorzata, 2021. "Late and early work scheduling: A survey," Omega, Elsevier, vol. 104(C).
    2. Jiang, Yiwei & Wu, Mengjing & Chen, Xin & Dong, Jianming & Cheng, T.C.E. & Blazewicz, Jacek & Ji, Min, 2024. "Online early work scheduling on parallel machines," European Journal of Operational Research, Elsevier, vol. 315(3), pages 855-862.
    3. Chen, Xin & Miao, Qian & Lin, Bertrand M.T. & Sterna, Malgorzata & Blazewicz, Jacek, 2022. "Two-machine flow shop scheduling with a common due date to maximize total early work," European Journal of Operational Research, Elsevier, vol. 300(2), pages 504-511.
    4. Pascale Bendotti & Luca Brunod Indrigo & Philippe Chrétienne & Bruno Escoffier, 2024. "Resource leveling: complexity of a unit execution time two-processor scheduling variant and related problems," Journal of Scheduling, Springer, vol. 27(6), pages 587-606, December.
    5. Györgyi, Péter & Kis, Tamás, 2020. "A common approximation framework for early work, late work, and resource leveling problems," European Journal of Operational Research, Elsevier, vol. 286(1), pages 129-137.
    6. Xiaofei Liu & Yajie Li & Weidong Li & Jinhua Yang, 2023. "Combinatorial approximation algorithms for the maximum bounded connected bipartition problem," Journal of Combinatorial Optimization, Springer, vol. 45(1), pages 1-21, January.
    7. Shi-Sheng Li & Jin-Jiang Yuan, 2020. "Single-machine scheduling with multi-agents to minimize total weighted late work," Journal of Scheduling, Springer, vol. 23(4), pages 497-512, August.
    8. Chen, Xin & Liang, Yage & Sterna, Małgorzata & Wang, Wen & Błażewicz, Jacek, 2020. "Fully polynomial time approximation scheme to maximize early work on parallel machines with common due date," European Journal of Operational Research, Elsevier, vol. 284(1), pages 67-74.
    9. Malgorzata Sterna & Kateryna Czerniachowska, 2017. "Polynomial Time Approximation Scheme for Two Parallel Machines Scheduling with a Common Due Date to Maximize Early Work," Journal of Optimization Theory and Applications, Springer, vol. 174(3), pages 927-944, September.
    10. Xin Chen & Sergey Kovalev & Małgorzata Sterna & Jacek Błażewicz, 2021. "Mirror scheduling problems with early work and late work criteria," Journal of Scheduling, Springer, vol. 24(5), pages 483-487, October.
    11. Christian Billing & Florian Jaehn & Thomas Wensing, 2020. "Fair task allocation problem," Annals of Operations Research, Springer, vol. 284(1), pages 131-146, January.
    12. Dvir Shabtay, 2023. "A new perspective on single-machine scheduling problems with late work related criteria," Annals of Operations Research, Springer, vol. 322(2), pages 947-966, March.
    13. Shabtay, Dvir & Mosheiov, Gur & Oron, Daniel, 2022. "Single machine scheduling with common assignable due date/due window to minimize total weighted early and late work," European Journal of Operational Research, Elsevier, vol. 303(1), pages 66-77.
    14. Chen, Rubing & Geng, Zhichao & Lu, Lingfa & Yuan, Jinjiang & Zhang, Yuan, 2022. "Pareto-scheduling of two competing agents with their own equal processing times," European Journal of Operational Research, Elsevier, vol. 301(2), pages 414-431.
    15. 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.
    16. Sarper, H. & Henry, M. C., 1996. "Combinatorial evaluation of six dispatching rules in a dynamic two-machine flow shop," Omega, Elsevier, vol. 24(1), pages 73-81, February.
    17. Baruch Mor & Gur Mosheiov & Dvir Shabtay, 2021. "Minimizing the total tardiness and job rejection cost in a proportionate flow shop with generalized due dates," Journal of Scheduling, Springer, vol. 24(6), pages 553-567, December.
    18. van Ooijen, H. P. G. & Bertrand, J. W. M., 2001. "Economic due-date setting in job-shops based on routing and workload dependent flow time distribution functions," International Journal of Production Economics, Elsevier, vol. 74(1-3), pages 261-268, December.
    19. Yuan Zhang & Jinjiang Yuan, 2019. "A note on a two-agent scheduling problem related to the total weighted late work," Journal of Combinatorial Optimization, Springer, vol. 37(3), pages 989-999, April.
    20. Meloni, Carlo & Pranzo, Marco & Samà, Marcella, 2022. "Evaluation of VaR and CVaR for the makespan in interval valued blocking job shops," International Journal of Production Economics, Elsevier, vol. 247(C).

    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:aqjoor:v:21:y:2023:i:3:d:10.1007_s10288-022-00517-1. 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.