Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Single machine batch scheduling to minimize the weighted number of late jobs

  • Published:
Mathematical Methods of Operations Research Aims and scope Submit manuscript

Abstract

The single machine batch scheduling problem to minimize the weighted number of late jobs is studied. In this problem,n jobs have to be processed on a single machine. Each job has a processing time, a due date and a weight. Jobs may be combined to form batches containing contiguously scheduled jobs. For each batch, a constant set-up time is needed before the first job of this batch is processed. The completion time of each job in the batch coincides with the completion time of the last job in this batch. A job is late if it is completed after its due date. A schedule specifies the sequence of jobs and the size of each batch, i.e. the number of jobs it contains. The objective is to find a schedule which minimizes the weighted number of late jobs. This problem isNP-hard even if all due dates are equal. For the general case, we present a dynamic programming algorithm which solves the problem with equal weights inO(n 3) time. We formulate a certain scaled problem and show that our dynamic programming algorithm applied to this scaled problem provides a fully polynomial approximation scheme for the original problem. Each algorithm of this scheme has a time requirement ofO(n 3/ɛ +n 3 logn). A side result is anO(n logn) algorithm for the problem of minimizing the maximum weight of late jobs.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Albers S, Bracker P (1993) The complexity of one-machine batching problems. Discrete Applied Mathematics 47:87–107

    Google Scholar 

  2. Brucker P (1991) Scheduling problems in connection with flexible production systems. In Proceedings, 1991 IEEE Int Conf on Robotics and Automation 1778–1783

  3. Cheng TCE, Gordon VS (1992) On batch delivery scheduling on a single machine, Preprint N 9, Institute of Engineering Cybernetics, Belarus Academy of Sciences, Minsk

    Google Scholar 

  4. Cheng TCE, Gordon VS, Kovalyov MY (1994) Single machine scheduling with batch deliveries. (in submission)

  5. Cheng TCE, Kahlbacher HG (1993) Scheduling with delivery and earliness penalties. Asia-Pacific Journal of Operational Research 10:145–152

    Google Scholar 

  6. Coffman EG, Nozari A, Yannakakis M (1989) Optimal scheduling of products with two subassemblies on a single machine. Operations Research 37:426–436

    Google Scholar 

  7. Coffman EG, Yannakakis M, Magazine MJ, Santos C (1990) Batch sizing and sequencing on a single machine. Annals of Operations Research 26:135–147

    Google Scholar 

  8. Dobson G, Karmarkar US, Rummel JL (1987) Batching to minimize flow times on one machine. Management Science 33:784–799

    Google Scholar 

  9. Garey MR, Johnson DS (1979) Computers and intractability: A guide to the theory ofN P-completenss. W.H. Freeman and Co, New York

    Google Scholar 

  10. Hochbaum DS, Landy D (1994) Scheduling with batching: minimizing the weighted number of tardy jobs, (to appear in Operations Research Letters)

  11. Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW (eds) Complexity of Computer Computations. Plenum Press, New York 85–103

    Google Scholar 

  12. Kovalyov MY (1994) Improving the complexities of approximation algorithms for optimization problems. Operations Research Letters 16:79–86

    Google Scholar 

  13. Lawler EL, Moore JM (1969) A functional equation and its application to resource allocation and sequencing problems. Management Science 16:77–84

    Google Scholar 

  14. Naddef D, Santos C (1988) One-pass batching algorithms for the one machine problem. Discrete Applied Mathematics 21:133–145

    Google Scholar 

  15. Potts CN, Van Wassenhove LN (1991) Integrating scheduling with batching and lot-sizing: A review of algorithms and complexity. Journal of the Operational Research Society 43:395–406

    Google Scholar 

  16. Rothkopf MH (1966) Scheduling independent tasks on parallel processors. Management Science 12:437–447

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Universität Osnabrück, 49069, Osnabrück, Germany

    Peter Brucker

  2. Institute of Engineering Cybernetics, Surganova 6, 220012, Minsk, Belarus

    Mikhail Y. Kovalyov

Authors
  1. Peter Brucker
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mikhail Y. Kovalyov
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Supported by INTAS Project 93-257.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Brucker, P., Kovalyov, M.Y. Single machine batch scheduling to minimize the weighted number of late jobs. Mathematical Methods of Operations Research 43, 1–8 (1996). https://doi.org/10.1007/BF01303431

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01303431

Key words

Search

Navigation