Abstract
We consider the single-machine scheduling problem of minimizing the number of late jobs. We omit here one of the standard assumptions in scheduling theory, which is that the processing times are deterministic. In this scheduling environment, the completion times will be stochastic variables as well. Instead of looking at the expected number of on time jobs, we present a new model to deal with the stochastic completion times, which is based on using a chance constraint to define whether a job is on time or late: a job is on time if the probability that it is completed by the deterministic due date is at least equal to a certain given minimum success probability. We have studied this problem for four classes of stochastic processing times. The jobs in the first three classes have processing times that follow: (i) A gamma distribution with shape parameter p j and scale parameter β, where β is common to all jobs; (ii) A negative binomial distribution with parameters p j and r, where r is the same for each job; (iii) A normal distribution with parameters p j and σ 2 j . The jobs in the fourth class have equally disturbed processing times, that is, the processing times consist of a deterministic part and a random component that is independently, identically distributed for each job. We show that the first two cases have a common characteristic that makes it possible to solve these problems in O(nlog n) time through the algorithm by Moore and Hodgson. To analyze the third and fourth problem we need the additional assumption that the due dates and the minimum success probabilities are agreeable. We show that under this assumption the third problem is \(\mathcal {NP}\) -hard in the ordinary sense, whereas the fourth problem is solvable by Moore and Hodgson’s algorithm.
We further indicate how the problem of maximizing the expected number of on time jobs (with respect to the standard definition) can be tackled if we add the constraint that the on time jobs are sequenced in a given order and when we require that the probability that a job is on time amounts to at least some given lower bound.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Dean, B. C. (2005). Approximation algorithms for stochastic scheduling problems. PhD thesis, MIT. www.cs.clemson.edu/~bcdean/bdean_phd_thesis.pdf.
Jackson, J. R. (1955). Scheduling a production line to minimize maximum tardiness (Research Report 43). Management Science Research Project, University of California, Los Angeles.
Karp, R. M. (1972). Reducibility among combinatorial problems. In R. E. Miller & J. W. Thatcher (Eds.), Complexity of computer computations (pp. 85–103). New York: Plenum.
Law, A. M., & Kelton, W. D. (2000). Simulation modeling and analysis. New York: McGraw–Hill.
Lawler, E. L. (unpublished) Scheduling a single machine to minimize the number of late jobs. Unpublished manuscript.
Lawler, E. L., & Moore, J. M. (1969). A functional equation and its application to resource allocation and sequencing problems. Management Science, 16, 77–84.
Lawler, E. L. (1973). Optimal sequencing of a single machine subject to precedence constraints. Management Science, 19, 544–546.
Moore, J. M. (1968). An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management Science, 15, 102–109.
van den Akker, J. M., & Hoogeveen, J. A. (2004). Minimizing the number of tardy jobs. In J. Y. -T. Leung (Ed.), Handbook of scheduling, algorithms, models, and performance analysis (pp. 227–243). Boca Raton: CRC Press.
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by EC Contract IST-1999-14186 (Project alcom-FT).
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License ( https://creativecommons.org/licenses/by-nc/2.0 ), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
van den Akker, M., Hoogeveen, H. Minimizing the number of late jobs in a stochastic setting using a chance constraint. J Sched 11, 59–69 (2008). https://doi.org/10.1007/s10951-007-0034-8
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10951-007-0034-8