Skip to main content
SpringerLink
Log in

Sequencing jobs with random processing times to minimize weighted completion time variance

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

We examine the problem of sequencing a set of jobs on a single machine, where each job has a random processing time and is associated with a known, job-dependent weight. The objective is to minimize the expectation of the weighted variance of job completion times. We establish the NP-completeness of this problem, and further show that the problem under some compatible conditions is NP-complete in the ordinary sense. We introduce the concept of a W-shaped solution for the problem and find that an optimal W-shaped sequence exists under the compatible conditions. We propose an exact algorithm, based on this W-shaped property, which can generate an optimal solution in pseudopolynomial time.

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 and G.D. Scudder, Sequencing with earliness and tardiness penalties: A review, Operations Research 38(1990)22–36.

    Google Scholar 

  2. X. Cai, Minimization of agreeably weighted variance in single machine systems, European Journal of Operational Research 85(1995)576–592.

    Article  Google Scholar 

  3. X. Cai, V-Shape property for job sequences that minimize the expected completion time variance, European Journal of Operational Research 91(1996)118–123.

    Article  Google Scholar 

  4. T.C.E. Cheng and M. Gupta, Survey of scheduling research involving due date determination decisions, European Journal of Operational Research 38(1989)156–166.

    Article  Google Scholar 

  5. P. De, J.B. Ghosh and C.E. Wells, On the minimization of completion time variance with a bicriteria extension, Operations Research 40(1992)1148–1155.

    Google Scholar 

  6. S. Eilon and I.G. Chowdhury, Minimizing waiting time variance in the single machine problem, Management Science 23(1977)567–575.

    Google Scholar 

  7. M.R. Garey, R.E. Tarjan and G.T. Wilfong, One-processor scheduling with symmetric earliness and tardiness penalty, Mathematics of Operations Research 13(1988)330–348.

    Google Scholar 

  8. M.C. Gupta, Y.P. Gupta and A. Kumar, Minimizing flow time variance in a single machine system using genetic algorithms, European Journal of Operational Research 70(1993)289–303.

    Article  Google Scholar 

  9. N. Hall and W. Kubiak, Proof of the conjecture of Schrage about the completion time variance problem, Operations Research Letters 10(1991)467–473.

    Article  Google Scholar 

  10. N. Hall and M.E. Posner, Earliness-tardiness scheduling problems, I: Weighted deviation of completion times about a common due date, Operations Research 39(1991)836–846.

    Google Scholar 

  11. N. Hall, W. Kubiak and S.P. Sethi, Earliness-tardiness scheduling problems, II: Deviation of completion times about a restrictive common due date, Operations Research 39(1991)847–856.

    Google Scholar 

  12. G.H. Hardy, J.E. Littlewood and G. Polya, Inequalities, Cambridge University Press, London, 1934.

    Google Scholar 

  13. J.J. Kanet, Minimizing variation of flow time in single machine systems, Management Science 27(1981)1453–1459.

    Google Scholar 

  14. H. Kise, T. Ibaraki and H. Mine, A solvable case of the one-machine scheduling problem with ready and due times, Operations Research 26(1978)121–126.

    Google Scholar 

  15. W. Kubiak, Completion time variance on a single machine is difficult, Operations Research Letters 12(1993)49–59.

    Article  Google Scholar 

  16. E.L. Lawler, Sequencing to minimize the weighted number of tardy jobs, Rev. Automat. Informat. Rec. Opnl. 10(1976)27–33.

    Google Scholar 

  17. E.L. Lawler, A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness, Annals of Discrete Mathematics 1(1977)331–342.

    Article  Google Scholar 

  18. C.-Y. Lee, S.L. Danusaputro and C.-S. Lin, Minimizing weighted number of tardy jobs and weighted earliness-tardiness penalties about a common due date, Computers and Operations Research 18(1991)379–389.

    Article  Google Scholar 

  19. A.G. Merten and M.E. Muller, Variance minimization in single machine sequencing problems, Management Science 18(1972)518–528.

    Google Scholar 

  20. J. Mittenthal and M. Raghavachari, Stochastic single machine scheduling with quadratic early-tardy penalties, Operations Research 41(1993)786–796.

    Google Scholar 

  21. M. Pinedo, Stochastic scheduling with release dates and due dates, Operations Research 31(1983) 559–572.

    Google Scholar 

  22. L. Schrage, Minimizing the time-in-system variance for a finite jobset, Management Science 21 (1975)540–543.

    Article  Google Scholar 

  23. V. Vani and M. Raghavachari, Deterministic and random single machine sequencing with variance minimization, Operations Research 35(1987)111–120.

    Google Scholar 

  24. S. Zhou and X. Cai, Variance minimization — relationship between completion time variance and waiting time variance, Journal of Australian Mathematical Society, Series B 38(1996)126–139.

    Google Scholar 

Download references

Authors
  1. X. Cai
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. S. Zhou
    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

Cai, X., Zhou, S. Sequencing jobs with random processing times to minimize weighted completion time variance. Annals of Operations Research 70, 241–260 (1997). https://doi.org/10.1023/A:1018926305578

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1018926305578

Search

Navigation