Skip to main content
SpringerLink
Log in

Batch sizing and job sequencing on a single machine

  • Single-Machine Scheduling
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

We study a single-machine scheduling problem in which the items to be processed have to be batched as well as sequenced. Since processed items become available in batches, flow times are defined to be the same for all items in the same batch. A constant set-up delay is incurred between consecutive batches. For any fixed, but arbitrary item sequence, we present an algorithm that finds a sequence of batches such that the total flow time of the items is minimized; we prove that for a set ofn items, the algorithm runs inO(n) time. We show that, among all sequences, the one leading to the minimum flow time has the items in non-decreasing order of running times. Thus, the optimal algorithm for the combined problem, called thebatch-sizing problem, runs inO(n logn) time. We also prove that this algorithm yields an improved solution to a scheduling problem recently studied by Baker [1].

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

Access this article

Log in via an institution

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. K.R. Baker, Scheduling the production of components at a common facility, Trans. IIE 20(1988)32–35.

    Article  Google Scholar 

  2. J.L. Bruno and P.J. Downey, Complexity of task sequencing with deadlines, set-up time and change-over costs, SIAM J. Comput. 7(1978)393–404.

    Article  Google Scholar 

  3. E.G. Coffman, Jr., A. Nozari and M. Yannakakis, Optimal scheduling of products with two subassemblies on a single machine, Oper. Res. 37(1989)426–436.

    Article  Google Scholar 

  4. G. Dobson, U. Karmarkar and J. Rummel, Batching to minimize flow times on one machine, Manag. Sci. 33–6(1987)784–799.

    Article  Google Scholar 

  5. D. Naddef and C. Santos, One-pass batching algorithms for the one-machine problem, Discr. Appl. Math. 21(1988)133–146.

    Article  Google Scholar 

  6. C. Santos and M.J. Magazine, Batching in single operation manufacturing systems, Oper. Res. Lett. 4(1985)99–102.

    Article  Google Scholar 

Download references

Author information

Author notes

  1. C. Santos

    Present address: Measurement and Manufacturing Systems, Hewlett-Packard Laboratories, 94303-0867, Palo Alto, CA, USA

Authors and Affiliations

  1. AT&T Bell Laboratories, 07974, Murray Hill, NJ, USA

    E. G. Coffman Jr. & M. Yannakakis

  2. Department of Management Sciences, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada

    M. J. Magazine & C. Santos

Authors
  1. E. G. Coffman Jr.
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M. Yannakakis
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. M. J. Magazine
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. C. Santos
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Coffman, E.G., Yannakakis, M., Magazine, M.J. et al. Batch sizing and job sequencing on a single machine. Ann Oper Res 26, 135–147 (1990). https://doi.org/10.1007/BF02248589

Download citation

  • Published:

  • Issue Date:

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

Keywords

Search

Navigation