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

On the parameterized tractability of single machine scheduling with rejection

Author

Listed:
  • Hermelin, Danny
  • Pinedo, Michael
  • Shabtay, Dvir
  • Talmon, Nimrod

Abstract

In this paper we study a single machine scheduling problem with rejection. In such a scheduling problem, the scheduler can reject to process a job in the shop at a certain cost. Our objective is to minimize the total completion time of the jobs to be processed in the shop, given that the total rejection cost will not exceed a certain predefined threshold. The problem is known to be NP-hard, and to better investigate its hardness our objective is to study whether the problem becomes tractable when some specific natural parameters are of a limited size. The analysis is done by using the theory of parameterized complexity and includes the following parameters: the cardinality of the set of accepted jobs, the number of different processing times, the number of different rejection costs, the maximal processing time, and the maximal rejection cost. We show that the problem is W[1]-hard for the first parameter, while it is fixed-parameterized tractable for all other parameters.

Suggested Citation

  • Hermelin, Danny & Pinedo, Michael & Shabtay, Dvir & Talmon, Nimrod, 2019. "On the parameterized tractability of single machine scheduling with rejection," European Journal of Operational Research, Elsevier, vol. 273(1), pages 67-73.
    • Handle: RePEc:eee:ejores:v:273:y:2019:i:1:p:67-73
    DOI: 10.1016/j.ejor.2018.07.038
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037722171830660X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2018.07.038?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. René Bevern & Rolf Niedermeier & Ondřej Suchý, 2017. "A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack," Journal of Scheduling, Springer, vol. 20(3), pages 255-265, June.
    2. Dvir Shabtay & Nufar Gaspar & Liron Yedidsion, 2012. "A bicriteria approach to scheduling a single machine with job rejection and positional penalties," Journal of Combinatorial Optimization, Springer, vol. 23(4), pages 395-424, May.
    3. Dušan Knop & Martin Koutecký, 2018. "Scheduling meets n-fold integer programming," Journal of Scheduling, Springer, vol. 21(5), pages 493-503, October.
    4. Slotnick, Susan A., 2011. "Order acceptance and scheduling: A taxonomy and review," European Journal of Operational Research, Elsevier, vol. 212(1), pages 1-11, July.
    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. Matthias Bentert & Robert Bredereck & Péter Györgyi & Andrzej Kaczmarczyk & Rolf Niedermeier, 2023. "A multivariate complexity analysis of the material consumption scheduling problem," Journal of Scheduling, Springer, vol. 26(4), pages 369-382, August.
    2. 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.
    3. Lingfa Lu & Liqi Zhang, 2023. "Scheduling problems with rejection to minimize the k-th power of the makespan plus the total rejection cost," Journal of Combinatorial Optimization, Springer, vol. 46(1), pages 1-17, August.
    4. Ou, Jinwen & Lu, Lingfa & Zhong, Xueling, 2023. "Parallel-batch scheduling with rejection: Structural properties and approximation algorithms," European Journal of Operational Research, Elsevier, vol. 310(3), pages 1017-1032.
    5. Imed Kacem & Hans Kellerer, 2024. "Minimizing the maximum lateness for scheduling with release times and job rejection," Journal of Combinatorial Optimization, Springer, vol. 48(3), pages 1-22, October.
    6. Danny Hermelin & Dvir Shabtay & Chen Zelig & Michael Pinedo, 2022. "A general scheme for solving a large set of scheduling problems with rejection in FPT time," Journal of Scheduling, Springer, vol. 25(2), pages 229-255, April.
    7. Mosheiov, Gur & Oron, Daniel & Shabtay, Dvir, 2021. "Minimizing total late work on a single machine with generalized due-dates," European Journal of Operational Research, Elsevier, vol. 293(3), pages 837-846.
    8. Baruch Mor & Gur Mosheiov & Dana Shapira, 2021. "Single machine lot scheduling with optional job-rejection," Journal of Combinatorial Optimization, Springer, vol. 41(1), pages 1-11, January.
    9. Mohamadreza Dabiri & Mehdi Yazdani & Bahman Naderi & Hassan Haleh, 2022. "Modeling and solution methods for hybrid flow shop scheduling problem with job rejection," Operational Research, Springer, vol. 22(3), pages 2721-2765, July.
    10. Klaus Heeger & Danny Hermelin & George B. Mertzios & Hendrik Molter & Rolf Niedermeier & Dvir Shabtay, 2023. "Equitable scheduling on a single machine," Journal of Scheduling, Springer, vol. 26(2), pages 209-225, April.
    11. Ma, Ran & Guo, Sainan & Miao, Cuixia, 2021. "A semi-online algorithm and its competitive analysis for parallel-machine scheduling problem with rejection," Applied Mathematics and Computation, Elsevier, vol. 392(C).
    12. Ma, Ran & Guo, Sainan, 2021. "Applying “Peeling Onion” approach for competitive analysis in online scheduling with rejection," European Journal of Operational Research, Elsevier, vol. 290(1), pages 57-67.

    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. Danny Hermelin & Dvir Shabtay & Chen Zelig & Michael Pinedo, 2022. "A general scheme for solving a large set of scheduling problems with rejection in FPT time," Journal of Scheduling, Springer, vol. 25(2), pages 229-255, April.
    2. Ou, Jinwen & Zhong, Xueling, 2017. "Bicriteria order acceptance and scheduling with consideration of fill rate," European Journal of Operational Research, Elsevier, vol. 262(3), pages 904-907.
    3. 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.
    4. de Weerdt, Mathijs & Baart, Robert & He, Lei, 2021. "Single-machine scheduling with release times, deadlines, setup times, and rejection," European Journal of Operational Research, Elsevier, vol. 291(2), pages 629-639.
    5. Danny Hermelin & Shlomo Karhi & Michael Pinedo & Dvir Shabtay, 2021. "New algorithms for minimizing the weighted number of tardy jobs on a single machine," Annals of Operations Research, Springer, vol. 298(1), pages 271-287, March.
    6. Wang, Dujuan & Yin, Yunqiang & Cheng, T.C.E., 2018. "Parallel-machine rescheduling with job unavailability and rejection," Omega, Elsevier, vol. 81(C), pages 246-260.
    7. Matthias Bentert & Robert Bredereck & Péter Györgyi & Andrzej Kaczmarczyk & Rolf Niedermeier, 2023. "A multivariate complexity analysis of the material consumption scheduling problem," Journal of Scheduling, Springer, vol. 26(4), pages 369-382, August.
    8. 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.
    9. Weidong Li & Qianna Cui, 2018. "Vector scheduling with rejection on a single machine," 4OR, Springer, vol. 16(1), pages 95-104, March.
    10. Wang, Xiuli & Cheng, T.C.E., 2015. "A heuristic for scheduling jobs on two identical parallel machines with a machine availability constraint," International Journal of Production Economics, Elsevier, vol. 161(C), pages 74-82.
    11. 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.
    12. Öner-Közen, Miray & Minner, Stefan, 2017. "Impact of priority sequencing decisions on on-time probability and expected tardiness of orders in make-to-order production systems with external due-dates," European Journal of Operational Research, Elsevier, vol. 263(2), pages 524-539.
    13. Wang, Xiuli & Xie, Xingzi & Cheng, T.C.E., 2013. "Order acceptance and scheduling in a two-machine flowshop," International Journal of Production Economics, Elsevier, vol. 141(1), pages 366-376.
    14. Altendorfer, Klaus & Minner, Stefan, 2015. "Influence of order acceptance policies on optimal capacity investment with stochastic customer required lead times," European Journal of Operational Research, Elsevier, vol. 243(2), pages 555-565.
    15. Li, Feng & Xu, Shifu & Xu, Zhou, 2023. "New exact and approximation algorithms for integrated production and transportation scheduling with committed delivery due dates and order acceptance," European Journal of Operational Research, Elsevier, vol. 306(1), pages 127-140.
    16. Belleh Fontem & Megan Price, 2021. "Joint client selection and contract design for a risk-averse commodity broker in a two-echelon supply chain," Annals of Operations Research, Springer, vol. 307(1), pages 111-138, December.
    17. Boysen, Nils & Briskorn, Dirk & Schwerdfeger, Stefan, 2019. "Matching supply and demand in a sharing economy: Classification, computational complexity, and application," European Journal of Operational Research, Elsevier, vol. 278(2), pages 578-595.
    18. Chen, Heng & Hu, Zhangchen & Solak, Senay, 2021. "Improved delivery policies for future drone-based delivery systems," European Journal of Operational Research, Elsevier, vol. 294(3), pages 1181-1201.
    19. Anderson Rogério Faia Pinto & Antonio Fernando Crepaldi & Marcelo Seido Nagano, 2018. "A Genetic Algorithm applied to pick sequencing for billing," Journal of Intelligent Manufacturing, Springer, vol. 29(2), pages 405-422, February.
    20. Lingfa Lu & Liqi Zhang & Jinwen Ou, 2021. "In-house production and outsourcing under different discount schemes on the total outsourcing cost," Annals of Operations Research, Springer, vol. 298(1), pages 361-374, March.

    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:273:y:2019:i:1:p:67-73. 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.