Single Machine Scheduling with Rejection and Generalized Parameters | SpringerLink
Skip to main content
Springer Nature Link
Log in

Single Machine Scheduling with Rejection and Generalized Parameters

  • Conference paper
  • First Online:
Combinatorial Optimization and Applications (COCOA 2021)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 13135))

  • 993 Accesses

Abstract

In this paper, we consider three single machine scheduling problems with rejection and generalized parameters. Inspired by generalized due dates, we introduce three generalized parameters into our problems as follows: (1) generalized release dates, (2) generalized processing times, and (3) generalized rejection costs. In scheduling with generalized parameters, each parameter (for examples, release date, processing time or rejection cost) is assigned not to a specific job but to a job position. Furthermore, in scheduling with rejection, each job is either rejected and paid a corresponding rejection cost, or accepted and processed on the machine. The objective is to minimize the sum of the makespan of the accepted jobs and the total rejection cost of the rejected jobs. We show that the first scheduling problem with generalized release dates is binary NP-hard. Furthermore, we provide a pseudo-polynomial time algorithm, a 2-approximation algorithm and a full polynomial-time approximation scheme (FPTAS) for this problem. For the latter two problems with generalized processing times or generalized rejection costs, we provide a polynomial-time optimal algorithm, respectively.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 12583
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 15729
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Agnetis, A., Mosheiov, G.: Scheduling with job rejection and position-dependent processing times on proportionate flowshops. Optim. Lett. 11, 885–892 (2017)

    Article  MathSciNet  Google Scholar 

  2. Bartal, Y., Leonardi, S., Spaccamela, A.M., Stougie, J.: Multi-processor scheduling with rejection. SIAM J. Discret. Math. 13, 64–78 (2000)

    Article  Google Scholar 

  3. Chen, R.-X., Li, S.-S.: Minimizing maximum delivery completion time for order scheduling with rejection. J. Comb. Optim. 40(4), 1044–1064 (2020). https://doi.org/10.1007/s10878-020-00649-2

    Article  MathSciNet  MATH  Google Scholar 

  4. Du, J.Z., Leung, J.Y.T.: Minimizing total tardiness on one machine is NP-hard. Math. Oper. Res. 15, 483–495 (1990)

    Article  MathSciNet  Google Scholar 

  5. Gao, Y., Yuan, J.J.: Unary NP-hardness of minimizing the total deviation with generalized or assignable due dates. Discret. Appl. Math. 189, 49–52 (2015)

    Article  MathSciNet  Google Scholar 

  6. Gao, Y., Yuan, J.J.: Unary NP-hardness of minimizing total weighted tardiness with generalized due dates. Oper. Res. Lett. 44, 92–95 (2016)

    Article  MathSciNet  Google Scholar 

  7. Garey, M.R., Johnson, D.S.: Computers and Intractablity: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)

    MATH  Google Scholar 

  8. Gerstl, E., Mosheiov, G.: Single machine scheduling problems with generalized due-dates and job-rejection. Int. J. Prod. Res. 55, 3164–3172 (2017)

    Article  Google Scholar 

  9. Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287–326 (1979)

    Article  MathSciNet  Google Scholar 

  10. Hall, N.G.: Scheduling problems with generalized due dates. IIE Trans. 18, 220–222 (1986)

    Article  Google Scholar 

  11. Hall, N.G., Sethi, S.P., Srikandarajah, S.: On the complexity of generalized due date scheduling problems. Eur. J. Oper. Res. 51, 100–109 (1991)

    Article  Google Scholar 

  12. Hermelin, D., Pinedo, M., Shabtay, D., Talmon, N.: On the parameterized tractability of a single machine scheduling with rejection. Eur. J. Oper. Res. 273, 67–73 (2019)

    Article  MathSciNet  Google Scholar 

  13. Lawer, E.L.: Optimal sequencing a single machine subject to precedence constraints. Manage. Sci. 19, 544–546 (1973)

    Article  Google Scholar 

  14. Liu, P., Lu, X.: New approximation algorithms for machine scheduling with rejection on single and parallel machine. J. Comb. Optim. 40(4), 929–952 (2020). https://doi.org/10.1007/s10878-020-00642-9

    Article  MathSciNet  MATH  Google Scholar 

  15. Liu, Z.X.: Scheduling with partial rejection. Oper. Res. Lett. 48, 524–529 (2020)

    Article  MathSciNet  Google Scholar 

  16. Lu, L.F., Zhang, L.Q., Zhang, J., Zuo, L.L.: Single machine scheduling with outsourcing under different fill rates or quantity discount rates. Asia-Pacific J. Oper. Res. 37, 1950033 (2020)

    Article  MathSciNet  Google Scholar 

  17. Lu, L.F., Zhang, L.Q., Ou, J.W.: In-house production and outsourcing under different discount schemes on the total outsourcing cost. Ann. Oper. Res. 298, 361–374 (2021)

    Article  MathSciNet  Google Scholar 

  18. Ma, R., Guo, S.N.: Applying “Peeling Onion’’ approach for competitive analysis in online scheduling with rejection. Eur. J. Oper. Res. 290, 57–67 (2021)

    Article  MathSciNet  Google Scholar 

  19. Mor, B., Mosheiov, G., Shapira, D.: Flowshop scheduling with learning effect and job rejection. J. Sched. 23(6), 631–641 (2019). https://doi.org/10.1007/s10951-019-00612-y

    Article  MathSciNet  MATH  Google Scholar 

  20. Mor B., Mosheiov G., Shabtay D.: Minimizing the total tardiness and job rejection cost in a proportionate flow shop with generalized due dates. J. Sched. (2021). https://doi.org/10.1007/s10951-021-00697-4

  21. Mosheiov, G., Oron, D.: A note on the SPT heuristic for solving scheduling problems with generalized due dates. Comput. Oper. Res. 31, 645–655 (2004)

    Article  Google Scholar 

  22. Mosheiov, G., Oron, D., Shabtay, D.: Minimizing total late work on a single machine with generalized due-dates. Eur. J. Oper. Res. 293, 837C846 (2021)

    Article  MathSciNet  Google Scholar 

  23. Oron, D.: Two-agent scheduling problems under rejection budget constraints. Omega 102, 102313 (2021)

    Article  Google Scholar 

  24. Shabtay, D., Gaspar, N., Kaspi, M.: A survey on off-line scheduling with rejection. J. Sched. 16, 3–28 (2013)

    Article  MathSciNet  Google Scholar 

  25. Srikandarajah, S.: A note on the generalized due dates scheduling problem. Nav. Res. Logist. 37, 587–597 (1990)

    Article  MathSciNet  Google Scholar 

  26. Tanaka, K., Vlach, M.: Minimizing maximum absolute lateness and range of lateness under generalized due dates on a single machine. Ann. Oper. Res. 86, 507–526 (1999)

    Article  MathSciNet  Google Scholar 

  27. Wang, D.J., Yin, Y.Q., Jin, Y.: Parallel-machine rescheduling with job unavailability and rejection. Omega 81, 246–260 (2018)

    Article  Google Scholar 

  28. Yin, Y.Q., Cheng, S.R., Cheng, T.C.E., Wu, C.C., Wu, W.H.: Two-agent single-machine scheduling with assignable due dates. Appl. Math. Comput. 219, 1674–1685 (2012)

    MathSciNet  MATH  Google Scholar 

  29. Zhang, L.Q., Lu, L.F., Yuan, J.J.: Single machine scheduling with release dates and rejection. Eur. J. Oper. Res. 198, 975–978 (2009)

    Article  MathSciNet  Google Scholar 

  30. Zou, J., Yuan, J.J.: Single-machine scheduling with maintenance activities and rejection. Discret. Optim. 38, 100609 (2020)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgments

The authors thank the anonymous reviewers for their constructive comments. This research was supported by NSFCs (11901168, 11971443 and 11771406).

Author information

Authors and Affiliations

  1. School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, Henan, People’s Republic of China

    Xue Yu & Lingfa Lu

  2. College of Information and Management Science, Henan Agricultural University, Zhengzhou, Henan, People’s Republic of China

    Liqi Zhang

Authors
  1. Xue Yu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lingfa Lu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Liqi Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lingfa Lu .

Editor information

Editors and Affiliations

  1. University of Texas at Dallas, Richardson, TX, USA

    Ding-Zhu Du

  2. University of New Brunswick, Fredericton, NB, Canada

    Donglei Du

  3. Tianjin University of Technology, Tianjin, China

    Chenchen Wu

  4. Beijing University of Technology, Beijing, China

    Dachuan Xu

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Yu, X., Lu, L., Zhang, L. (2021). Single Machine Scheduling with Rejection and Generalized Parameters. In: Du, DZ., Du, D., Wu, C., Xu, D. (eds) Combinatorial Optimization and Applications. COCOA 2021. Lecture Notes in Computer Science(), vol 13135. Springer, Cham. https://doi.org/10.1007/978-3-030-92681-6_20

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-92681-6_20

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-92680-9

  • Online ISBN: 978-3-030-92681-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation